當初我要是這麼學習二叉樹就好了
2022-01-11由 紙鶴視界 發表于 林業
遞迴樹怎麼畫
目錄
1。 樹形結構
1。1 概念（瞭解）
1。2 概念（重要）
1。3 樹的表示形式
1。4 樹的應用
2。 二叉樹（BinaryTree重點）
2。1 概念
2。2 二叉樹的
5種
基本形態
2。3 兩種特殊的二叉樹
2。3。1 斜樹
2。3。2 滿二叉樹
2。3。3 完全二叉樹
2。4 二叉樹的性質
2。4。1
第i層結點個數
2。4。2
樹的所有最大點個數
2。4。3
葉子結點和非葉子結點數量關係
2。4。4
根據結點求樹深度
2。4。5
父子結點編號關係
2。4。6 小練兵
2。5 二叉樹的儲存
2。5。1 順序儲存
2。5。1。1 完全二叉樹的形式儲存
2。5。1。2 一般樹的形式儲存
2。5。2 鏈式儲存
3。 二叉樹由淺入深解析
3。1 遍歷二叉樹
3。1。1 二叉樹遍歷原理
3。1。2 二叉樹遍歷方法
3。1。2。1 前序遍歷
3。1。2。2 中序遍歷
3。1。2。3 後序遍歷
3。1。2。4 層序遍歷
3。1。3 二叉樹遍歷演算法
3。1。3。1 前序遍歷演算法
根左右
3。1。3。2 中序遍歷演算法
左根右
3。1。3。2 後序遍歷演算法
左右根
3。1。3。2 層序遍歷演算法
上至下， 左至右
3。2 二叉樹建立問題
3。2。1 前序中序構建二叉樹
3。2。2 中序後序構建二叉樹
3。2。3 根據二叉樹建立字串
3。2。4 前序遍歷字串構建二叉樹
3。2。5 合併二叉樹
3。2。6 遞增二叉樹
3。3 經典題目解析
3。3。1 結點個數
3。3。2 葉子結點個數
3。3。3 第k層結點個數
3。3。4 查詢 val 所在結點
3。3。5 相同的樹
3。3。6 另一棵樹子樹
3。3。7 二叉樹最大深度
3。3。8 平衡二叉樹
3。3。9 對稱二叉樹
3。3。10 二叉樹的完全性檢驗
3。3。11 二叉樹最近公公祖先
3。3。12 二叉樹最大寬度
3。4。 特殊的二叉樹問題
3。4。1 搜尋二叉樹
3。4。2 赫夫曼樹及其應用
3。4。1。 赫夫曼樹
3。4。2。赫夫曼樹定義與原理
3。4。3 赫夫曼編碼
3。4。3 線索二叉樹
4。 總結回顧
5。 結束語
1。 樹形結構
1。1 概念（瞭解）
樹不再是順序表， 連結串列， 棧， 佇列那樣一對一的線性結構。 而樹則
是一種一對多的資料結構， 由n（n>=0）個互不相交有限節點組層有層次關係的集合。
特點如下:
有一個特殊的節點， 稱為根節點， 根節點沒有前驅節點
除根節點外， 其餘節點被分成M（M > 0）個互不相交的集合T1， T2， …， Tm，其中每一個集合 <= m） 又是一棵與樹類似的子樹。每棵子樹的根節點有且只有一個前驅，可以有0個或多個後繼
樹是遞迴定義的［樹的定義中用到了樹的概念］
錯誤的二叉樹 D和E不應該相交， I節點有兩個父節點
正確的樹：
1。2 概念（重要）
用的是上圖中正確的二叉樹來解釋概念
節點的度:
一個節點含有的子樹的個數稱為該節點的度［A的度就是2］
非終端節點或分支節點：度不為0的節點［A， B， C， D， E］
樹的度:
一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為3
葉子節點或終端節點:
度為0的節點稱為葉節點； 如上圖：G、H、I、J節點為葉節點
雙親節點或父節點:
若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
孩子節點或子節點:
一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
兄弟節點:
具有相同父節點的節點互稱為兄弟節點［B和C， E和F， G， H和I］
堂兄弟節點:
雙親在同一層的節點互稱為堂兄弟節點［D和E， D和F］
節點的祖先:
從根到該節點的所有分支經歷所有節點［A］
根結點:
一棵樹中，沒有雙親結點的結點；如上圖：A
森林:
由m（m>=0）棵互不相交的樹的集合稱為森林
節點的層次:
從根開始定義起，根為第1層，根的子節點為第2層，以此類推
樹的高度或深度:
樹中節點的最大層次； 如上圖：樹的高度為4
1。3 樹的表示形式
樹結構相對線性表就比較複雜了，要儲存表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法、孩子表示法、孩子兄弟表示法等等。我們這裡就簡單的瞭解其中最常用的
孩子兄弟表示法
【線上OJ常考的就是這種表示形式】
class
Node
{
int
value
；
// 樹中儲存的資料
Node
child
；
// 第一個孩子引用
Node
brother
；
// 下一個兄弟引用
}
1。4 樹的應用
檔案系統管理(目錄和檔案)
2。 二叉樹（BinaryTree重點）
2。1 概念
我們從經典的猜數字遊戲開始， 由淺入深介紹二叉樹。
在100以內猜數字， 最多幾次可以猜對呢？答案是：7
下面是根據每次猜的大小來構建二叉樹
我們發現利用這個大小關係來查詢指定範圍內某個數字， 效率不是高的一丁半點。 因此對於這種具有對立關係的情況： 0和1， 真與假， 上與下， 正與反， 對與錯都適合用樹來建模。 這種特殊的樹狀結構稱為二叉樹
一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成。
特點：
每個節點最多有2顆子樹， 即不存在度大於2的節點
二叉樹有左右子樹之分， 次序不能顛倒， 因此二叉樹也是一顆有序樹
2。2 二叉樹的
5種
基本形態
空二叉樹
只有一個根節點
根節點只有左子樹
根節點只有右子樹
根節點即有左子樹又有右子樹
2。3 兩種特殊的二叉樹
2。3。1 斜樹
顧名思義， 斜樹一定要是斜的， 往哪兒斜也是有講究的。
所有的節點都只有左子樹叫做左斜樹； 所有的節點都只有右子樹叫做右斜樹
左斜樹:
右斜樹:
斜樹有明顯特點： 每一層都只有一個節點， 結點個數和樹的深度相同。
有些同學就奇怪了： 這也能叫樹嗎， 這不是我們熟悉的線性表嗎？
解釋： 對的， 線性表結構可以理解為樹的一種極其特殊的表現形式
2。3。2 滿二叉樹
在一棵二叉樹中， 如果所有分支結點都存在左子樹和右子樹， 並且所有葉子節點都在同一層上， 這樣的二叉樹稱為滿二叉樹
它的樣子看得很美, 很勻稱
滿二叉樹特點：
葉子結點只能出現在最下一層， 出現在其它層就不可能達到平衡
非葉子結點的度一定是2， 否賊就是“缺胳膊少腿”
在同樣深度的二叉樹中， 滿二叉樹結點個數最多， 葉子結點最多
2。3。3 完全二叉樹
把一顆具有 n 個節點的二叉樹按層序編號， 編號i（<1=i<=n）的節點與同樣深度的滿二叉樹中編號為i的節點在二叉樹中所在位置完全相同
這是一種有些難以理解的特殊二叉樹
首先從字面上理解區分， “滿”和“完全”的差異： 滿二叉樹一定是一顆完全二叉樹， 但是完全二叉樹不一定是一顆滿二叉樹
什麼是按層序編號？
上圖中就是按照從上到下， 從左到右一次按照1， 2， 3， …， n的序號
完全二叉樹特點：
葉子結點只能出現在最下兩層
最下層的葉子結點一定集中在左部連續位置
倒數第二層， 如果有葉子結點， 一定都在右部連續位置
如果結點的度為1， 則該節點只有左孩子， 即不存在只有右子樹的情況
同樣結點數的二叉樹， 完全二叉樹的深度最小
從上面的列子中， 也給了我們一個判斷某二叉樹是否為
完全二叉樹
的辦法： 看著二叉樹的示意圖， 心中默默給每個節點按照滿二叉樹的結構逐層順序編號， 如果編號出現了空檔， 就說明不是完全二叉樹否則就是完全二叉樹
2。4 二叉樹的性質
2。4。1
第i層結點個數
若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有
2^（i-1）
（i>0）個結點
2。4。2
樹的所有最大點個數
若規定根節點的層數為1，則深度為K的二叉樹最大節點數是
2^k-1
（k>0）個結點
2。4。3
葉子結點和非葉子結點數量關係
對任何一棵二叉樹， 如果其葉結點個數為 n0， 度為2的非葉結點個數為 n2，則有
n0=n2+1
［最下一層的葉子結點個數=上面的所有非葉子結點個數+1］
2。4。4
根據結點求樹深度
具有n個節點的二叉樹的深度K為
log2^（n+1）向上取整
2。4。5
父子結點編號關係
對於具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節點從0開始編號，則對於序號為i 的結點有：
若i>0，雙親序號：（i-1）/2；
若i=0，i為根節點編號，無雙親節點
若2i+1 若2i+2 這個規律很重要， 涉及到堆排， 二叉搜尋樹需要用到這個規律 2。4。6 小練兵 設一棵完全二叉樹中總共有1000個節點， 則該二叉樹中 500 個葉子節點， 500個非葉子節點， 1個節點只有左孩子， 0個只有右孩子 。 500個葉子結點計算步驟 葉子結點總個數=第10層葉子結點個數+第9層葉子結點個數 有同學會想： 為何第9層會有葉子結點呢？ 解釋: 因為我們發現此樹共有 1000 個結點， 而滿二叉樹的話會有 2^10-1 個結點， 所以說明 第10層沒滿， 第9層一定有葉子結點 有了這個理解後再做進一步的計算 第10層全是葉子結點個數： 樹的總結點個數 - 9層及以上所有結點個數 因為是一顆完全二叉樹， 所以可以保證第9層一定是滿二叉樹 算式： 1000-（2^9-1）–>1000-511=489 現在我們還差第9層的葉子結點個數 第9層葉子結點個數： 第9層結點個數 - 第10層父節點個數 算式： 2^（9-1）-第10層父節點個數 最後的問題就是求第10層父節點個數 第10層父節點個數求法 如果結點個數n是偶數， 則其父結點個數為 n/2 如果結點個數n是奇數， 則其父結點個數n/2+1 在第一步中我們求得了第10層父節點個數， 求第10層父節點個數就是： 489/2 + 1–>245 現在可以計算第 3 步得出第9層葉子結點個數： 2^（9-1）-245–>256-245=11 現在可以計算第 1 步中的所有整棵樹的葉子結點； 第 10 層結點數 + 第 9 葉子結點數： 489+11 = 500 有了葉子結點個數， 很容易知道非葉子節點 總結點個數-葉子結點個數 ： 1000-500 由於完全二叉樹第10層結點個數為489， 為奇數， 所以一定有 1 個節點只有左孩子， 有 0 個節點只有右子樹 將一顆有 100 個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根節點編號為 1 ，則編號為 98 的節點的父節點編號為： （98-1）/2 = 48 設非空二叉樹的所有子樹中，其左子樹上的結點值均小於根結點值，而右子樹上的結點值均不小於根結點值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結果為有序序列的是： 中序遍歷 將一棵二叉樹的根結點放入佇列，然後遞迴的執行如下操作，將出隊結點所有子結點加入隊。以上操作可以實現 層序遍歷 。 n個節點的完全二叉樹，最多可以有多少層： log（n+1）上取整 2。5 二叉樹的儲存 2。5。1 順序儲存 二叉樹的順序儲存就使用一維陣列儲存二叉樹中的節點並且儲存的位置應該要能體現節點之間的邏輯關係， 比如孩子雙親， 左右兄弟節點 2。5。1。1 完全二叉樹的形式儲存 將這顆二叉樹儲存陣列中， 相應的下標對應其相等的位置 這下看出 完全二叉樹 的優越性了吧， 由於它定義的嚴格， 所以順序結構也能表現出二叉樹的結構來 2。5。1。2 一般樹的形式儲存 對於一般二叉樹而言， 層序編號不能反映邏輯關係， 但是可以按照完全二叉樹編號， 只不過把不存在的結點設施為 ‘^’ 而已。 淺色節點代表不存在 考慮一下極端情況： 又斜樹【左斜樹】 一顆深度為 k 的右斜樹， 只有 k 個節點， 卻需要分配 2^k-1 個儲存單元， 這顯然是對儲存空間的浪費。 所以順序儲存只適用於完全二叉樹 2。5。2 鏈式儲存 既然順序儲存適應性不強， 我們就要考慮鏈式儲存結構。 二叉樹每個節點最多有兩個孩子， 所以設計一個數據域和兩個指標域比較理想。 這就是二叉連結串列 孩子表示法 class Node { int val ； // 資料域 Node left ； // 左孩子的引用，常常代表左孩子為根的整棵左子樹 Node right ； // 右孩子的引用，常常代表右孩子為根的整棵右子樹 } 孩子雙親表示法主要用在在平衡樹，本文采用 孩子表示法 來構建二叉樹， 大多數的線上OJ題目也都採用的這種方法來構建二叉樹。 3。 二叉樹由淺入深解析 3。1 遍歷二叉樹 3。1。1 二叉樹遍歷原理 導言： 假設有20張100元的和2000張1元的獎券， 同時撒向了空中， 大家比賽看誰最中間的最多。 相信同學都會說： 先撿100元的。 道理非常簡單， 因為撿1張100元的等於撿100張1元的， 效率好的不是一點點？。 所以得出這樣的結論： 同樣是撿獎券， 在有限時間內， 要達到最高效率， 次序非常重要。 對於二叉樹的遍歷來講， 次序同樣顯得也很重要。 二叉樹的遍歷（traversing binary tree）： 是指從根結點出發， 按照某種次序 依次 訪問 二叉樹中的所有節點， 使得每一個節點被訪問一次且僅僅被訪問一次 這裡有兩個關鍵詞： 依次和訪問。 不同於線性結構， 最多也就是從頭至尾， 迴圈， 雙向等簡單的遍歷方式。 樹的節點之間不存在唯一的前驅和後繼關係， 在訪問一個節點後， 下一個被訪問的節點面臨著不同的選擇。 就像你人生的道路上， 高考填報志願要面臨哪個城市， 哪所大學， 具體專業等。 選擇方式不同， 遍歷的次序就完全不同 3。1。2 二叉樹遍歷方法 3。1。2。1 前序遍歷 若二叉樹為空， 則返回空操作 否則先訪問根節點， 然後前序遍歷左子樹再前序遍歷右子樹 最終訪問的結果就是： ABDGHCEIF 如下圖就是 根左右 的順序訪問二叉樹示意圖 3。1。2。2 中序遍歷 樹空， 則返回空操作 否則就從根結點開始（注意並不是先訪問根節點） 中序遍歷根節點的左子樹 然後訪問根節點 最後中序遍歷右子樹 最終訪問結果就是： GDHBAEICF 如下圖就是 左根右 的順序訪問二叉樹示意圖 3。1。2。3 後序遍歷 樹空， 則返回空操作 否先從左到右線葉子結點後節點的方式遍歷訪問左右子樹， 最後訪問根節點 最終訪問結果是： GHDBIEFCA 如下圖就是 左右根 的順序訪問二叉樹示意圖 3。1。2。4 層序遍歷 若樹為空， 返回空操作 否則從樹的第一層， 也就是根節點開始訪問 從上而下逐層遍歷 在同一層中， 按左到右的順序對節點逐個訪問 最終訪問結果就是： ABCDEFGHI 3。1。3 二叉樹遍歷演算法 假設我們有以下一顆二叉樹T, 用連結串列結構儲存 3。1。3。1 前序遍歷演算法 根左右 OJ題目連結 遞迴前序遍歷 private static void preOrderTraversal （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { System 。 out 。 print （ root 。 val + “ ” ） ； preOrder （ root 。 left ） ； preOrder （ root 。 right ） ； } } private static List < String > preOrderTraversal （ BinaryTreeNode root ） { List < String > result = new ArrayList < > （ ） ； if （ root == null ） { return result ； } else { result 。 add （ root 。 val ） ； result 。 addAll （ preOrderTraversal （ root 。 left ） ） ； result 。 addAll （ preOrderTraversal （ root 。 right ） ） ； return result ； } } A B D H K E C F I G J 演示 遞迴前序遍歷 步驟 呼叫 preOrderTraversal（BinaryTreeNode root） ， root 根節點不為空， 所以執行 System。out。print（root。val + “ ”）； 列印字母 A 呼叫 preOrderTraversal（root。left） ， 訪問了 A 節點的左孩子， 不為 null， 執行 System。out。print（root。val + “ ”）； 列印字母 B 再次遞迴呼叫 preOrderTraversal（root。left） ， 訪問了 B 節點的左孩子， 不為 null， 執行 System。out。print（root。val + “ ”）； 列印字母 D 再次遞迴呼叫 preOrderTraversal（root。left） ， 訪問了 D 節點的左孩子， 不為 null， 執行 System。out。print（root。val + “ ”）； 列印字母 H 再次遞迴呼叫 preOrderTraversal（root。left） ， 訪問 H 節點的左孩子， 此時因為 H 節點無左孩子， 所以 root == null 返回此函， 此時遞迴呼叫 preOrderTraversal（root。right）； 訪問了 H 節點的右孩子， 執行 System。out。print（root。val + “ ”）； 列印字母 K 再次遞迴呼叫 preOrderTraversal（root。left） ， 訪問 K 節點的左孩子， 返回 呼叫 preOrderTraversal（root。right） ， 訪問了 K 節點的右孩子， 也是 null， 返回。於是函式執行完畢。 返回到上一級遞迴的函式（即列印 H 節點時的函式）， 也執行完畢。［根左右都已經遍歷完， 所以執行完畢］ 返回列印 D 節點時的函式， 呼叫 preOrderTraversal（root。ri ght） 訪問 D 節點的右孩子， 不存在 返回到 B 節點， 呼叫 preOrderTraversal（root。right） ， 訪問 B 節點的右孩子， 列印字母 E 由於節點 E 沒有左右孩子， 返回列印節點 B 時的遞迴函式， 遞迴執行完畢。 返回到最初的 preOrderTraversal（root） ， 呼叫 preOrderTraversal（root。right） ， 訪問 A 節點的右孩子， 列印字母 C 之後類似前面的遞迴呼叫， 一次繼續列印F， I， G， j 知道了遞迴的程式碼如何執行, 那我們再看看非遞迴實現前序遍歷 /* 非遞迴 1。先建立一個棧 2。根節點放進棧裡 3。迴圈取棧頂元素 4。出棧並訪問這個元素值域 5。把當前元素的右子樹入棧， 再左子樹入棧【因為先列印左子樹後列印右子樹所以對於棧而言應該先入右子樹再入左子樹】 */ private static void preOrderTraversalNo （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { Stack < BinaryTreeNode > stack = new Stack < > （ ） ； stack 。 push （ root ） ； while （ ！ stack 。 empty （ ） ） { BinaryTreeNode top = stack 。 pop （ ） ； System 。 out 。 print （ top 。 val + “ ” ） ； if （ top 。 right ！= null ） { stack 。 push （ top 。 right ） ； } if （ top 。 left ！= null ） { stack 。 push （ top 。 left ） ； } } } } A B D H K E C F I G J 演示 迭代前序遍歷 步驟 非遞迴思路很巧妙的利用了棧的先進後出特性進行前序遍歷 3。1。3。2 中序遍歷演算法 左根右 OJ題目連結 遞迴中序遍歷 private static void inOrderTraversal （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { preOrder （ root 。 left ） ； System 。 out 。 print （ root 。 val + “ ” ） ； preOrder （ root 。 right ） ； } } H K D B E A I F C G J 演示 遞迴中序遍歷 步驟 呼叫 inOrderTraversal（BinaryTreeNode root） ， root 的根節點 A 不為 null， 於是呼叫 inOrderTraversal（root。left） ， 訪問節點 B ； B 不為空， 繼續呼叫 inOrderTraversal（root。left） ， 訪問節點 D ； D 不為空， 繼續呼叫 inOrderTraversal（root。left） ， 訪問節點 H ； H 不為空， 繼續呼叫 inOrderTraversal（root。left） ， 訪問節點 H的左孩子 ； 為空， 返回。 列印當前節點 H 然後呼叫 inOrderTraversal（root。right） ， 訪問 H 節點的右節點 K 。因為 K 無左孩子， 所以列印 K 因為 K 沒有右節點， 所以返回。 列印 H 節點的函式執行完畢， 返回。 列印字母 D 節點 D 沒有右孩子， 所以返回。 列印 B 呼叫 inOrderTraversal（root。right） ， 訪問 B 節點的右節點 E ， 因為 E 沒有左孩子， 所以列印 E 節點 E 無右孩子， 返滬。 列印 B 的函式執行完畢， 返回到了我們最初執行 inOrderTraversal（root） 的地方， 列印字母 A 呼叫 inOrderTraversal（root。right） ， 訪問 A 節點的右孩子C，再遞迴訪問 C 的左孩子 F ， F 的左孩子 I ， 因為 I 無右孩子， 所以列印 I 。 之後分別列印 F, C, G, J 迭代中序遍歷 /* 1。先建立一個棧 2。根節點入棧 3。迴圈取棧頂元素 4。左子樹 集體入棧後再入右子樹 5。最外層 while 迴圈判斷需要留意。因為 cur= cur。right 會導致 cur == nulll， 因此在加入一個 ！stack。empty（） 的判斷 */ private static void inOrderTraversalNo （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { Stack < BinaryTreeNode > stack = new Stack < > （ ） ； BinaryTreeNode cur = root ； while （ cur ！= null || ！ stack 。 empty （ ） ） { while （ cur ！= null ） { stack 。 push （ cur ） ； cur = cur 。 left ； } cur = stack 。 pop （ ） ； System 。 out 。 print （ cur 。 val + “ ” ） ； cur = cur 。 right ； } } } H K D B E A I F C G J 演示 迭代中序遍歷 步驟 3。1。3。2 後序遍歷演算法 左右根 OJ題目連結 遞迴後序遍歷 /* OJ： 透過 */ class Solution { List < Integer > list = new ArrayList < > （ ） ； public List < Integer > postorderTraversal （ TreeNode root ） { if （ root == null ） { return list ； } else { postorderTraversal （ root 。 left ） ； postorderTraversal （ root 。 right ） ； list 。 add （ root 。 val ） ； return list ； } } } private static void postOrderTraversal （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { postOrderTraversal （ root 。 left ） ； postOrderTraversal （ root 。 right ） ； System 。 out 。 print （ root 。 val + “ ” ） ； } } 演示 遞迴後序遍歷 步驟 後序遍歷先遞迴左子樹， 由根節點 A->B->D->H， 節點 H 無左孩子， 再檢視 H 的右孩子 K ， 因為節點 K 無左右孩子， 所以 列印 K 。 K 列印執行完之後返回到執行列印 H 的程式 System。out。print（root。val + “ ”）； ， 列印 H 節點 後續的分析步驟和都是看 返回的節點有無左右子樹是否遍歷完了： 遍歷完了就輸出根節點， 否則就繼續遍歷 迭代後序遍歷 /* 和中序遍歷類似 1。外層迴圈依舊需要加上 ！stack。empty（）來帶動迴圈 2。被列印完的節點置為 null， 並且判斷該節點是否被列印過 3。判斷 超時 */ private static void postOrderTraversalNo （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { Stack < BinaryTreeNode > stack = new Stack < > （ ） ； BinaryTreeNode cur = root ； BinaryTreeNode prev = null ； while （ cur ！= null || ！ stack 。 empty （ ） ） { while （ cur ！= null ） { stack 。 push （ cur ） ； cur = cur 。 left ； } cur = stack 。 peek （ ） ； if （ cur 。 right == null || cur 。 right == prev ） { stack 。 pop （ ） ； System 。 out 。 print （ cur 。 val + “ ” ） ； prev = cur ； cur = null ； } else { cur = cur 。 right ； } } } } K H D E B I F J G C A 演示 迭代後序遍歷 步驟 3。1。3。2 層序遍歷演算法 上至下， 左至右 OJ題目連結 class Solution { public List < List < Integer > > levelOrder （ TreeNode root ） { // 1。返回空盒子 List < List < Integer > > list = new ArrayList < > （ ） ； if （ root == null ） { return list ； } else { // 2。佇列村粗 Queue < TreeNode > queue = new LinkedList < > （ ） ； queue 。 offer （ root ） ； while （ ！ queue 。 isEmpty （ ） ） { int size = queue 。 size （ ） ； List < Integer > tmp = new ArrayList < > （ ） ； while （ size —— > 0 ） { TreeNode top = queue 。 poll （ ） ； tmp 。 add （ top 。 val ） ； if （ top 。 left ！= null ） { queue 。 offer （ top 。 left ） ； } if （ top 。 right ！= null ） { queue 。 offer （ top 。 right ） ； } } list 。 add （ tmp ） ； } return list ； } } } ［ ［ A ］ ， ［ B ， C ］ ， ［ D ， E ， F ， G ］ ， ［ H ， I ， J ］ ， ［ K ］ ］ 演示 OJ練習題中的程式碼執行 步驟 正常的層序輸出 /* 1。先建立一個佇列 2。把根節點放在佇列 3。迴圈取佇列元素全部 4。內部 list 新增 當前元素 4。再把當前元素的左子樹入佇列， 再入右子樹 5。大的 ret 新增每次新添元素後的 list */ private static void levelOrder （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { Queue < BinaryTreeNode > queue = new LinkedList < > （ ） ； queue 。 offer （ root ） ； while （ ！ queue 。 isEmpty （ ） ） { BinaryTreeNode top = queue 。 poll （ ） ； System 。 out 。 print （ top 。 val + “ ” ） ； if （ top 。 left ！= null ） { queue 。 offer （ top 。 left ） ； } if （ top 。 right ！= null ） { queue 。 offer （ top 。 right ） ； } } } } A B C D E F G H I J K 3。2 二叉樹建立問題 3。2。1 前序中序構建二叉樹 OJ題目連結 class Solution { private int findInorderIndex （ int ［ ］ inorder ， int inbegin ， int inend ， int key ） { for （ int i = inbegin ； i <= inend ； ++ i ） { if （ inorder ［ i ］ == key ） { return i ； } } return - 1 ； } private TreeNode buildTreeChild （ int ［ ］ preorder ， int ［ ］ inorder ， int inbegin ， int inend ） { if （ inbegin > inend ） { return null ； } else { TreeNode root = new TreeNode （ preorder ［ preIndex ++ ］ ） ； int rootIndex = findInorderIndex （ inorder ， inbegin ， inend ， root 。 val ） ； root 。 left = buildTreeChild （ preorder ， inorder ， inbegin ， rootIndex - 1 ） ； root 。 right = buildTreeChild （ preorder ， inorder ， rootIndex + 1 ， inend ） ； return root ； } } private int preIndex = 0 ； public TreeNode buildTree （ int ［ ］ preorder ， int ［ ］ inorder ） { if （ preorder == null || inorder == null ） { return null ； } else { return buildTreeChild （ preorder ， inorder ， 0 ， inorder 。 length - 1 ） ； } } } 其時建立二叉樹也是利用了遞迴的原理。 只不過在當初列印節點的程式碼換成了生成節點， 給節點賦值的操作而已。 前序遍歷的第一個節點一定是 根節點 ， 所以我們在中序遍歷中劃分根節點的左右子樹， 然後遞迴找根節點再劃分左右子樹， 遞迴的終止條件是 區間的左一定要大於區間的右 程式碼思路: 判斷前序或中序是否有一個為 null 【特殊情況處理】 利用 buildTreeChild 函式返回根節點 先構造根節點， 再遞迴構建左子樹和右子樹 所有遞迴完之後返回最後的 root 就是樹的根節點 演示圖 第一查詢的是 preorder［preIndex］ 的根節點【preIndex值為0】 由於第二次劃分的時候， 新的 inend 是 rootIndex-1 所以導致的 if（inbegin>inend） return； 程式返回執行 root。right = buildTreeChild（preorder， inorder， rootIndex+1， inend）； 第三次劃分 綜合 3。2。2 中序後序構建二叉樹 OJ題目連結 class Solution { private int postIndex = 0 ； private int findInorderIndex （ int ［ ］ inorder ， int inbegin ， int inend ， int key ） { for （ int i = inbegin ； i <= inend ； ++ i ） { if （ inorder ［ i ］ == key ） { return i ； } } return - 1 ； } private TreeNode buildTreeChild （ int ［ ］ inorder ， int ［ ］ postorder ， int inbegin ， int inend ） { if （ inbegin > inend ） { return null ； } else { TreeNode root = new TreeNode （ postorder ［ postIndex —— ］ ） ； int rootIndex = findInorderIndex （ inorder ， inbegin ， inend ， root 。 val ） ； root 。 right = buildTreeChild （ inorder ， postorder ， rootIndex + 1 ， inend ） ； root 。 left = buildTreeChild （ inorder ， postorder ， inbegin ， rootIndex - 1 ） ； return root ； } } public TreeNode buildTree （ int ［ ］ inorder ， int ［ ］ postorder ） { if （ inorder == null || postorder == null ） { return null ； } else { postIndex = postorder 。 length - 1 ； return buildTreeChild （ inorder ， postorder ， 0 ， postIndex ） ； } } } 後序遍歷和前序變一樣想法一樣， 但是應該注意順序【後序遍歷最後一是根， 而前序遍歷第一個就是根】 演示圖 因為從後往前看的話， 根節點過來就是右節點， 所以先構建右子樹在構建左子樹。 遍歷遞迴思路和上述一樣， 這裡就不多述 總結出一個二叉樹的性質 已知前序遍歷和中序遍歷， 可以確定唯一的一顆二叉樹 已知中序遍歷和後序遍歷， 可以確定唯一的一顆二叉樹 思考: 已知前序遍歷和後序遍歷能否構建唯一的一顆二叉樹 不能， 原因很簡單。 比如一棵二叉樹前序遍歷是 ABC 後序遍歷是 CBA 我們可以確定根節點是 A 但不能確定 A 的左右子樹。 這棵樹就有如下的四種可能 3。2。3 根據二叉樹建立字串 OJ題目連結 解法1 先處理左子樹， 再處理右子樹 按照題目要求進行一個一個新增括號 class Solution { private void tree2strChild （ TreeNode root ， StringBuffer stringBuffer ） { if （ root == null ） { return ； } else { stringBuffer 。 append （ root 。 val ） ； // 1。處理左子樹 if （ root 。 left == null ） { if （ root 。 right == null ） { return ； } else { stringBuffer 。 append （ “（）” ） ； } } else { stringBuffer 。 append （ “（” ） ； tree2strChild （ root 。 left ， stringBuffer ） ； stringBuffer 。 append （ “）” ） ； } // 2。處理右子樹 if （ root 。 right == null ） { return ； } else { stringBuffer 。 append （ “（” ） ； tree2strChild （ root 。 right ， stringBuffer ） ； stringBuffer 。 append （ “）” ） ； } } } public String tree2str （ TreeNode root ） { if （ root == null ） { return “” ； } else { StringBuffer stringBuffer = new StringBuffer （ ） ； tree2strChild （ root ， stringBuffer ） ； return stringBuffer 。 toString （ ） ； } } } 解法2 程式碼少， 容易理解， 但執行效率低 遞迴前序遍歷的形式新增括號 新增完畢之後再刪除第一個和最後一個括號即可 class Solution { private StringBuffer stringBuffer = null ； private void tree2strChild （ TreeNode root ） { if （ root == null ） { return ； } else { stringBuffer 。 append （ “（” + root 。 val ） ； tree2strChild （ root 。 left ） ； if （ root 。 left == null && root 。 right ！= null ） { stringBuffer 。 append （ “（）” ） ； } tree2strChild （ root 。 right ） ； stringBuffer 。 append （ “）” ） ； } } public String tree2str （ TreeNode root ） { if （ root == null ） { return “” ； } else { stringBuffer = new StringBuffer （ ） ； tree2strChild （ root ） ； stringBuffer 。 deleteCharAt （ 0 ） ； stringBuffer 。 deleteCharAt （ stringBuffer 。 length （ ） - 1 ） ； return stringBuffer 。 toString （ ） ； } } } 3。2。4 前序遍歷字串構建二叉樹 OJ題目連結 import java 。 util 。 Scanner ； import java 。 util 。 Stack ； class TreeNode { char val ； TreeNode left ； TreeNode right ； TreeNode （ char val ） { this 。 val = val ； } } public class Main { // 1。採用的是迭代的方式進行中序遍歷 private static void inOrderTraversal （ TreeNode root ） { if （ root == null ） { return ； } else { Stack < TreeNode > stack = new Stack < > （ ） ； TreeNode cur = root ； while （ cur ！= null || ！ stack 。 empty （ ） ） { // 2。 左子樹集體入棧 while （ cur ！= null ） { stack 。 push （ cur ） ； cur = cur 。 left ； } cur = stack 。 pop （ ） ； System 。 out 。 print （ cur 。 val + “ ” ） ； cur = cur 。 right ； } } } private static int index = 0 ； // 記錄列印的字串下標， 因為是遞迴， 所以應該使用全域性變數而不是區域性變數 private static TreeNode createTree （ String str ） { if （ str == null ） { return null ； } else { TreeNode root = null ； // 1。越過空節點 if （ str 。 charAt （ index ） == ‘#’ ） { ++ index ； } else { // 2。 按照前序根左右的形式遞迴構建二叉樹 root = new TreeNode （ str 。 charAt （ index ++ ） ） ； root 。 left = createTree （ str ） ； root 。 right = createTree （ str ） ； } return root ； } } public static void main （ String ［ ］ args ） { Scanner scanner = new Scanner （ System 。 in ） ； while （ scanner 。 hasNext （ ） ） { String str = scanner 。 next （ ） ； TreeNode root = createTree （ str ） ； inOrderTraversal （ root ） ； System 。 out 。 println （ ） ； } } } 3。2。5 合併二叉樹 OJ題目練習 class Solution { public TreeNode mergeTrees （ TreeNode root1 ， TreeNode root2 ） { // 1。如果某個節點為null， 則返回另一個節點 if （ root1 == null ） { return root2 ； } else if （ root2 == null ） { return root1 ； } else { // 2。如果兩個節點都不為null， 則開始合併二叉樹 TreeNode root = new TreeNode （ root1 。 val + root2 。 val ） ； root 。 left = mergeTrees （ root1 。 left ， root2 。 left ） ； root 。 right = mergeTrees （ root1 。 right ， root2 。 right ） ； return root ； } } } 3。2。6 遞增二叉樹 OJ練習題目 class Solution { private TreeNode cur = null ； private void inOrderTraversal （ TreeNode root ） { if （ root == null ） { return ； } else { //1。左 inOrderTraversal （ root 。 left ） ； // 2。根 cur 。 right = root ； root 。 left = // 3。右 inOrderTraversal （ root 。 right ） ； } } public TreeNode increasingBST （ TreeNode root ） { if （ root == null ） { return null ； } else { // 1。傀儡節點用來儲存cur節點的位置用於返回 TreeNode newRoot = new TreeNode （ - 1 ） ； // 2。移動節點 cur = newRoot ； inOrderTraversal （ root ） ； return newRoot 。 right ； } } } 3。3 經典題目解析 3。3。1 結點個數 /* 求結點個數 遍歷思路： 遞迴每次遍歷就自增 1［線上 OJ 可能會翻車： 先拿一個小樹呼叫 gerSize1 方法， 然後再拿一個大的樹來呼叫 getSize1］ 子問題思路： return 1+func（）。。。自帶返回值 */ private static int size = 0 ； private static void getSize1 （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { ++ size ； getSize1 （ root 。 left ） ； getSize1 （ root 。 right ） ； } } private static int getSize2 （ BinaryTreeNode root ） { if （ root == null ） { return 0 ； } else { return 1 + getSize2 （ root 。 left ） + getSize2 （ root 。 right ） ； } } 3。3。2 葉子結點個數 /* 求葉子結點個數 遍歷思路： 遞迴遍歷 子問題思路： return 1+func（）。。。 */ private static int leaftSize = 0 ； private static void getLeafSize1 （ BinaryTreeNode root ） { if （ root == null ） { return ； } else { if （ root 。 left == null && root 。 right == null ） { ++ leaftSize ； } else { getLeafSize1 （ root 。 left ） ； getLeafSize1 （ root 。 right ） ； } } } private static int getLeafSize2 （ BinaryTreeNode root ） { if （ root == null ） { return 0 ； } else { if （ root 。 left == null && root 。 right == null ） { return 1 ； } else { return getLeafSize2 （ root 。 left ） + getLeafSize2 （ root 。 right ） ； } } } 3。3。3 第k層結點個數 private static int getKLevelSize （ BinaryTreeNode root ， int k ） { if （ root == null || k < 1 ） { return 0 ； } else { if （ k == 1 ） { return 1 ； } else { return getKLevelSize （ root 。 left ， k - 1 ） + getKLevelSize （ root 。 right ， k - 1 ） ； } } } 3。3。4 查詢 val 所在結點 private static BinaryTreeNode find （ BinaryTreeNode root ， String val ） { if （ root == null ） { return null ； } else { if （ root 。 val 。 equals （ val ） ） { return root ； } else { BinaryTreeNode ret = find （ root 。 left ， val ） ； if （ ret ！= null && ret 。 val 。 equals （ val ） ） { return ret ； } ret = find （ root 。 right ， val ） ； if （ ret ！= null && ret 。 val 。 equals （ val ） ） { return ret ； } return null ； } } } 3。3。5 相同的樹 OJ題目練習 class Solution { public boolean isSameTree （ TreeNode p ， TreeNode q ） { // 1。都為null： 說明之前的節點和節點值相等， 所以相等； 或者兩個空節點也是相等的 if （ p == null && q == null ） { return true ； // 2。某個節點遍歷完了但另一個節點不為null， 所以是false } else if （ p == null || q == null ） { return false ； } else { // 3節點值不相等就 false if （ p 。 val ！= q 。 val ） { return false ； } else { // 4。 遞迴進行下一次比較 return isSameTree （ p 。 left ， q 。 left ） && isSameTree （ p 。 right ， q 。 right ） ； } } } 3。3。6 另一棵樹子樹 OJ題目練習 class Solution { public boolean isSameTree （ TreeNode p ， TreeNode q ） { // 1。都為null： 說明之前的節點和節點值相等， 所以相等； 或者兩個空節點也是相等的 if （ p == null && q == null ） { return true ； // 2。某個節點遍歷完了但另一個節點不為null， 所以是false } else if （ p == null || q == null ） { return false ； } else { // 3節點值不相等就 false if （ p 。 val ！= q 。 val ） { return false ； } else { // 4。 遞迴進行下一次比較 return isSameTree （ p 。 left ， q 。 left ） && isSameTree （ p 。 right ， q 。 right ） ； } } } public boolean isSubtree （ TreeNode root ， TreeNode subRoot ） { // 1。兩個 nullnull 則是子樹； 遍歷到了葉子結點的子樹【雖然不存在】， 說明之前遍歷的都是相等的 if （ root == null && subRoot == null ） { return true ； } else if （ root == null && subRoot ！= null || root ！= null && subRoot == null ） { return false ； } else { // 1。如果兩個節點不為空， 且相等， 則是子樹 if （ isSameTree （ root ， subRoot ） ） { return true ； // 2。遞迴判斷是否為子樹 } else if （ isSubtree （ root 。 left ， subRoot ） ） { return true ； } else if （ isSubtree （ root 。 right ， subRoot ） ） { return true ； } else { return false ； } } } } 3。3。7 二叉樹最大深度 OJ練習題目 class Solution { public int maxDepth （ TreeNode root ） { if （ root == null ） { return 0 ； } else { // 1。計算左子樹的高度 int left = maxDepth （ root 。 left ） + 1 ； // 2。計算右子樹的高度 int right = maxDepth （ root 。 right ） + 1 ； if （ left > right ） { return left ； } else { return right ； } } } } 3。3。8 平衡二叉樹 OJ練習題目 class Solution { private int maxDepth （ TreeNode root ） { if （ root == null ） { return 0 ； } else { int left = 1 + maxDepth （ root 。 left ） ； int right = 1 + maxDepth （ root 。 right ） ； return left > right ？ left ： right ； } } public boolean isBalanced （ TreeNode root ） { if （ root == null ） { return true ； } else { int left = maxDepth （ root 。 left ） ； int right = maxDepth （ root 。 right ） ； if （ Math 。 abs （ left - right ） > 1 ） { return false ； } else { return isBalanced （ root 。 left ） && isBalanced （ root 。 right ） ； } } } } // 1。 最佳化後的程式碼： 邊求高度邊計算左右子樹高度差， 不用遞迴兩次 class Solution { private int maxDepth （ TreeNode root ） { if （ root == null ） { return 0 ； } else { int left = maxDepth （ root 。 left ） ； int right = maxDepth （ root 。 right ） ； if （ left >= 0 && right >= 0 && Math 。 abs （ left - right ） <= 1 ） { return Math 。 max （ left ， right ） + 1 ； } else { return - 1 ； } } } public boolean isBalanced （ TreeNode root ） { return maxDepth （ root ） > - 1 ； } } 3。3。9 對稱二叉樹 OJ練習題目 class Solution { private boolean isSameTree （ TreeNode leftTree ， TreeNode rightTree ） { if （ leftTree == null && rightTree == null ） { return true ； } else if （ leftTree ！= null && rightTree == null || leftTree == null && rightTree ！= null ） { return false ； } else { if （ leftTree 。 val ！= rightTree 。 val ） { return false ； } else { /* 1。 之前的判斷步驟和 比較二叉樹是否相同 有點類似 2。 之後應該比較 左樹的左 和 右樹的右； 左樹的右 和 右樹的左 是否相同 */ return isSameTree （ leftTree 。 left ， rightTree 。 right ） && isSameTree （ leftTree 。 right ， rightTree 。 left ） ； } } } public boolean isSymmetric （ TreeNode root ） { if （ root == null ） { return true ； } else { return isSameTree （ root 。 left ， root 。 right ） ； } } } 3。3。10 二叉樹的完全性檢驗 OJ題目練習 利用佇列特性進行全部入佇列(包含 null 節點)再進行出佇列判斷 /* 1。 當遇到 null 節點時候說明已經遍歷所有完全二叉樹就退出 2。 在佇列末尾慢慢彈出元素， 如果彈出了不為 null 則說明不是一個完全二叉樹 */ class Solution { public boolean isCompleteTree （ TreeNode root ） { if （ root == null ） { return true ； } else { Queue < TreeNode > queue = new LinkedList < > （ ） ； queue 。 offer （ root ） ； // 1。直到遇到 null 節點就停止入佇列 while （ ！ queue 。 isEmpty （ ） ） { TreeNode top = queue 。 poll （ ） ； if （ top ！= null ） { queue 。 offer （ top 。 left ） ； // 程式走到葉子結點， 則會把 null 節點也帶入佇列， 後續的 peekpeek 探測的時候如果遇到了不為 null 的節點的話就代表在遇到 null 節點之後還有其它葉子結點， 此時一定不是完全二叉樹 queue 。 offer （ top 。 right ） ； } else { break ； } } //程式執行到這兒， 說明佇列中已經儲存所有的節點 // 2。節點出佇列， peek探測元素是否為 null while （ ！ queue 。 isEmpty （ ） ） { TreeNode top = queue 。 peek （ ） ； if （ top ！= null ） { return false ； } else { queue 。 poll （ ） ； //出佇列 } } return true ； } } } 最佳化: 簡單高效的透過對比節點數和下標數判斷 class Solution { private int n = 0 ， p = 0 ； private boolean dfs （ TreeNode root ， int k ） { if （ root == null ） { return true ； // 1。節點遍歷完畢 } else if （ k > 100 ） { return false ； // 2。題目提示： 樹中將會有 1 到 100 個結點 } else { ++ n ； // 3。每遍歷一次， 結點個數就自增一， 記錄當前節點下標 p = Math 。 max （ p ， k ） ； // 4。因為有左右子樹， 所以每次應該選取最大下標才可 return dfs （ root 。 left ， 2 * k ） && dfs （ root 。 right ， 2 * k + 1 ） ； } } public boolean isCompleteTree （ TreeNode root ） { if （ root == null ） { return true ； } else { if （ ！ dfs （ root ， 1 ） ） { return false ； // 1。 超過 100 節點就返回 false } else { return n == p ； // 2。未超過 100 節點， 判斷節點數和最大下標數是否相等 } } } } 3。3。11 二叉樹最近公公祖先 OJ題目練習 /* left == null， right == null： return null left ！= null， right ！= null： return root left == null， right ！= null： return right left ！= null， right == null： return left */ class Solution { public TreeNode lowestCommonAncestor （ TreeNode root ， TreeNode p ， TreeNode q ） { if （ root == null || root == p || root == q ） { return root ； } else { TreeNode left = lowestCommonAncestor （ root 。 left ， p ， q ） ； TreeNode right = lowestCommonAncestor （ root 。 right ， p ， q ） ； if （ left == null && right == null ） { return null ； } else if （ left ！= null && right == null ） { return left ； } else if （ left == null && right ！= null ） { return right ； } else { return root ； } } } } 3。3。12 二叉樹最大寬度 OJ題目練習 class Solution { public int widthOfBinaryTree （ TreeNode root ） { if （ root == null ） { return 0 ； } else { LinkedList < TreeNode > queue = new LinkedList < > （ ） ； queue 。 offer （ root ） ； int max_width = 0 ； while （ ！ queue 。 isEmpty （ ） ） { int cur_width = queue 。 getLast （ ） 。 val - queue 。 getFirst （ ） 。 val + 1 ； // 1。利用結點的值域記錄當前佇列寬度 // 2。頭節點的左右子樹入佇列， 為下一次寬度計算做準備 int count = queue 。 size （ ） ； // 3。佇列大小時刻變化著的， 我們應該保留入佇列之前的佇列大小 for （ int i = 0 ； i < count ； ++ i ） { TreeNode top = queue 。 poll （ ） ； // 4。出佇列元素且保留， 為後續左右子樹入佇列做鋪墊 if （ top 。 left ！= null ） { queue 。 offer （ top 。 left ） ； top 。 left 。 val = top 。 val << 1 ； // 5。依據的是二叉樹的性質5——左孩子：2*i 根：i 右孩子： 2*i+1 } if （ top 。 right ！= null ） { queue 。 offer （ top 。 right ） ； top 。 right 。 val = （ top 。 val << 1 ） + 1 ； } } if （ max_width < cur_width ） { max_width = cur_width ； } } return max_width ； } } } 其它語言要考慮下方提示： 整形溢位問題 3。4。 特殊的二叉樹問題 3。4。1 搜尋二叉樹 static class BinaryTreeNode { // 鍵值對的形式儲存 int key ； int value ； BinaryTreeNode left ； BinaryTreeNode right ； public BinaryTreeNode （ int key ， int value ） { this 。 key = key ； this 。 value = value ； } } // root： 表示樹的根節點， 空樹就是用 null 來表示 private BinaryTreeNode root = null ； //查詢： 根據 Key 找 Value private Integer search （ int key ） { BinaryTreeNode cur = root ； while （ cur ！= null ） { if （ key < cur 。 key ） { cur = cur 。 left ； } else if （ key > cur 。 key ） { cur = cur 。 right ； } else { return key ； } } return null ； } // 插入 private void insert （ int key ， int value ） { if （ root == null ） { root = new BinaryTreeNode （ key ， value ） ； } else { BinaryTreeNode cur = root ； BinaryTreeNode parend = null ； while （ cur ！= null ） { parend = cur ； if （ key < cur 。 key ） { cur = cur 。 left ； } else if （ key > cur 。 key ） { cur = cur 。 right ； } else { return ； // 二叉搜尋樹不存在相等， 如果相等也沒必要賦值 } } // 程式執行到這兒， 說明 parent 已經是 cur 的父節點， 修改父節點即可 if （ key < parend 。 key ） { parend 。 left = new BinaryTreeNode （ key ， value ） ； } else { parend 。 right = new BinaryTreeNode （ key ， value ） ； } } } // 刪除： 按照 key 刪除 private void remove （ int key ） { // 1。先查詢 key 對應的位置 BinaryTreeNode cur = root ； BinaryTreeNode parent = null ； while （ cur ！= null ） { parent = cur ； if （ key < cur 。 key ） { cur = cur 。 left ； } else if （ key > cur 。 key ） { cur = cur 。 right ； } else { /* 2。核心刪除 考慮當前 cur。left 為空 是否為根節點 root 是： 連結右子樹 否： 接著判斷當前刪除的子節點 cur 是其父節點 parent 節點的左右子樹關係 考慮當前 cur。right 為空 緊接 cur。left 根節點判斷一樣的思路 考慮當前 cur。right 和 cur。left 都不為空 移形換影刪除 */ if （ cur 。 left == null ） { if （ cur == root ） { root = cur 。 right ； } else if （ cur == parent 。 left ） { parent 。 left = cur 。 right ； } else if （ cur == parent 。 right ） { parent 。 right = cur 。 right ； } } else if （ cur 。 right == null ） { if （ cur == root ） { root = cur 。 left ； } else if （ cur == parent 。 left ） { parent 。 left = cur 。 left ； } else if （ cur == parent 。 right ） { parent 。 right = cur 。 left ； } } else { // 具體移形換影步驟 // 1。右子樹找最小值， 並記錄其父節點 BinaryTreeNode targetParent = cur ； BinaryTreeNode target = cur 。 right ； while （ target 。 left ！= null ） { // 最小值特點是： 左子樹為空 targetParent = target ； target = target 。 left ； } // 2。程式執行到這兒： targetParent 是 target 父節點； target 是右子樹中最小值 // 3。就把 替罪羊target 節點的值賦值給刪除節點 cur 。 key = target 。 key ； cur 。 value = target 。 value ； // 4。斷開末尾 最小值節點 的關係， 建立新的關係 if （ target == targetParent 。 left ） { targetParent 。 left = target 。 right ； // 最小值左節點為 null } else if （ target == targetParent 。 right ） { targetParent 。 right = target 。 right ； } } } } } 3。4。2 赫夫曼樹及其應用 3。4。1。 赫夫曼樹 什麼是 哈夫曼樹 哈夫曼樹的目的是為了字串的壓縮， 我們經常用的 zip， tar， ara…等等壓縮都是基於 哈夫曼樹的原理 舉箇中小學通用的評分標準 if （ a < 60 ） { b = “不及格” ； } else if （ a < 70 ） { b = “及格” ； } else if （ a < 80 ） { b = “中等” ； } else if （ a < 90 ） { b = “良好” ； } else { b = “優秀” ； } 粗看沒什麼問題， 結果是對的。 一張好的試卷應該讓學生成績大部分處於 中等 或 良好 範圍， 優秀 和 不及格 應該很少才對。 而上面的程式， 就需要讓所有的成績判斷是否及格， 再逐級而上得到結果。 資料量大的時候， 演算法效率很低下 實際生活中學生成績分佈規律如下表 那麼 70 分以上大約佔總數80%的成績都需要經過 3 次以上的判斷才可以得到結果， 這顯然不合理。 仔細觀察發現： 中等成績（70~79）比例最高， 其次是良好成績， 不及格所佔比例最少。 對上述的二叉樹重新分配如下（有點像搜尋二叉樹， 其實並不是的， 仔細往後面的文章看）： 3。4。2。赫夫曼樹定義與原理 把兩顆二叉樹簡化成葉子結點帶權的二叉樹【A： 不及格， B： ，及格C： 中等，D：良好， E：優秀】 從樹中一個節點到另一個節點之間的分支結構狗曾兩個雞誒但之間的路徑， 路徑上的分支樹木稱作路徑長度 二叉樹a中根節點到D節點路徑長度就是4， 二叉樹b中根節點到D節點長度就是2 二叉樹a總長度： 1+1+2+2+3+3+4+4=20 二叉樹b總長度： 1+1+2+2+2+2+3+3=16 如果考慮帶權的節點 ： 該節點到樹根之間的路徑長度與節點上權的乘積。 樹的帶權路徑長度作為作為樹中所有葉子結點的帶權路徑長度的之和， 用 WPL 來表示。 其中最小的 WPL 的樹稱為 赫夫曼樹 。 二叉樹a WPL： 5 * 1 + 15 * 2 + 40 * 2 + 30 * 4 + 10 * 4 = = 315 二叉樹b WPL： 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220 這樣的結果意味著如果有 1_0000 個學生的百分制資料計算五級分製成績, 二叉樹a需要計算31500次比較, 二叉樹b需要2200次比較. 差不多少了1/3的量, 效能上提高不是一點點 該如何構建赫夫曼樹呢？ 先把有權值的葉子結點按照從小到大的順序排列成一個有序序列［A5， E10， B15， D30， C40］ 取頭兩個最小全值的節點作為一個新節點 N1 的兩個位元組點， A 是 N1 左子樹， E 是 N1 右子樹。 注意左右子樹大小關係 將 N1 替換 A 與 E， 插入有序序列中， 保持從小到大排列［N1 15， B15， D30， C40］ 重複步驟2。 將 N1 與 B 作為一個新節點 N2 的兩個位元組點 重複步驟3的序列替換序列最小值， 再重複步驟2生成新的節點… 最終效果： WPL=40 * 1 + 30 * 2 + 15 * 3 + 10 * 4 + 5 * 4 = 205， 比搜尋二叉樹還少了15， 因此這才是最優的赫夫曼樹 3。4。3 赫夫曼編碼 赫夫曼樹更大作用是為解決當年遠距離通訊（主要是電報）的資料傳輸的最最佳化問題。 比如有一段文字內容為 “BADCADFEED” 要網路傳輸給別人， 顯然用二進位制的資料（0 和 1）來表示是很自然的想法， 這段文字有 6 個字母ABCDEF。 相應的二進位制資料表示就是： 這樣真正傳輸的就是編碼後的 “001000011010000011101100100011”， 對方接受可以按照 3 位一分來譯碼。 如果文章內容很長， 這樣的二進位制串也很可怕。 此時就應該使用 赫夫曼樹 。 假設6個字母的頻率： A:27, B:8, C:15, D:15, E:30, F:5 合起來正好是100%。 左圖構造赫夫曼樹的過程權值顯示； 右圖是將權值左子樹改為0， 右子樹分制改為1後的赫夫曼樹 此時我們對 6 個字母重新編碼 原編碼： 001000011010000011101100100011［30個字元］ 新編碼： 1001010010101001000111100［25個字元］ 少了5個字元， 也就是大約 17%［5/30=0。167］ 的成本。 字元愈多， 這種壓縮效果更明顯 問題來了: 收到了赫夫曼編碼又該如何解析呢? 編碼中非0即1， 長短不等的話其實很容易混淆的， 所以要設計長短不等的編碼： 任一字元的編碼都不是另一個字元編碼的字首， 這種比那嗎稱為字首編碼［01， 1001， 101， 00， 11， 1000都是不同長短長度， 因此不容易混淆］ 這樣並不足以， 我們去方便的解碼， 因此在解碼的時候接收方和傳送方都必須要約定好相同的 赫夫曼編碼規則 當收到 1001010010101001000111100 時， 約定好的 赫夫曼編碼規則 可知 1001 得到第一個字母是 B ， 接下來的誒 01 意味著第二個字母 A … 一般地，設需要編碼的字符集為{ d1，d2， …， dn }，各個字元在電文中出現的次數或頻率集合為{ w1，w2， …， wn}， 以d1，d2，…， dn作為葉子結點，以w1，w2， …， wn作為相應葉子結點的權值來構造一棵赫夫曼樹。 規定赫夫曼樹的左分支代表0，右分支代表1，則從根結點到葉子結點所經過的路徑分支組成的0和1的序列便為該結點對應字元的編碼，這就是赫夫曼編碼。 3。4。3 線索二叉樹 ^ ： 表示空指標， 圖中二叉樹有許多空指標， 發現這些空間都沒有利用。 這其實不是一個好現象， 應該合理利用起來。 首先那我們來看看有多少個多少個空指標呢？ 對於一個有 n 個節點的二叉樹有 2n 個指標， 而 n 個節點的二叉樹一共有 n-1 條分支線數， 也就是說存在 2n-(n-1)=n+1 個空指標域。 對應到題目中就有 11 個空指標的浪費。 另一方面， 我們中序遍歷二叉樹得出 HDIBJEAFCG ， 這樣的字元序列， 我們知道 J 的前驅是 B 後繼是 E ， 也就是說從 中序遍歷二叉樹我們可以知道任意一個節點的前驅和後繼 問題: 上邊找到的規律是建立在已經遍歷過的基礎上, 在二叉連結串列上我們只知道每個左右孩子的地址, 而不知道後繼是誰, 後繼是誰要想知道必須要再次遍歷一次 解決方案 我們在遍歷的時候就建立好前驅後繼。 我們把這種前驅和後繼的指標稱為線索， 加上線索的二叉連結串列稱為線索連結串列， 相應的二叉樹稱為 線索二叉樹（Threaded Binary Tree） 我們把這棵二叉樹進行中序遍歷， 將所有空指標的 rchild ， 改為指向它的後續結點。 於是就可以透過指標知道 H 的後繼是 D （1）， I 的後繼是 B （2）， J 的後繼是 E （3）（E。next = A（4）， F。next = C（5）， G。next = null（6））。 此時共有 6 個空指標被利用。 再看圖， 把這棵二叉樹中的所有空指標域中的 lchild ， 改為指向當前結點的前驅。 因此 H 的前驅是 NULL （1）， I 的前驅是 D （2）［J。prev = B（3）， F。prev = A（4）， G。prev = C（5）］。一共有 5 個空指標被利用， 加上上面的 右子樹 利用後一共有 11 個空指標被利用 實線空心箭頭為前驅 prev, 虛線實心箭頭為後繼 next 就更容易看出， 線索二叉樹， 等於是把一棵二叉樹變成了一個雙向連結串列， 這樣對於我們的插入刪除節點， 查詢某個節點都帶來了方便。 所以我們對 二叉樹以某種次序遍歷使其變為線索二叉樹的過程為 線索化 二叉搜尋樹與雙向連結串列 OJ題目練習 Java： 構建程式碼 /** public class TreeNode { int val = 0； TreeNode left = null； TreeNode right = null； public TreeNode（int val） { this。val = val； } } */ public class Solution { private TreeNode prev = null ； // 1。 用來記錄前驅節點 private void ConvertChild （ TreeNode root ） { if （ root == null ） { return ； } else { // 2。根絕二叉搜尋樹性質： 中序遍歷就是有序結果 ConvertChild （ root 。 left ） ； /* 3。建立前後指向 節點的左子樹是前驅， 右子樹是後繼 對於最左端葉子結點 4 這種沒有左右子樹的結點要特殊考慮： 保留的前驅節點的右子樹指向當前函式呼叫的節點【4。right = 6】， 但對於這種情況還需要判斷它是否為 null， 否則就會 空指標異常 4。left = null null。right = 4；空指標異常 null = 4； 加上 if 判斷後： 4。left = null； null = 4； 程式 return 返回到 6節點函式 6。left = 4； 4。right = 6； 4 = 6； */ root 。 left = prev ； // 第一次遞迴結束返回到 root 是4這個節點 if （ prev ！= null ） { prev 。 right = root ； } prev = root ； ConvertChild （ root 。 right ） ； } } public TreeNode Convert （ TreeNode pRootOfTree ） { if （ pRootOfTree == null ） { return null ； } else { ConvertChild （ pRootOfTree ） ； while （ pRootOfTree 。 left ！= null ） { pRootOfTree = pRootOfTree 。 left ； } return pRootOfTree ； } } } Java 語言在定義節點類的時候只需要： 資料域val， 左子樹left， 右子樹right ， 在實現雙向連結串列的時候需要額外一個 prev節點 來存放當前節點的前驅【左子樹】 C: 線索二叉樹結構體思路 lchild: 左子樹， rchild: 右子樹 對於C語言而言， 我們如何知道某一節點的 lchild 是指向它的左孩子還是指向前驅呢？ rchild 是指向右孩子還是後繼呢？ 比如： E 節點的 lchild 是指向它的左子樹 J ， 而 rchild 卻是指向它的後繼 A 。 顯然我們在決定 lchild 是指向左孩子還是前驅， rchild 是指向右孩子還是後繼上是需要一個區分標誌的。 因此我們給每個節點在增設兩個標誌域 ltag 和 rtag ， 注意 ltag 和 rtag 只是存放 0 和 1 的布林型變數， 其佔用的記憶體空間要小於像 lchild 和 rchild 的指標變數 ltag == 0時指向該節點的左孩子， 為1時指向該節點的後繼 rtag == 0時指向該節點的右孩子， 為1時指向該節點的後繼 typedef int DataType ； // 資料型別 typedef enum { Link ， //Link == 0表示只想做還有子樹指標 Thread ， //Thread == 1表示只想前驅或後繼的線索 } PointerTag ； typedef struct BiThrNode { // 二叉樹儲存節點結構 DataType data ； // 資料域 struct BiThrNode * lchild ， * rchild ； // 左右子樹 PointerTag LTag ； // 左標誌 PointerTag RTag ； // 右標誌 } BiThrNode ， * BiThrTree ； 那麼瞭解了C語言的結構體構造線索二叉樹原理後我們該如何實現呢？ 參考前邊 Java程式碼的實現， 我們發現可以規律無非是 左根右 的方式處理資料。 無非是中間那部分 根 的資料如何處理 BiThrNode * prev ； // 全域性變數， 始終指向剛剛訪問過的節點 void InThreading （ BiThrNode * pb ） { if （ pb ） { /* * 中序遍歷線索化二叉樹遞迴函式 */ // 1。 左 InThreading （ pb -> lchild ） ； /* * 2。中間部分建立聯絡 * 因為中序遍歷之後第一個元素就是 連結串列的頭節點， 所以應該選取左節點為空的節點就是 連結串列頭節點 * * 前驅分析： * if（！pb->lchild）： 表示如果某結點的左子樹域為空， 因為其前驅節點剛剛訪問過 * 賦值給了 prev， 所以可以把 prev 賦值給 pb->lchild， 並修改 pb->Ltag=Thread。完成了前驅節點的線索化 * 後繼分析： * 此時 pb 節點的後繼還沒有訪問到， 只能透過它的前驅節點 prev 的右子樹 rchild 來判斷： * if（！prev-rchild）為空， 則 pb 就是 prev 的後繼， 於是 prev-Thread， prev->rchild = pb 完成後繼節點的線索化 * 完成前驅和後繼的判斷後把 pb 給 prev， 便於下一次遍歷 */ if （ ！ pb -> lchild ） { // 如果沒有左孩子 pb -> LTag = Thread ； // 前驅線索 pb -> lchild = prev ； // 左孩子指標指向前驅 } if （ ！ prev -> rchild ） { // 如果沒有右孩子 prev -> LTag = Thread ； // 後繼線索 prev -> lchild = pb ； // 右孩子指標指向後繼 } prev = pb ； // 3。右 InThreading （ pb -> rchild ） ； } } 4。 總結回顧 二叉樹每個結點最多兩棵子樹，有左右之分。提到了斜樹，滿二叉樹、完全二叉樹等特殊二叉樹的概念 我們接著談到它的各種性質，這些性質給我們研究二叉樹帶來了方便。 二叉樹的儲存結構由於其特殊性使得既可以用順序儲存結構又可以用鏈式儲存結構表示 遍歷是二叉樹最重要的一門學問，前序、中序、後序以及層序遍歷都是需要熟練掌握的知識。要讓自己要學會用計算機的執行思維去模擬遞迴的實現，可以加深我們對遞迴的理解。不過，並非二叉樹遍歷就一定要用到遞迴， 只不過遞迴的實現比較優雅而已。這點需要明確 二叉樹的建立自然也是可以透過遞迴來實現 搜尋二叉樹能實現查詢效率較大化， 如果遇到 斜樹 則會變的很慢 研究中也發現，二叉連結串列有很多浪費的空指標可以利用，查詢某個結點的前驅和後繼為什麼非要每次遍歷才可以得到，這就引出瞭如何構造一棵線索二叉樹的問題。線索二叉樹給二叉樹的結點查詢和遍歷帶來了高效率 最後，我們知道了關於二叉樹的另一個應用，赫夫曼樹和赫夫曼編碼，對於帶權路徑的二叉樹做了詳盡地講述，讓你初步理解資料壓縮的原理，並明白其是如何做到無最後，我們提到了關於二叉樹的-一個應用，赫夫曼樹和赫夫曼編碼，對於帶權路徑的二叉樹做了詳盡地講述，讓你初步理解資料壓縮的原理，並明白其是如何做到無損編碼和無錯解碼 中間插入的一些 力扣， 牛克 線上OJ就當練手與解析， 有興趣的可以去刷一刷。 5。 結束語 二叉樹相較於連結串列， 佇列， 棧顯然更難一層樓。路漫漫求修遠兮， 吾將上下而求索。勉勵自己頁面每一個來看我部落格的人共同進步， 學習更高質量的知識為目標。 ，https：//blog。csdn。net/weixin_45364220/article/details/120621141
上一篇鋼化玻璃的特性和原理
下一篇庭院景觀假山玲瓏剔透的美