您好,登錄后才能下訂單哦!
二叉樹(binary tree)是一顆樹,其中每個節(jié)點都不能有多于兩個的兒子。
1.二叉樹節(jié)點
作為圖的特殊形式,二叉樹的基本組成單元是節(jié)點與邊;作為數(shù)據(jù)結(jié)構(gòu),其基本的組成實體是二叉樹節(jié)點(binary tree node),而邊則對應(yīng)于節(jié)點之間的相互引用。
如下,給出了二叉樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)圖示和相關(guān)代碼:
// 定義節(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.遞歸遍歷
二叉樹本身并不具有天然的全局次序,故為實現(xiàn)遍歷,需通過在各節(jié)點與其孩子之間約定某種局部次序,間接地定義某種全局次序。
按慣例左兄弟優(yōu)先于右兄弟,故若將節(jié)點及其孩子分別記作V、L和R,則下圖所示,局部訪問的次序可有VLR、LVR和LRV三種選擇。根據(jù)節(jié)點V在其中的訪問次序,三種策略也相應(yīng)地分別稱作先序遍歷、中序遍歷和后序遍歷,下面將分別介紹。
2.1 先序遍歷
圖示:
代碼實現(xiàn):
/** * 對該二叉樹進行前序遍歷 結(jié)果存儲到list中 前序遍歷 */ public static void preOrder(BinNode node) { list.add(node); // 先將根節(jié)點存入list // 如果左子樹不為空繼續(xù)往左找,在遞歸調(diào)用方法的時候一直會將子樹的根存入list,這就做到了先遍歷根節(jié)點 if (node.lChild != null) { preOrder(node.lChild); } // 無論走到哪一層,只要當前節(jié)點左子樹為空,那么就可以在右子樹上遍歷,保證了根左右的遍歷順序 if (node.rChild != null) { preOrder(node.rChild); } }
2.2 中序遍歷
圖示:
代碼實現(xiàn):
/** * 對該二叉樹進行中序遍歷 結(jié)果存儲到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 后序遍歷
實例圖示:
代碼實現(xiàn):
/** * 對該二叉樹進行后序遍歷 結(jié)果存儲到list中 */ public static void postOrder(BinNode node) { if (node.lChild != null) { postOrder(node.lChild); } if (node.rChild != null) { postOrder(node.rChild); } list.add(node); }
附:測試相關(guān)代碼
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 + " "); } } // 樹的初始化:先從葉節(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); }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。