Java數(shù)據(jù)結(jié)構(gòu)之二叉樹遍歷算法與底層實現(xiàn)方法剖析
1. 樹型結(jié)構(gòu)（了解）
1.1 概念
樹是一種非線性的數(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個或多個后繼
注意：樹是遞歸定義的。
樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)
1.2 概念（重要）
結(jié)點的度：一個結(jié)點含有子樹的個數(shù)稱為該結(jié)點的度； 如上圖：A的度為6
樹的度：一棵樹中，所有結(jié)點度的最大值稱為樹的度； 如上圖：樹的度為6
葉子結(jié)點或終端結(jié)點：度為0的結(jié)點稱為葉結(jié)點； 如上圖：B、C、H、I...等節(jié)點為葉結(jié)點
雙親結(jié)點或父結(jié)點：若一個結(jié)點含有子結(jié)點，則這個結(jié)點稱為其子結(jié)點的父結(jié)點； 如上圖：A是B的父結(jié)點
孩子結(jié)點或子結(jié)點：一個結(jié)點含有的子樹的根結(jié)點稱為該結(jié)點的子結(jié)點； 如上圖：B是A的孩子結(jié)點
根結(jié)點：一棵樹中，沒有雙親結(jié)點的結(jié)點；如上圖：A
結(jié)點的層次：從根開始定義起，根為第1層，根的子結(jié)點為第2層，以此類推
樹的高度或深度：樹中結(jié)點的最大層次； 如上圖：樹的高度為4
樹的以下概念只需了解，在看書時只要知道是什么意思即可：
非終端結(jié)點或分支結(jié)點：度不為0的結(jié)點； 如上圖：D、E、F、G...等節(jié)點為分支結(jié)點
兄弟結(jié)點：具有相同父結(jié)點的結(jié)點互稱為兄弟結(jié)點； 如上圖：B、C是兄弟結(jié)點
堂兄弟結(jié)點：雙親在同一層的結(jié)點互為堂兄弟；如上圖：H、I互為兄弟結(jié)點
結(jié)點的祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點；如上圖：A是所有結(jié)點的祖先
子孫：以某結(jié)點為根的子樹中任一結(jié)點都稱為該結(jié)點的子孫。如上圖：所有結(jié)點都是A的子孫
森林：由m（m>=0）棵互不相交的樹組成的集合稱為森林
1.3 樹的表示形式（了解）
樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法， 孩子表示法、孩子雙親表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。
1.4 樹的應(yīng)用
文件系統(tǒng)管理（目錄和文件）
2. 二叉樹（重點）
2.1 概念
一棵二叉樹是結(jié)點的一個有限集合，該集合：
1. 或者為空
2. 或者是由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成。
從上圖可以看出：
1. 二叉樹不存在度大于2的結(jié)點
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：
2.2 兩種特殊的二叉樹
1. 滿二叉樹: 一棵二叉樹，如果每層的結(jié)點數(shù)都達(dá)到最大值，則這棵二叉樹就是滿二叉樹。也就是說，如果一棵 二叉樹的層數(shù)為K，且結(jié)點總數(shù)是 ，則它就是滿二叉樹。
2. 完全二叉樹: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n 個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從0至n-1的結(jié)點一一對應(yīng)時稱之為完 全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
2.3 二叉樹的性質(zhì)
1. 若規(guī)定根結(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有
(i>0)個結(jié)點
2. 若規(guī)定只有根結(jié)點的二叉樹的深度為1，則深度為K的二叉樹的最大結(jié)點數(shù)是
(k>=0)
3. 對任何一棵二叉樹, 如果其葉結(jié)點個數(shù)為 n0, 度為2的非葉結(jié)點個數(shù)為 n2,則有n0＝n2＋1（度為0的節(jié)點會比度為2的節(jié)點多一個）二叉樹節(jié)點
一棵N個節(jié)點的樹產(chǎn)生N-1條邊
度為0的節(jié)點n0個，產(chǎn)生0條邊
度為1的節(jié)點n1個，產(chǎn)生n1條邊
度為2的節(jié)點n2個產(chǎn)生2*n2條邊
n1+2*n2=N-1 表達(dá)式1
n0+n1+n2=N 表達(dá)式2
推出 n2+1=n0
4. 具有n個結(jié)點的完全二叉樹的深度k log（n+1）為上取整
5. 對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的順序?qū)λ泄?jié)點從0開始編號則對于序號為i 的結(jié)點有：
若i>0，雙親序號：(i-1)/2；i=0，i為根結(jié)點編號，無雙親結(jié)點
若2i+1<n，左孩子序號：2i+1，否則無左孩子
若2i+2<n，右孩子序號：2i+2，否則無右孩子
1. 某二叉樹共有 399 個結(jié)點，其中有 199 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（ ）
A 不存在這樣的二叉樹
B 200
C 198
D 199
2.在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（ ）
A n
B n+1
C n-1
D n/2
3.一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為（）
A 383
B 384
C 385
D 386
4.一棵完全二叉樹的節(jié)點數(shù)為531個，那么這棵樹的高度為（ ）
A 11
B 10
C 8
D 12
2.4 二叉樹的存儲
二叉樹的存儲結(jié)構(gòu)分為：順序存儲和類似于鏈表的鏈?zhǔn)酱鎯?/strong>。
順序存儲在下節(jié)介紹。
二叉樹的鏈?zhǔn)酱鎯κ峭ㄟ^一個一個的節(jié)點引用起來的，常見的表示方式有二叉和三叉表示方式，具體如下：
2.5 二叉樹的基本操作
2.5.1 前置說明
在學(xué)習(xí)二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在大家對二叉樹結(jié)
構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，此處手動快速創(chuàng)建一棵簡單的二叉樹，快速進(jìn)入二叉樹操作學(xué)習(xí)，等 二叉樹結(jié)構(gòu)了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。
2.5.2 二叉樹的遍歷
1. 前中后序遍歷
學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結(jié) 點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題(比如：打印節(jié)點內(nèi)容、節(jié)點內(nèi)容加
1)。 遍歷是二叉樹上最重要的操作之一，是二叉樹上進(jìn)行其它運算之基礎(chǔ)。
在遍歷二叉樹時，如果沒有進(jìn)行某種約定，每個人都按照自己的方式遍歷，得出的結(jié)果就比較混亂，如果按 照某種規(guī)則進(jìn)行約定，則每個人對于同一棵樹的遍歷結(jié)果肯定是相同的。如果N代表根節(jié)點，L代表根節(jié)點的 左子樹，R代表根節(jié)點的右子樹，則根據(jù)遍歷根節(jié)點的先后次序有以下遍歷方式：
NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點--->根的左子樹--->根的右樹。
A B D C E F
LNR：中序遍歷(Inorder Traversal)——根的左子樹--->根節(jié)點--->根的右子樹。
D B A E C F
LRN：后序遍歷(Postorder Traversal)——根的左子樹--->根的右子樹--->根節(jié)點。
D B E C F A
1.某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH 。該完全二叉樹的前序序列為()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
2.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK;中序遍歷：HFIEJKG.則二叉樹根結(jié)點為()
A: E B: F C: G D: H
3.設(shè)一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為()
A: adbce B: decab C: debac D: abcde
4.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF ，則按層次輸出(同一層從左到右)的序列為()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
【參考答案】 1.A 2.A 3.D 4.A
二叉樹初始化
static class Node{
char val;
Node left;
Node right;
public Node(char val){
this.val = val;
}
}
public Node createTree(){
Node A = new Node('A');
Node B = new Node('B');
Node C = new Node('C');
Node D = new Node('D');
Node E = new Node('E');
Node F = new Node('F');
Node G = new Node('G');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
return A;
}二叉樹先序遍歷
void preOrder(Node root){
if(root==null){
return;
}
System.out.print(root.val);
preOrder(root.left);
preOrder(root.right);
}二叉樹中序遍歷
void inOrder(Node root){
if(root==null){
return;
}
preOrder(root.left);
System.out.print(root.val);
preOrder(root.right);
}二叉樹后序遍歷
void postOrder(Node root){
if(root==null){
return;
}
preOrder(root.left);
preOrder(root.right);
System.out.print(root.val);
}2. 層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點所在 層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層 上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
二叉樹前序非遞歸遍歷實現(xiàn)、
List<Integer> list=new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null){
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
} List<Integer> list=new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null){
return list;
}
list.add(root.val);
List<Integer> lefttree = preorderTraversal(root.left);
list.addAll(leftree);
List<Integer> righttree = preorderTraversal(root.right);
list.addAll(rightree);
return list;
}獲取節(jié)點個數(shù)
public static int size1=0;
public void sizoe(Node root){
if(root==null){
return;
}
size1++;
sizoe(root.left);
sizoe(root.right);
}獲取葉子節(jié)點
public int leaves(Node root){
if(root==null){
return 0;
}
if(root.left==null && root.right==null){
return 1;
}
return leaves(root.left)+leaves(root.right);
}獲取第k層節(jié)點個數(shù)
public int getleaves(Node root,int i){
int j=i;
if(root==null){
return 0;
}
if(j==1){
return 1;
}
return getleaves(root.left,j-1)
+getleaves(root.right,j-1);
}// 獲取二叉樹的高度 時間復(fù)雜度和空間復(fù)雜度分別為 O(N) O(log2N)
int getHeight(Node root){
if(root==null){
return 0;
}
int l=getHeight(root.left);
int r=getHeight(root.right);
return Math.max(l,r)+1;
}查找val元素
public Node findVal(Node root,char val){
if(root==null){
return null;
}
if(root.val==val){
return root;
}
Node l= findVal(root.left,val);
if(l!=null){
return l;
}
Node r= findVal(root.right,val);
if(r!=null){
return r;
}
return null;
}1. 檢查兩顆樹是否相同
public boolean isSameTree(TreeNode p1, TreeNode p2) {
//先判斷結(jié)構(gòu)是否一樣
if(p1!=null&&p2==null||p1==null&&p2!=null){
return false;
}
//他們的是否同時為空，同時為空那么他們的結(jié)構(gòu)一樣
if(p1==null&&p2==null){
return true;
}
//結(jié)構(gòu)一樣以后，判斷值是否一樣
if(p1.val!=p2.val){
return false;
}
return isSameTree(p1.left,p2.left) && isSameTree(p1.right,p2.right);
}2. 另一顆樹的子樹
我們?nèi)ケ闅vroot樹里面的節(jié)點，找到有沒有和subroot樹 一樣的樹，還需要利用上面的算法
1.當(dāng)前子樹和根節(jié)點是否一樣？
2.判斷子樹是不是當(dāng)前root的左子樹一樣？
3.判斷子樹是不是當(dāng)前root的右子樹一樣？
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null){
return false;
}
從根開始判斷是否一樣
if(isSameTree(root,subRoot)){
return true;
}
if(isSubtree(root.left,subRoot)){
return true;
}
if(isSubtree(root.right,subRoot)){
return true;
}
return false;
}
public boolean isSameTree(TreeNode p1, TreeNode p2) {
if(p1!=null&&p2==null||p1==null&&p2!=null){
return false;
}
if(p1==null&&p2==null){
return true;
}
if(p1.val!=p2.val){
return false;
}
return isSameTree(p1.left,p2.left) && isSameTree(p1.right,p2.right);
}3. 翻轉(zhuǎn)二叉樹。
首先將root節(jié)點的左右子樹進(jìn)行交換，然后再把root的letf子樹放入invertTree進(jìn)行遞歸，root的right子樹放入invertTree進(jìn)行遞歸，最后返回根節(jié)點
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}5. 對稱二叉樹
我們的思路是，分成兩部分，第一部分判斷根節(jié)點是否為空，如果為空就是對稱的，如果不為空，那么就進(jìn)行左右樹的判斷，第一就是他們之間一個為空一個不為空的情況，然后就是他們不為空的時候判斷是否相等，
public boolean isSymmetric(TreeNode root) {
if(root==null){
return false;
}
return isSymmetriccha(root.left,root.right);
}
public boolean isSymmetriccha(TreeNode leftree,TreeNode rightree) {
if(leftree==null&&rightree!=null||leftreet!=null&&rightree==null){
return false;
}
if(leftree==null&&rightree==null){
return true;
}
if(leftree.val!=rightree.val){
return false;
}
return isSymmetriccha(leftree.left,rightree.right) && isSymmetriccha(leftree.right,rightreet.left);
}判斷一顆二叉樹是否是平衡二叉樹。
對于一顆平衡二叉樹，他的左右子樹高度差不超過1，如果超過則不是平衡二叉樹，同時他的每一棵子樹的左右樹高度差也是不能超過1，所以我們的思路是遍歷每一個節(jié)點，并且去去求節(jié)點的左右樹高度差是不是超過1
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int c= Math.abs(getHeight(root.left)-getHeight(root.right));
if(c>=2){
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
public int getHeight(TreeNode root){
if(root==null){
return 0;
}
int l=getHeight(root.left);
二叉搜索樹與雙向鏈表
二叉搜索的特點是左樹所有節(jié)點比根小，右樹所有節(jié)點比根大，
因此二叉搜索的中序遍歷就是有序的，如何把他變成一個雙向鏈表呢，我們的思路是把他們的 right(紅色)作為后繼，left作為前驅(qū)(綠色)，
當(dāng)我們不斷進(jìn)行中序遍歷，來帶最左邊節(jié)點1以后，此時root就是1，我們定義一個prev空指針，來進(jìn)行改接，首先是將root的left指針指向prev，然后把root賦給prev，prev就是1，此時程序返回到root=2這里，prev是1，我們將root的left指針指向prev，然后呢再將prev的right指針指向root，再將root賦給prev，prev變成2，然后呢根據(jù)中序遍歷，又來到root=3在這里，依次這樣下去，同時呢我們要確定prev是否為空，為空就不能使用right指針，就能把二叉搜索樹變成雙向鏈表
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
Convertchai(pRootOfTree);
TreeNode head=pRootOfTree;
while(head.left!=null){
head=head.left;
}
return head;
}
public void Convertchai(TreeNode root) {
if(root==null){
return;
}
Convertchai(root.left);
root.left=prev;
if(prev!=null){
prev.right=root;
}
prev=root;
Convertchai(root.right);
}根據(jù)輸入字符創(chuàng)建二叉樹， ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹。建立起此二叉樹以后，再對二叉樹進(jìn)行中序遍歷，輸出遍歷結(jié)果。
我們的思路是用一個字符串來傳入，對這個字符串進(jìn)行遍歷，遇到一個字符就創(chuàng)建節(jié)點，如何遇到#，就讓i往后走，例如我們 對ABC##DE#G##F###，一直到c節(jié)點的時候，然后我們讓i++，遇到#，不對這個做任何操作，只讓他返回空，于是c的左右都是空，然后我們遞歸回到b繼續(xù)開始創(chuàng)建，
public static int i=0;
public static Treenode createtree(String str){
Treenode root=null;
if(str.charAt(i)!='#'){
root=new Treenode(str.charAt(i));
i++;
root.left=createtree(str);
root.right=createtree(str);
}
else{
i++;
}
return root;
}二叉樹的層序遍歷
我們的思路是對二叉樹進(jìn)行先序遍歷，同時定義一個隊列，將根節(jié)點A入隊，然后開始隊列不為空的循環(huán)，循環(huán)里面，定義cur指針接受隊列里面彈出的元素，然后對這個節(jié)點進(jìn)行判斷，他的左邊是否為空，不為空入隊，在判斷右邊是否為空，不為空入隊，一直循環(huán)下去，直到隊列為空
public void levelorder(Node root){
if(root==null){
return;
}
Queue<Node> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node cur=queue.poll();
System.out.print(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}判斷一顆二叉樹是否為完全二叉樹
public boolean isCompletetree(Node root){
if(root==null){
return true;
}
Queue<Node> queue=new LinkedList<>();
while(!queue.isEmpty()){
Node cur=queue.poll();
if(cur!=null){
queue.offer(cur.left);
queue.offer(cur.right);
}
else{
break;
}
}
while(!queue.isEmpty()){
Node cur=queue.poll();
if(cur!=null){
return false;
}
}
return true;
}給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先 。
尋找pq公共祖先，我們的思路是對這顆樹進(jìn)行遍歷，如果p在root上，那么root就是公共祖先，如果q在root上，他是公共祖先,然后我們先序遞歸下去，同時定義leftree指針和rightree指針，去接收左右子樹中是否存在q或者q，如果左樹右樹同時不為空，那么這個root就是公共祖先，如果只是左樹不為空，則就是返回左樹，同理也是返回右樹
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(root==p||root==q){
return root;
}
TreeNode lefttree=lowestCommonAncestor(root.left,p,q);
TreeNode righttree=lowestCommonAncestor(root.right,p,q);
if(lefttree!=null&&righttree!=null){
return root;
}
else if(lefttree!=null){
return lefttree;
}
else{
return righttree;
}
}獲得節(jié)點路徑
9. 根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
我們的思路是因為前序的第一個接觸到的字符就是根，然后是根的左右，而中序遍歷，是先左子樹 再根 最后右樹，比如定義一個i=0;一開始前序遍歷里面的e就是整顆的根，然后我們在中序里面找到e，通過e把他們分為根e的左右子樹部分，在中序里面找到e的下標(biāo)，在e之前就是左子樹部分，e的右邊就是右樹部分，隨后先序里面再后走i++,這個時候來到了e的左樹根f，我們同樣去中序里面找到f，并返回他的下標(biāo)，f之前就是他的左樹部分，e的后面就是他的右數(shù)部分，依次這樣遞歸下去，然后直到be<end返回
public int preind=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return createTree(preorder,inorder,0,inorder.length-1);
}
public TreeNode createTree(int[] preorder,int[] inorder,int be ,int end) {
//root沒有子樹了
if(be>end){
return null;
}
TreeNode root=new TreeNode(preorder[preind]);
int rootindex=findval(inorder,be,end,preorder[preind]);
preind++;
root.left=createTree(preorder,inorder,be,rootindex-1);
root.right=createTree(preorder,inorder,rootindex+1,end);
return root;
}
public int findval(int []arr,int begin,int end,int val){
for(int i=begin;i<=end;i++){
if(arr[i]==val){
return i;
}
}
return -1;
}二叉樹創(chuàng)建字符串。
public String tree2str(TreeNode root) {
if(root==null){
return null;
}
StringBuilder str=new StringBuilder();
creat(root,str);
return str.toString();
}
public void creat(TreeNode root,StringBuilder str){
if(root==null){
return ;
}
str.append(root.val);
if(root.left!=null){
str.append("(");
creat(root.left,str);
str.append(")");
}
else{
if(root.right==null){
return ;
}
else{
str.append("()");
}
}
if(root.right!=null){
str.append("(");
creat(root.right,str);
str.append(")");
}
else{
return;
}
}2. 二叉樹前序非遞歸遍歷實現(xiàn) 。
void setPrev1(Node root){
if(root==null){
return;
}
Node cur=root;
Stack<Node> stack=new Stack<>();
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
System.out.print(cur.val);
cur=cur.left;
}
Node top =stack.pop();
cur=top.right;
}
}13. 二叉樹中序非遞歸遍歷實現(xiàn)。
void inorderNO(Node root){
if(root==null){
return;
}
Node cur=root;
Stack<Node> stack=new Stack<>();
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
Node top =stack.pop();
System.out.print(cur.val);
cur=top.right;
}
}14. 二叉樹后序非遞歸遍歷實現(xiàn)。
void preOrder1(Node root){
if(root==null){
return;
}
Stack<Node> stack=new Stack<>();
Node cur=root;
Node temp=null;
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
Node top=stack.peek();
if(top.right==null||top.right==temp){
System.out.print(cur.val);
stack.pop();
temp=top;
}
else{
cur=top.right;
}
}
}本文摘要： 本文系統(tǒng)介紹了樹型結(jié)構(gòu)和二叉樹的定義、性質(zhì)及操作。首先闡述了樹的基本概念（根節(jié)點、度、層次等）和表示方法，重點講解了二叉樹的兩種特殊類型（滿二叉樹和完全二叉樹）及其性質(zhì)。詳細(xì)說明了二叉樹的存儲結(jié)構(gòu)（順序/鏈?zhǔn)剑┖突静僮鳎ㄇ靶?中序/后序/層序遍歷的實現(xiàn)方法（遞歸與非遞歸），以及計算節(jié)點數(shù)、查找節(jié)點、判斷樹結(jié)構(gòu)等常見算法。最后介紹了二叉樹在構(gòu)建、轉(zhuǎn)換等方面的應(yīng)用實例，如根據(jù)遍歷序列構(gòu)建二叉樹、二叉搜索樹轉(zhuǎn)雙向鏈表等典型問題解決方案。全文通過代碼示例和圖示相結(jié)合的方式，全面展示了二叉樹的理論知識和實踐應(yīng)用。
總結(jié)
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之二叉樹遍歷算法與底層實現(xiàn)方法剖析的文章就介紹到這了,更多相關(guān)Java二叉樹遍歷算法與底層實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Spring裝配Bean之用Java代碼安裝配置bean詳解
這篇文章主要給大家介紹了關(guān)于Spring裝配Bean之用Java代碼安裝配置bean的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用spring具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧。2017-10-10
本文給大家分析了Java8默認(rèn)方法和函數(shù)式接口實例其它創(chuàng)建方式，需要的朋友跟著學(xué)習(xí)下吧。2017-11-11
Spring、SpringMvc和SpringBoot的區(qū)別及說明
Spring框架提供了全面的Java開發(fā)解決方案,核心包括IOC和AOP,SpringMvc作為其中的WEB層開發(fā)框架,通過復(fù)雜的XML配置管理前端視圖和后臺邏輯,SpringBoot則簡化了配置,專注于微服務(wù)接口開發(fā),支持嵌入式服務(wù)器,提高了開發(fā)效率2024-10-10
這篇文章主要介紹了Spring中七種事務(wù)傳播機制詳解,Spring在TransactionDefinition接口中規(guī)定了7種類型的事務(wù)傳播行為,Propagation枚舉則引用了這些類型,開發(fā)過程中我們一般直接用Propagation枚舉,需要的朋友可以參考下2024-01-01
這篇文章主要介紹了Java中HashMap里面key為null存放到哪，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
這篇文章主要介紹了通過案例了解靜態(tài)修飾符static使用場景,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-10-10
這篇文章主要介紹了JPA框架實現(xiàn)分頁查詢和條件查詢功能，JPA是Java Persistence API的簡稱，在過去很多數(shù)據(jù)庫的增刪查改操作都是用這個框架操作的，感興趣想要詳細(xì)了解可以參考下文2023-05-05
雪花算法是一種分布式的id生成算法。原理是將long分成若干個區(qū)段分別管理。本文將利用Java簡單的實現(xiàn)雪花算法，感興趣的可以了解一下2022-12-12
LocalDateTime?是Java8中新加入的日期時間類，現(xiàn)在都?Java20?了，不會還有人沒用過?LocalDateTime?吧？今天給大家演示一下?LocalDateTime?的常用方法2023-04-04
這篇文章主要介紹了在IDEA里gradle配置和使用的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07