Java數(shù)據(jù)結(jié)構(gòu)最清晰圖解二叉樹前 中 后序遍歷
一，前言
二叉樹是數(shù)據(jù)結(jié)構(gòu)中重要的一部分，它的前中后序遍歷始終貫穿我們學(xué)習(xí)二叉樹的過程，所以掌握二叉樹三種遍歷是十分重要的。本篇主要是圖解+代碼Debug分析，概念的部分講非常少，重中之重是圖解和代碼Debug分析，我可以保證你看完此篇博客對于二叉樹的前中后序遍歷有一個新的認(rèn)識??！廢話不多說，讓我們學(xué)起來吧??！
二，樹
①概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看 起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
有一個特殊的節(jié)點，稱為根節(jié)點，根節(jié)點沒有前驅(qū)節(jié)點
除根節(jié)點外，其余節(jié)點被分成M(M > 0)個互不相交的集合T1、T2、......、Tm，其中每一個集合 Ti (1 <= i <= m) 又是一棵與樹類似的子樹。每棵子樹的根節(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼
樹是遞歸定義的。
②樹的基礎(chǔ)概念
節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度
葉子節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點
雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點
孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點
根結(jié)點：一棵樹中，沒有雙親結(jié)點的結(jié)點
節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推
樹的高度或深度：樹中節(jié)點的最大層次
三，二叉樹
①概念
一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉 樹組成。
二叉樹的特點：
1. 每個結(jié)點最多有兩棵子樹，即二叉樹不存在度大于 2 的結(jié)點。
2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹。
②兩種特殊的二叉樹
1. 滿二叉樹: 一個二叉樹，如果每一個層的結(jié)點數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果 一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是 ，則它就是滿二叉樹。
2. 完全二叉樹: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n 個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全 二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
③二叉樹的性質(zhì)
1. 若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)?(i>0)個結(jié)點
2. 若規(guī)定只有根節(jié)點的二叉樹的深度為1，則深度為K的二叉樹的最大結(jié)點數(shù)是2^k-1 (k>=0)
3. 對任何一棵二叉樹, 如果其葉結(jié)點個數(shù)為 n0, 度為2的非葉結(jié)點個數(shù)為 n2,則有n0＝n2＋1
4. 具有n個結(jié)點的完全二叉樹的深度k為log2(n+1)上取整
四，二叉樹遍歷
二叉樹是有四種遍歷，層序遍歷這里不講。
①二叉樹的遍歷
所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作 依賴于具體的應(yīng)用問題(比如：打印節(jié)點內(nèi)容、節(jié)點內(nèi)容加1)。 遍歷是二叉樹上最重要的操作之一，是二叉樹上進 行其它運算之基礎(chǔ)。
在遍歷二叉樹時，如果沒有進行某種約定，每個人都按照自己的方式遍歷，得出的結(jié)果就比較混亂，如果按照某種 規(guī)則進行約定，則每個人對于同一棵樹的遍歷結(jié)果肯定是相同的。如果N代表根節(jié)點，L代表根節(jié)點的左子樹，R代 表根節(jié)點的右子樹，則根據(jù)遍歷根節(jié)點的先后次序有以下遍歷方式：
1. NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點--->根的左子樹--->根的右子樹。
2. LNR：中序遍歷(Inorder Traversal)——根的左子樹--->根節(jié)點--->根的右子樹。
?3. LRN：后序遍歷(Postorder Traversal)——根的左子樹--->根的右子樹--->根節(jié)點。
?由于被訪問的結(jié)點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根 的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。
注意：三種遍歷中只有訪問根節(jié)點打印，每一種遍歷當(dāng)訪問到每一個節(jié)點都要有對應(yīng)三種不同的遍歷方式，直到遍歷到null返回到該根節(jié)點繼續(xù)完成遍歷！?。”热缯f前序遍歷，我每訪問一個節(jié)點都要執(zhí)行問根結(jié)點--->根的左子樹--->根的右子樹這三步，中序后序遍歷一樣。
以下面這個二叉樹為例，接下來就是詳解
②前序遍歷
圖解
?代碼分析
我們用枚舉法創(chuàng)建這個二叉樹
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)最清晰圖解二叉樹前 中 后序遍歷的文章就介紹到這了,更多相關(guān)Java 二叉樹遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹的實現(xiàn)詳解
- 詳解Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹
- Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹的原理與實現(xiàn)
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹
- java數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹
- Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實現(xiàn)詳解
- Java數(shù)據(jù)結(jié)構(gòu)二叉樹難點解析
- Java?數(shù)據(jù)結(jié)構(gòu)進階二叉樹題集下
相關(guān)文章
Java中@RequiredArgsConstructor注解的基本用法
這篇文章主要介紹了Java中@RequiredArgsConstructor注解的基本用法,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-09-09
這篇文章主要為大家詳細(xì)介紹了Java導(dǎo)出CSV文件的方法，分頁查詢大數(shù)據(jù)量，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
SpringBoot啟動失敗的解決方法：A component required a&nb
這篇文章主要介紹了解決SpringBoot啟動失敗：A component required a bean of type ‘xxxxxxx‘ that could not be found.,目前解決方法有兩種，一種是不注入bean的方式，另一種是使用@Component的方式，本文給大家詳細(xì)講解，需要的朋友可以參考下2023-02-02
這篇文章主要介紹了基于ComponentScan注解的掃描范圍及源碼解析,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09
本文是關(guān)于Java IO文件流和垃圾回收問題，一個小的測試程序搞清楚Java IO的問題，希望能幫助有需要的小伙伴2016-07-07
Spring boot中filter類不能注入@Autowired變量問題
這篇文章主要介紹了Spring boot中filter類不能注入@Autowired變量問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
今天小編就為大家分享一篇關(guān)于在AOP中Spring生成代理類的兩種方式，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
這篇文章主要介紹了java根據(jù)富文本生成pdf文件過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-10-10
關(guān)于Process的waitFor死鎖問題及解決方案
這篇文章主要介紹了關(guān)于Process的waitFor死鎖問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
ReentrantLock繼承了Lock接口，?lock方法實際上是調(diào)用了Sync的子類NonfairSync(非公平鎖)的lock方法。ReentrantLock的真正實現(xiàn)在他的兩個內(nèi)部類NonfairSync和FairSync中，默認(rèn)實現(xiàn)是非公平鎖2023-02-02