Java數(shù)據(jù)結(jié)構(gòu)最清晰圖解二叉樹(shù)前 中 后序遍歷
一,前言
二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)中重要的一部分,它的前中后序遍歷始終貫穿我們學(xué)習(xí)二叉樹(shù)的過(guò)程,所以掌握二叉樹(shù)三種遍歷是十分重要的。本篇主要是圖解+代碼Debug分析,概念的部分講非常少,重中之重是圖解和代碼Debug分析,我可以保證你看完此篇博客對(duì)于二叉樹(shù)的前中后序遍歷有一個(gè)新的認(rèn)識(shí)??!廢話不多說(shuō),讓我們學(xué)起來(lái)吧??!
二,樹(shù)
①概念
樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗?起來(lái)像一棵倒掛的樹(shù),也就是說(shuō)它是根朝上,而葉朝下的。它具有以下的特點(diǎn):
有一個(gè)特殊的節(jié)點(diǎn),稱(chēng)為根節(jié)點(diǎn),根節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)
除根節(jié)點(diǎn)外,其余節(jié)點(diǎn)被分成M(M > 0)個(gè)互不相交的集合T1、T2、......、Tm,其中每一個(gè)集合 Ti (1 <= i <= m) 又是一棵與樹(shù)類(lèi)似的子樹(shù)。每棵子樹(shù)的根節(jié)點(diǎn)有且只有一個(gè)前驅(qū),可以有0個(gè)或多個(gè)后繼
樹(shù)是遞歸定義的。
②樹(shù)的基礎(chǔ)概念
節(jié)點(diǎn)的度:一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度
樹(shù)的度:一棵樹(shù)中,最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度
葉子節(jié)點(diǎn)或終端節(jié)點(diǎn):度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)
雙親節(jié)點(diǎn)或父節(jié)點(diǎn):若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn),則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn)
孩子節(jié)點(diǎn)或子節(jié)點(diǎn):一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)
根結(jié)點(diǎn):一棵樹(shù)中,沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)
節(jié)點(diǎn)的層次:從根開(kāi)始定義起,根為第1層,根的子節(jié)點(diǎn)為第2層,以此類(lèi)推
樹(shù)的高度或深度:樹(shù)中節(jié)點(diǎn)的最大層次
三,二叉樹(shù)
①概念
一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉 樹(shù)組成。
二叉樹(shù)的特點(diǎn):
1. 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),即二叉樹(shù)不存在度大于 2 的結(jié)點(diǎn)。
2. 二叉樹(shù)的子樹(shù)有左右之分,其子樹(shù)的次序不能顛倒,因此二叉樹(shù)是有序樹(shù)。
②兩種特殊的二叉樹(shù)
1. 滿二叉樹(shù): 一個(gè)二叉樹(shù),如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,則這個(gè)二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō),如果 一個(gè)二叉樹(shù)的層數(shù)為K,且結(jié)點(diǎn)總數(shù)是 ,則它就是滿二叉樹(shù)。
2. 完全二叉樹(shù): 完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的,有n 個(gè)結(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全 二叉樹(shù)。 要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。
③二叉樹(shù)的性質(zhì)
1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹(shù)的第i層上最多有2^(i-1)?(i>0)個(gè)結(jié)點(diǎn)
2. 若規(guī)定只有根節(jié)點(diǎn)的二叉樹(shù)的深度為1,則深度為K的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^k-1 (k>=0)
3. 對(duì)任何一棵二叉樹(shù), 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0=n2+1
4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為log2(n+1)上取整
四,二叉樹(shù)遍歷
二叉樹(shù)是有四種遍歷,層序遍歷這里不講。
①二叉樹(shù)的遍歷
所謂遍歷(Traversal)是指沿著某條搜索路線,依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作 依賴(lài)于具體的應(yīng)用問(wèn)題(比如:打印節(jié)點(diǎn)內(nèi)容、節(jié)點(diǎn)內(nèi)容加1)。 遍歷是二叉樹(shù)上最重要的操作之一,是二叉樹(shù)上進(jìn) 行其它運(yùn)算之基礎(chǔ)。
在遍歷二叉樹(shù)時(shí),如果沒(méi)有進(jìn)行某種約定,每個(gè)人都按照自己的方式遍歷,得出的結(jié)果就比較混亂,如果按照某種 規(guī)則進(jìn)行約定,則每個(gè)人對(duì)于同一棵樹(shù)的遍歷結(jié)果肯定是相同的。如果N代表根節(jié)點(diǎn),L代表根節(jié)點(diǎn)的左子樹(shù),R代 表根節(jié)點(diǎn)的右子樹(shù),則根據(jù)遍歷根節(jié)點(diǎn)的先后次序有以下遍歷方式:
1. NLR:前序遍歷(Preorder Traversal 亦稱(chēng)先序遍歷)——訪問(wèn)根結(jié)點(diǎn)--->根的左子樹(shù)--->根的右子樹(shù)。
2. LNR:中序遍歷(Inorder Traversal)——根的左子樹(shù)--->根節(jié)點(diǎn)--->根的右子樹(shù)。
?3. LRN:后序遍歷(Postorder Traversal)——根的左子樹(shù)--->根的右子樹(shù)--->根節(jié)點(diǎn)。
?由于被訪問(wèn)的結(jié)點(diǎn)必是某子樹(shù)的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根 的左子樹(shù)和根的右子樹(shù)。NLR、LNR和LRN分別又稱(chēng)為先根遍歷、中根遍歷和后根遍歷。
注意:三種遍歷中只有訪問(wèn)根節(jié)點(diǎn)打印,每一種遍歷當(dāng)訪問(wèn)到每一個(gè)節(jié)點(diǎn)都要有對(duì)應(yīng)三種不同的遍歷方式,直到遍歷到null返回到該根節(jié)點(diǎn)繼續(xù)完成遍歷?。。”热缯f(shuō)前序遍歷,我每訪問(wèn)一個(gè)節(jié)點(diǎn)都要執(zhí)行問(wèn)根結(jié)點(diǎn)--->根的左子樹(shù)--->根的右子樹(shù)這三步,中序后序遍歷一樣。
以下面這個(gè)二叉樹(shù)為例,接下來(lái)就是詳解
②前序遍歷
圖解
?代碼分析
我們用枚舉法創(chuàng)建這個(gè)二叉樹(shù)
public TreeNode createTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; }
// 前序遍歷 void preOrderTraversal(TreeNode root){ if(root == null) { return; } System.out.print(root.val+" "); preOrderTraversal(root.left); preOrderTraversal(root.right); }
DeBug分析
③中序遍歷
圖解
// 中序遍歷 void inOrderTraversal(TreeNode root){ if(root == null) { return; } inOrderTraversal(root.left); System.out.print(root.val+" "); inOrderTraversal(root.right); }
?DeBug分析
④后序遍歷
圖解
// 后序遍歷 void postOrderTraversal(TreeNode root){ if(root == null) { return; } postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.print(root.val+" "); }
?DeBug分析
五,完整代碼
class TreeNode{ public char val; public TreeNode right; public TreeNode left; public TreeNode(char val){ this.val = val; } } public class BinaryTree { public TreeNode createTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } // 前序遍歷 void preOrderTraversal(TreeNode root){ if(root == null) { return; } System.out.print(root.val+" "); preOrderTraversal(root.left); preOrderTraversal(root.right); } // 中序遍歷 void inOrderTraversal(TreeNode root){ if(root == null) { return; } inOrderTraversal(root.left); System.out.print(root.val+" "); inOrderTraversal(root.right); } // 后序遍歷 void postOrderTraversal(TreeNode root){ if(root == null) { return; } postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.print(root.val+" "); } }
public class TestDeno { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.preOrderTraversal(root); System.out.println(); binaryTree.inOrderTraversal(root); System.out.println(); binaryTree.postOrderTraversal(root); } }
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)最清晰圖解二叉樹(shù)前 中 后序遍歷的文章就介紹到這了,更多相關(guān)Java 二叉樹(shù)遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)的實(shí)現(xiàn)詳解
- 詳解Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)
- Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)的原理與實(shí)現(xiàn)
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹(shù)
- java數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹(shù)
- Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)前中后序遍歷非遞歸的具體實(shí)現(xiàn)詳解
- Java數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)難點(diǎn)解析
- Java?數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹(shù)題集下
相關(guān)文章
Java中父類(lèi)和子類(lèi)之間的轉(zhuǎn)換操作示例
這篇文章主要介紹了Java中父類(lèi)和子類(lèi)之間的轉(zhuǎn)換操作,結(jié)合實(shí)例形式分析了Java中父類(lèi)和子類(lèi)之間的轉(zhuǎn)換相關(guān)原理、操作技巧與使用注意事項(xiàng),需要的朋友可以參考下2020-05-05基于紅黑樹(shù)插入操作原理及java實(shí)現(xiàn)方法(分享)
下面小編就為大家分享一篇基于紅黑樹(shù)插入操作原理及java實(shí)現(xiàn)方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2017-12-12javafx tableview鼠標(biāo)觸發(fā)更新屬性詳解
這篇文章主要為大家詳細(xì)介紹了javafx tableview鼠標(biāo)觸發(fā)更新屬性的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-08-08解析SpringBoot項(xiàng)目開(kāi)發(fā)之Gzip壓縮過(guò)程
這篇文章主要介紹了SpringBoot項(xiàng)目開(kāi)發(fā)之Gzip壓縮過(guò)程,本文給大家分享幾種Gzip壓縮方式,通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-07-07SpringBoot集成Redis,并自定義對(duì)象序列化操作
這篇文章主要介紹了SpringBoot集成Redis,并自定義對(duì)象序列化操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06Java IO流和文件操作實(shí)現(xiàn)過(guò)程解析
這篇文章主要介紹了Java IO流和文件操作實(shí)現(xiàn)過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-10-10自定義mybatis插件如何實(shí)現(xiàn)sql日志打印
這篇文章主要介紹了自定義mybatis插件如何實(shí)現(xiàn)sql日志打印問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-05-05Java使用MulticastSocket實(shí)現(xiàn)群聊應(yīng)用程序
這篇文章主要為大家詳細(xì)介紹了Java使用MulticastSocket實(shí)現(xiàn)群聊應(yīng)用程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05