数据结构与算法一 - 二叉树基础
前言
樹是數據結構中的重中之重，尤其以各類二叉樹為學習的難點。一直以來，對于樹的掌握都是模棱兩可的狀態，現在希望通過寫一個關于二叉樹的專題系列。在學習與總結的同時更加深入的了解掌握二叉樹。本系列文章將著重介紹一般二叉樹、完全二叉樹、滿二叉樹、線索二叉樹、霍夫曼樹、二叉排序樹、平衡二叉樹、紅黑樹、B樹。希望各位讀者能夠關注專題，并給出相應意見，通過系列的學習做到心中有“樹”。
1 重點概念
1.1 結點概念
結點是數據結構中的基礎，是構成復雜數據結構的基本組成單位。
1.2 樹結點聲明
本系列文章中提及的結點專指樹的結點。例如：結點A在圖中表示為：
?
2 樹
2.1 定義
樹（Tree）是n（n>=0)個結點的有限集。n=0時稱為空樹。在任意一顆非空樹中：
1）有且僅有一個特定的稱為根（Root）的結點；
2）當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1、T2、......、Tn，其中每一個集合本身又是一棵樹，并且稱為根的子樹。
此外，樹的定義還需要強調以下兩點：
1）n>0時根結點是唯一的，不可能存在多個根結點，數據結構中的樹只能有一個根結點。
2）m>0時，子樹的個數沒有限制，但它們一定是互不相交的。
示例樹：
圖2.1為一棵普通的樹：
?
圖2.1 普通樹由樹的定義可以看出，樹的定義使用了遞歸的方式。遞歸在樹的學習過程中起著重要作用，如果對于遞歸不是十分了解，建議先看看遞歸算法
2.2 結點的度
結點擁有的子樹數目稱為結點的度。
圖2.2中標注了圖2.1所示樹的各個結點的度。
?
圖2.2 度示意圖?
2.3 結點關系
結點子樹的根結點為該結點的孩子結點。相應該結點稱為孩子結點的雙親結點。
圖2.2中，A為B的雙親結點，B為A的孩子結點。
同一個雙親結點的孩子結點之間互稱兄弟結點。
圖2.2中，結點B與結點C互為兄弟結點。
2.4 結點層次
從根開始定義起，根為第一層，根的孩子為第二層，以此類推。
圖2.3表示了圖2.1所示樹的層次關系
?
圖2.3 層示意圖2.5 樹的深度
樹中結點的最大層次數稱為樹的深度或高度。圖2.1所示樹的深度為4。
3 二叉樹
3.1 定義
二叉樹是n(n>=0)個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹組成。
圖3.1展示了一棵普通二叉樹：
?
圖3.1 二叉樹?
3.2 二叉樹特點
由二叉樹定義以及圖示分析得出二叉樹有以下特點：
1）每個結點最多有兩顆子樹，所以二叉樹中不存在度大于2的結點。
2）左子樹和右子樹是有順序的，次序不能任意顛倒。
3）即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。
3.3 二叉樹性質
1）在二叉樹的第i層上最多有2i-1 個節點 。（i>=1）
2）二叉樹中如果深度為k,那么最多有2k-1個節點。(k>=1）
3）n0=n2+1 n0表示度數為0的節點數，n2表示度數為2的節點數。
4）在完全二叉樹中，具有n個節點的完全二叉樹的深度為[log2n]+1，其中[log2n]是向下取整。
5）若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結點有如下特性：
(1) 若 i=1，則該結點是二叉樹的根，無雙親, 否則，編號為 [i/2] 的結點為其雙親結點;
(2) 若 2i>n，則該結點無左孩子， 否則，編號為 2i 的結點為其左孩子結點；
(3) 若 2i+1>n，則該結點無右孩子結點， 否則，編號為2i+1 的結點為其右孩子結點。
3.4 斜樹
斜樹：所有的結點都只有左子樹的二叉樹叫左斜樹。所有結點都是只有右子樹的二叉樹叫右斜樹。這兩者統稱為斜樹。
?
圖3.2 左斜樹 圖3.3 右斜樹?
?
3.5 滿二叉樹
滿二叉樹：在一棵二叉樹中。如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。
滿二叉樹的特點有：
1）葉子只能出現在最下一層。出現在其它層就不可能達成平衡。
2）非葉子結點的度一定是2。
3）在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多。
3.6 完全二叉樹
完全二叉樹：對一顆具有n個結點的二叉樹按層編號，如果編號為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。
圖3.5展示一棵完全二叉樹
特點：
1）葉子結點只能出現在最下層和次下層。
2）最下層的葉子結點集中在樹的左部。
3）倒數第二層若存在葉子結點，一定在右部連續位置。
4）如果結點度為1，則該結點只有左孩子，即沒有右子樹。
5）同樣結點數目的二叉樹，完全二叉樹深度最小。
注：滿二叉樹一定是完全二叉樹，但反過來不一定成立。
?
3.7 二叉樹的存儲結構
3.7.1 順序存儲
二叉樹的順序存儲結構就是使用一維數組存儲二叉樹中的結點，并且結點的存儲位置，就是數組的下標索引。
圖3.6圖3.6所示的一棵完全二叉樹采用順序存儲方式，如圖3.7表示：
圖3.7 順序存儲由圖3.7可以看出，當二叉樹為完全二叉樹時，結點數剛好填滿數組。
那么當二叉樹不為完全二叉樹時，采用順序存儲形式如何呢？例如：對于圖3.8描述的二叉樹：
其中，∧表示數組中此位置沒有存儲結點。此時可以發現，順序存儲結構中已經出現了空間浪費的情況。
那么對于圖3.3所示的右斜樹極端情況對應的順序存儲結構如圖3.10所示：
?
圖3.10由圖3.10可以看出，對于這種右斜樹極端情況，采用順序存儲的方式是十分浪費空間的。因此，順序存儲一般適用于完全二叉樹。
3.7.2 二叉鏈表
既然順序存儲不能滿足二叉樹的存儲需求，那么考慮采用鏈式存儲。由二叉樹定義可知，二叉樹的每個結點最多有兩個孩子。因此，可以將結點數據結構定義為一個數據和兩個指針域。表示方式如圖3.11所示：
?
圖3.11
定義結點代碼：
public class BitNode<T>{/// <summary>/// 左孩子/// </summary>public BitNode<T> Left { get; set; }/// <summary>/// 數據域/// </summary>public T Data { get; set; }/// <summary>/// 右孩子/// </summary>public BitNode<T> Right { get; set; }}
則圖3.6所示的二叉樹可以采用圖3.12表示。
?
圖3.12圖3.12中采用一種鏈表結構存儲二叉樹，這種鏈表稱為二叉鏈表。
3.8 二叉樹遍歷
二叉樹的遍歷一個重點考查的知識點。
3.8.1 定義
二叉樹的遍歷是指從二叉樹的根結點出發，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次，且僅被訪問一次。
二叉樹的訪問次序可以分為四種：
前序遍歷
中序遍歷
后序遍歷
層序遍歷
3.8.2 前序遍歷
前序遍歷通俗的說就是從二叉樹的根結點出發，當第一次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。?
3.13
圖3.13所示二叉樹訪問如下：
?
從根結點出發，則第一次到達結點A，故輸出A;
繼續向左訪問，第一次訪問結點B，故輸出B；
按照同樣規則，輸出D，輸出H；
當到達葉子結點H，返回到D，此時已經是第二次到達D，故不在輸出D，進而向D右子樹訪問，D右子樹不為空，則訪問至I，第一次到達I，則輸出I；
I為葉子結點，則返回到D，D左右子樹已經訪問完畢，則返回到B，進而到B右子樹，第一次到達E，故輸出E；
向E左子樹，故輸出J；
按照同樣的訪問規則，繼續輸出C、F、G；
則3.13所示二叉樹的前序遍歷輸出為：
ABDHIEJCFG
?
3.8.3 中序遍歷
中序遍歷就是從二叉樹的根結點出發，當第二次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。
圖3.13所示二叉樹中序訪問如下：
從根結點出發，則第一次到達結點A，不輸出A，繼續向左訪問，第一次訪問結點B，不輸出B；繼續到達D，H；
到達H，H左子樹為空，則返回到H，此時第二次訪問H，故輸出H；
H右子樹為空，則返回至D，此時第二次到達D，故輸出D；
由D返回至B，第二次到達B，故輸出B；
按照同樣規則繼續訪問，輸出J、E、A、F、C、G；
則3.13所示二叉樹的中序遍歷輸出為：
HDIBJEAFCG
3.8.4 后序遍歷
后序遍歷就是從二叉樹的根結點出發，當第三次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。
圖3.13所示二叉樹后序訪問如下：
從根結點出發，則第一次到達結點A，不輸出A，繼續向左訪問，第一次訪問結點B，不輸出B；繼續到達D，H；
到達H，H左子樹為空，則返回到H，此時第二次訪問H，不輸出H；
H右子樹為空，則返回至H，此時第三次到達H，故輸出H；
由H返回至D，第二次到達D，不輸出D；
繼續訪問至I，I左右子樹均為空，故第三次訪問I時，輸出I；
返回至D，此時第三次到達D，故輸出D；
按照同樣規則繼續訪問，輸出J、E、B、F、G、C，A；
則圖3.13所示二叉樹的后序遍歷輸出為：
HIDJEBFGCA
雖然二叉樹的遍歷過程看似繁瑣，但是由于二叉樹是一種遞歸定義的結構，故采用遞歸方式遍歷二叉樹的代碼十分簡單。
遞歸實現代碼如下：
3.8.5 層次遍歷
層次遍歷就是按照樹的層次自上而下的遍歷二叉樹。針對圖3.13所示二叉樹的層次遍歷結果為：
ABCDEFGHIJ
層次遍歷的詳細方法可以參考二叉樹的按層遍歷法。
3.8.6 遍歷常考考點
對于二叉樹的遍歷有一類典型題型。
1）已知前序遍歷序列和中序遍歷序列，確定一棵二叉樹。
例題：若一棵二叉樹的前序遍歷為ABCDEF，中序遍歷為CBAEDF，請畫出這棵二叉樹。
分析：前序遍歷第一個輸出結點為根結點，故A為根結點。早中序遍歷中根結點處于左右子樹結點中間，故結點A的左子樹中結點有CB，右子樹中結點有EDF。
如圖3.14所示：
?
?
圖3.14按照同樣的分析方法，對A的左右子樹進行劃分，最后得出二叉樹的形態如圖3.15所示：
?
?
圖3.15.png2）已知后序遍歷序列和中序遍歷序列，確定一棵二叉樹。
后序遍歷中最后訪問的為根結點，因此可以按照上述同樣的方法，找到根結點后分成兩棵子樹，進而繼續找到子樹的根結點，一步步確定二叉樹的形態。
注：已知前序遍歷序列和后序遍歷序列，不可以唯一確定一棵二叉樹。
4 結語
通過上述的介紹，已經對于二叉樹有了初步的認識。本篇文章介紹的基礎知識希望讀者能夠牢牢掌握，并且能夠在腦海中建立一棵二叉樹的模型，為后續學習打好基礎。
附c#實現的代碼：
public class BitTree : BitNode<string> {public BitTree(){this.Data = "A";this.Left = new BitNode<string>{Data = "B",Left = new BitNode<string>{Data = "D",Left = new BitNode<string> { Data = "H" },Right = new BitNode<string> { Data = "I" },},Right = new BitNode<string>{Data = "E",Left = new BitNode<string> { Data = "J" }}};this.Right = new BitNode<string>{Data = "C",Left = new BitNode<string> { Data = "F" },Right = new BitNode<string> { Data = "G" }};}}public class BitNode<T> {/// <summary>/// 左孩子/// </summary>public BitNode<T> Left { get; set; }/// <summary>/// 數據域/// </summary>public T Data { get; set; }/// <summary>/// 右孩子/// </summary>public BitNode<T> Right { get; set; } }// 前序 void PreOrderVisitTree<T>(BitNode<T> node) {Console.WriteLine(node.Data.ToString());if (node.Left != null) this.PreOrderVisitTree<T>(node.Left);if (node.Right != null) this.PreOrderVisitTree<T>(node.Right); }// 中序 void InOrderVisitTree<T>(BitNode<T> node) {if (node.Left != null) this.InOrderVisitTree<T>(node.Left);Console.WriteLine(node.Data.ToString());if (node.Right != null) this.InOrderVisitTree<T>(node.Right); }// 后序 void PostOrderVisitTree<T>(BitNode<T> node) {if (node.Left != null) this.PostOrderVisitTree<T>(node.Left);if (node.Right != null) this.PostOrderVisitTree<T>(node.Right);Console.WriteLine(node.Data.ToString()); }var bt = new BitTree(); this.PostOrderVisitTree<string>(bt); View Code?
更多有關樹的專題請移步
樹專題
作者：MrHorse1992
出處：https://www.jianshu.com/p/bf73c8d50dc2
技術交流Q群: 816425449
轉載于:https://www.cnblogs.com/yiting/p/11211249.html
總結
以上是生活随笔為你收集整理的数据结构与算法一 - 二叉树基础的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： day011_步入百万年薪的第十一天
- 下一篇： 两个大整数的除法