溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
二叉樹(binary tree)是一顆樹，其中每個節點都不能有多于兩個的兒子。
1.二叉樹節點
作為圖的特殊形式，二叉樹的基本組成單元是節點與邊；作為數據結構，其基本的組成實體是二叉樹節點（binary tree node），而邊則對應于節點之間的相互引用。
如下，給出了二叉樹節點的數據結構圖示和相關代碼：
// 定義節點類：
private static class BinNode {
private Object element;
private BinNode lChild;// 定義指向左子樹的指針
private BinNode rChild;// 定義指向右子樹的指針
public BinNode(Object element, BinNode lChild, BinNode rChild) {
this.element = element;
this.lChild = lChild;
this.rChild = rChild;
}
}
2.遞歸遍歷
二叉樹本身并不具有天然的全局次序，故為實現遍歷，需通過在各節點與其孩子之間約定某種局部次序，間接地定義某種全局次序。
按慣例左兄弟優先于右兄弟，故若將節點及其孩子分別記作V、L和R，則下圖所示，局部訪問的次序可有VLR、LVR和LRV三種選擇。根據節點V在其中的訪問次序，三種策略也相應地分別稱作先序遍歷、中序遍歷和后序遍歷，下面將分別介紹。
2.1 先序遍歷
圖示：
代碼實現：
/**
* 對該二叉樹進行前序遍歷 結果存儲到list中 前序遍歷
*/
public static void preOrder(BinNode node) {
list.add(node); // 先將根節點存入list
// 如果左子樹不為空繼續往左找，在遞歸調用方法的時候一直會將子樹的根存入list，這就做到了先遍歷根節點
if (node.lChild != null) {
preOrder(node.lChild);
}
// 無論走到哪一層，只要當前節點左子樹為空，那么就可以在右子樹上遍歷，保證了根左右的遍歷順序
if (node.rChild != null) {
preOrder(node.rChild);
}
}
2.2 中序遍歷
圖示：
代碼實現：
/**
* 對該二叉樹進行中序遍歷 結果存儲到list中
*/
public static void inOrder(BinNode node) {
if (node.lChild != null) {
inOrder(node.lChild);
}
list.add(node);
if (node.rChild != null) {
inOrder(node.rChild);
}
}
2.3 后序遍歷
實例圖示：
代碼實現：
/**
* 對該二叉樹進行后序遍歷 結果存儲到list中
*/
public static void postOrder(BinNode node) {
if (node.lChild != null) {
postOrder(node.lChild);
}
if (node.rChild != null) {
postOrder(node.rChild);
}
list.add(node);
}
附：測試相關代碼
private static BinNode root;
private static List<BinNode> list = new ArrayList<BinNode>();
public static void main(String[] args) {
init();
// TODO Auto-generated method stub
//preOrder(root);
//inOrder(root);
postOrder(root);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i).element + " ");
}
}
// 樹的初始化:先從葉節點開始,由葉到根
public static void init() {
BinNode b = new BinNode("b", null, null);
BinNode a = new BinNode("a", null, b);
BinNode c = new BinNode("c", a, null);
BinNode e = new BinNode("e", null, null);
BinNode g = new BinNode("g", null, null);
BinNode f = new BinNode("f", e, g);
BinNode h = new BinNode("h", f, null);
BinNode d = new BinNode("d", c, h);
BinNode j = new BinNode("j", null, null);
BinNode k = new BinNode("k", j, null);
BinNode m = new BinNode("m", null, null);
BinNode o = new BinNode("o", null, null);
BinNode p = new BinNode("p", o, null);
BinNode n = new BinNode("n", m, p);
BinNode l = new BinNode("l", k, n);
root = new BinNode("i", d, l);
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
