二叉樹(binary tree)是一顆樹，其中每個節(jié)點都不能有多于兩個的兒子。
讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：空間域名、虛擬主機、營銷軟件、網站建設、韓城網站維護、網站推廣。
1.二叉樹節(jié)點
作為圖的特殊形式，二叉樹的基本組成單元是節(jié)點與邊；作為數據結構，其基本的組成實體是二叉樹節(jié)點（binary tree node），而邊則對應于節(jié)點之間的相互引用。
如下，給出了二叉樹節(jié)點的數據結構圖示和相關代碼：
重慶分公司
重慶分公司
// 定義節(jié)點類：
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.遞歸遍歷
二叉樹本身并不具有天然的全局次序，故為實現遍歷，需通過在各節(jié)點與其孩子之間約定某種局部次序，間接地定義某種全局次序。
按慣例左兄弟優(yōu)先于右兄弟，故若將節(jié)點及其孩子分別記作V、L和R，則下圖所示，局部訪問的次序可有VLR、LVR和LRV三種選擇。根據節(jié)點V在其中的訪問次序，三種策略也相應地分別稱作先序遍歷、中序遍歷和后序遍歷，下面將分別介紹。
2.1 先序遍歷
圖示：
代碼實現：
/**
* 對該二叉樹進行前序遍歷 結果存儲到list中 前序遍歷
*/
public static void preOrder(BinNode node) {
list.add(node); // 先將根節(jié)點存入list
// 如果左子樹不為空繼續(xù)往左找，在遞歸調用方法的時候一直會將子樹的根存入list，這就做到了先遍歷根節(jié)點
if (node.lChild != null) {
preOrder(node.lChild);
}
// 無論走到哪一層，只要當前節(jié)點左子樹為空，那么就可以在右子樹上遍歷，保證了根左右的遍歷順序
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 Listlist = new ArrayList (); 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 + " "); } } // 樹的初始化:先從葉節(jié)點開始,由葉到根 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); }
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持創(chuàng)新互聯。
