深度閱讀：大學生必須要搞懂的資料結構，15張圖來了解【樹】

樹的概念

什么是樹？

樹屬于非線性資料結構的一種，概念也極多，是由結點或頂點和邊組成的且不存在著任何環的一種資料結構，

沒有結點的樹稱為空樹，一棵非空的樹包括一個根結點，還很可能有多個附加結點，并且所有結點構成一個多級分層結構，

樹的定義

n個節點組成的有限集合，n=0，空樹；n>0,1個根節點，m個互不相交的有限集，每個子集為根的子樹，如圖所示為一顆樹：

樹

樹的基本術語

• 節點的度：樹中某個節點的子樹的個數，

• 樹的度：樹中各節點的度的最大值，

• 分支節點：度不為零的節點，

• 葉子節點：度為零的節點，

• 路徑：i->j；

• 路徑長度：路徑經過節點數目減1，

• 孩子節點：某節點的后繼節點；

• 雙親節點：該節點為其孩子節點的雙親節點（父母節點）；

• 兄弟節點：同一雙親的孩子節點；

• 子孫節點：某節點所有子樹中的節點；

• 祖先節點：從樹節點到該節點的路徑上的節點；

• 節點的層次：根節點為第一層，以此類推；

• 樹的高度：樹中節點的最大層次；

• 有序樹：樹中節點子樹按次序從左向右安排，次序不能改變；

• 無序樹：與有序樹相反；

• 森林：互不相交的樹的集合，

樹的性質

1. 樹的節點樹為所有節點度數加1（加根節點），

2. 度為m的樹中第i層最多有m^(i-1)個節點，

3. 高度為h的m次樹至多(m^h-1)/(m-1)個節點，

4. 具有n個節點的m次樹的最小高度為logm( n(m-1) + 1 )向上取整，

二叉樹

二叉樹簡介

二叉樹是n(n>=0)個結點的有限集合，每一個結點中最多擁有一個左結點和一個右結點，并且沒有多余的結點，如圖所示：

二叉樹

二叉樹的特點

根據二叉樹的定義以及圖示分析得出二叉樹有以下特點：

1. 每個結點最多有兩顆子樹，不存在度大于2的結點，

2. 左子樹和右子樹的次序不能任意顛倒，

3. 即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹，

二叉樹的性質

二叉樹具有以下幾種特征

1. 二叉樹第i層上的結點數目最多為2{i-1} (i≥1)，

2. 深度為k的二叉樹至多有(2{k}-1)(k≥1)個結點，

3. 包含n個結點的二叉樹的高度至少為log2 (n+1)，

4. 在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1，

幾種特殊的二叉樹

斜樹

所有的結點都只有左(右)子樹的二叉樹叫左(右)斜樹，統稱為斜樹，如圖所示：

斜樹

滿二叉樹

在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹，其有以下特點

1. 葉子只能出現在最下一層，否則就不可能達成平衡，

2. 非葉子結點的度一定是2，

3. 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多，

滿二叉樹

完全二叉樹

一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹，

完全二叉樹

二叉樹的存盤

簡介

以創建一顆二叉樹，并實作通過特定的插入順序和讀取順序達成讀取為順序為例子進行簡介，

結點設計

一顆二叉樹的結點設計一定要有如下內容：

• 結點元素，data域，用來存盤資料；

• 左孩子結點，left指標，用來指向當前結點的下一層的左邊結點；

• 右孩子結點，right指標，用來指向當前結點的下一層的右邊結點；

除此之外，我們使用一棵樹的時候需要建立一顆樹根，由這個根，來進行逐步的向下構建，其代碼如下：

樹的創建

首先創建一個空的結點進行連接，將這個空的結點中的date域賦予資料，再判斷tree中是否是一個空樹，如果為空，只需要將整個根指向這一個結點即可，如果不為空，再進行兩個判斷，判斷輸入的資料是否大于或者小于當前比對的結點資料，根據其大小進行相應的排列，這樣存盤進入的資料總是有一定規律的，在輸出的時候根據這個規律進行輸出即可，其代碼可以顯示為：

遍歷，顯示樹

代碼如下：

樹的遍歷之先序遍歷二叉樹

遍歷簡介

遍歷是按照一定的規則性，將資料結構中的所有資料全部依次訪問，而二叉樹需要通過在各節點與其孩子之間約定某種區域次序，間接地定義某種全域次序，

• 先序遍歷：根左右

先序遍歷：

先序遍歷就是在訪問二叉樹的結點的時候采用，先根，再左，再右的方式，對于一個最簡單的訪問而言如下圖，先序遍歷的訪問順序就是A，B，C

多個結點相互嵌套構成的二叉樹如圖所示，在訪問遍歷一開始的時候，先訪問根結點A，次訪問左節點B，由于左結點中嵌套了一組結點，因此左節點又作為下一個結點的根結點，

繼續沿著B訪問到了D，同樣由于D中包含了一組新的結點，D又作為根節點繼續訪問，就又訪問到了E，由于E沒有后面的結點了，作為D為根的左結點E訪問結束后，訪問到F，這一組訪問結束之后再回退訪問G，那么這一個二叉樹的先序遍歷訪問順序就是：ABDEFGCH

代碼實作

擴展->前綴運算式

我們日常的運算運算式通常是如下形式，這種成為中綴運算式，也就是運算子在運算元的中間，如圖，為常規運算式：(a+b)*c

其二叉樹的表現形式為：

而前綴運算式的表達方式就是 *+cab ，它的一個特征就是符號遷移，常規的運算式是需要大量的括號表達先后順序的，而這樣的運算式表達形式不需要，更容易讓計算機處理，

我們常規的運算式的計算是中序的，而計算機更方便對前綴運算式這樣的方式進行理解，進行這樣的轉換首先思路要進行轉換，

在代碼中我們實作這樣的轉換一般可以利用堆疊，熟練書些這樣的轉換就需要STL的掌握，

樹的遍歷之中序遍歷二叉樹

簡介

• 中序遍歷：左根右

如下圖，就一個最簡單的二叉樹遍歷而言，中序遍歷的遍歷訪問程序是先B再A再C，

多個結點構成的如圖所示，進行第一次訪問的時候，我們在ABC中進行遍歷，由左根右的順序，我們遍歷訪問到B，B同時又作為BDG的根結點，因此需要繼續向下進行遍歷，

此時我們遍歷到DEF，這時E屬于這一組之中的左結點，因此我們根據根左右的先后順序得到了最先的遍歷效果，EDF，

這EDF同時作為BDG中的左節點（把EDF看作一個整體）進行回溯，此時的訪問的結點順序為EDFBG，

同理EDFBG作為ABC的左結點根據左根右的順序EDFBGAC，左半部分訪問完畢接著訪問右半部分，我們將^CH（^表示空）看作一組左中右，而C就是由EDFBGAC組合而成，因此最終的遍歷順序為：EDFBGACH

代碼實作

中綴運算式（常規算式）

中綴運算式是一個通用的算識訓邏輯公式表示方法，中綴運算式就是我們最常用的運算式形式，也是人最容易理解的運算式形式，

如圖，為常規運算式：(a+b)*c

其二叉樹的表現形式為：

由前文可知前綴運算式的表達方式就是 *+cab ，我們常規的運算式的計算是中序的，其運算式就是(a+b)*c，

我們可以理解為將運算式利用二叉樹化，然后通過中序遍歷的方式進行提取，如果需要發生組合時，需要我們借助括號的形式表示優先級，這樣也有一個弊端，就是當多個嵌套的時候需要的括號較多，

樹的遍歷之后序遍歷二叉樹

簡介

• 后序遍歷：左右根

后序遍歷就是在訪問二叉樹的結點的時候采用，先左，再右，再根的方式，對于一個最簡單的訪問而言如圖，先訪問左節點B，之后訪問右結點C，最后訪問根節點A，后序遍歷的訪問順序就是BCA

多個結點相互嵌套構成的二叉樹如下圖所示，在訪問遍歷一開始的時候，先訪問左節點B再訪問右結點C最后訪問A；

由于B結點其中也包含了新的結點，在面對處理的結點后還存在有與之相聯的結點的時候，需要優先處理其的子結點，這也是“遞回”的基本思路；

因此，由于B屬于DG的根結點，相較于B，應該先訪問D結點，而又由于D結點屬于EF的根結點，就又變成先訪問E結點，E屬于最末端了，根據后序遍歷左右根的訪問順序，依次生成EFDGB作為一個整體；

接著我們需要訪問C，由于C又是^HC之中的根結點，我們先訪問這個空結點，又因為其是一個空的結點，我們會跳過，就變成了HC的訪問順序；

最后在匯總的時候EFDGB作為左節點，HC作為右結點，A作為根結點，完成我們最終的遍歷順序EFDGBHCA，

代碼實作

后綴運算式

后綴運算式與前綴運算式不同，前綴運算式采用先序遍歷的方式遍歷訪問我們的公式順序，常規式則就是中序方式，而后綴運算式采用后續遍歷的方式進行訪問，

如圖，為常規運算式：(a+b)*c

其二叉樹的表現形式為：

而后綴運算式的表達方式就是ab+c* ，相較于前綴運算式，后綴運算式則就是將符號進行后移，其在計算機中的讀取運算概念也符合堆疊的思路，因此沒有什么特殊的不同，

標籤：C

上一篇：56.Qt-滾動字幕之無間隙滾動(原創)

下一篇：小白做了個學生資訊管理系統，但是不知道為什么就是運行的界面不對