樹的概念

什么是樹？

樹屬于非線性數(shù)據(jù)結(jié)構(gòu)的一種，概念也極多，是由結(jié)點(diǎn)或頂點(diǎn)和邊組成的且不存在著任何環(huán)的一種數(shù)據(jù)結(jié)構(gòu)。

沒有結(jié)點(diǎn)的樹稱為空樹。一棵非空的樹包括一個(gè)根結(jié)點(diǎn)，還很可能有多個(gè)附加結(jié)點(diǎn)，并且所有結(jié)點(diǎn)構(gòu)成一個(gè)多級分層結(jié)構(gòu)。

樹的定義

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

樹的基本術(shù)語

• 節(jié)點(diǎn)的度：樹中某個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)。

• 樹的度：樹中各節(jié)點(diǎn)的度的最大值。

• 分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)。

• 葉子節(jié)點(diǎn)：度為零的節(jié)點(diǎn)。

• 路徑：i->j；

• 路徑長度：路徑經(jīng)過節(jié)點(diǎn)數(shù)目減1。

• 孩子節(jié)點(diǎn)：某節(jié)點(diǎn)的后繼節(jié)點(diǎn)；

• 雙親節(jié)點(diǎn)：該節(jié)點(diǎn)為其孩子節(jié)點(diǎn)的雙親節(jié)點(diǎn)（父母節(jié)點(diǎn)）；

• 兄弟節(jié)點(diǎn)：同一雙親的孩子節(jié)點(diǎn)；

• 子孫節(jié)點(diǎn)：某節(jié)點(diǎn)所有子樹中的節(jié)點(diǎn)；

• 祖先節(jié)點(diǎn)：從樹節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)；

• 節(jié)點(diǎn)的層次：根節(jié)點(diǎn)為第一層，以此類推；

• 樹的高度：樹中節(jié)點(diǎn)的最大層次；

• 有序樹：樹中節(jié)點(diǎn)子樹按次序從左向右安排，次序不能改變；

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

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

樹的性質(zhì)

1. 樹的節(jié)點(diǎn)樹為所有節(jié)點(diǎn)度數(shù)加1（加根節(jié)點(diǎn)）。

2. 度為m的樹中第i層最多有m^(i-1)個(gè)節(jié)點(diǎn)。

3. 高度為h的m次樹至多(m^h-1)/(m-1)個(gè)節(jié)點(diǎn)。

4. 具有n個(gè)節(jié)點(diǎn)的m次樹的最小高度為logm( n(m-1) + 1 )向上取整。

二叉樹

二叉樹簡介

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

二叉樹的特點(diǎn)

根據(jù)二叉樹的定義以及圖示分析得出二叉樹有以下特點(diǎn)：

1. 每個(gè)結(jié)點(diǎn)最多有兩顆子樹，不存在度大于2的結(jié)點(diǎn)。

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

3. 即使樹中某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。

二叉樹的性質(zhì)

二叉樹具有以下幾種特征

1. 二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2{i-1} (i≥1)。

2. 深度為k的二叉樹至多有(2{k}-1)(k≥1)個(gè)結(jié)點(diǎn)。

3. 包含n個(gè)結(jié)點(diǎn)的二叉樹的高度至少為log2 (n+1)。

4. 在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

幾種特殊的二叉樹

斜樹

所有的結(jié)點(diǎn)都只有左(右)子樹的二叉樹叫左(右)斜樹，統(tǒng)稱為斜樹，如圖所示：

滿二叉樹

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

1. 葉子只能出現(xiàn)在最下一層，否則就不可能達(dá)成平衡。

2. 非葉子結(jié)點(diǎn)的度一定是2。

3. 在同樣深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多，葉子數(shù)最多。

完全二叉樹

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

二叉樹的存儲

簡介

以創(chuàng)建一顆二叉樹，并實(shí)現(xiàn)通過特定的插入順序和讀取順序達(dá)成讀取為順序?yàn)槔舆M(jìn)行簡介。

結(jié)點(diǎn)設(shè)計(jì)

一顆二叉樹的結(jié)點(diǎn)設(shè)計(jì)一定要有如下內(nèi)容：

• 結(jié)點(diǎn)元素，data域，用來存儲數(shù)據(jù)；

• 左孩子結(jié)點(diǎn)，left指針，用來指向當(dāng)前結(jié)點(diǎn)的下一層的左邊結(jié)點(diǎn)；

• 右孩子結(jié)點(diǎn)，right指針，用來指向當(dāng)前結(jié)點(diǎn)的下一層的右邊結(jié)點(diǎn)；

除此之外，我們使用一棵樹的時(shí)候需要建立一顆樹根，由這個(gè)根，來進(jìn)行逐步的向下構(gòu)建，其代碼如下：

//樹的結(jié)點(diǎn)
typedef?struct?node{
????int?data;
????struct?node*?left;
????struct?node*?right;
}?Node;

//樹根
typedef?struct?{
????Node*?root;
}?Tree;

樹的創(chuàng)建

首先創(chuàng)建一個(gè)空的結(jié)點(diǎn)進(jìn)行連接，將這個(gè)空的結(jié)點(diǎn)中的date域賦予數(shù)據(jù)，再判斷tree中是否是一個(gè)空樹，如果為空，只需要將整個(gè)根指向這一個(gè)結(jié)點(diǎn)即可，如果不為空，再進(jìn)行兩個(gè)判斷，判斷輸入的數(shù)據(jù)是否大于或者小于當(dāng)前比對的結(jié)點(diǎn)數(shù)據(jù)，根據(jù)其大小進(jìn)行相應(yīng)的排列，這樣存儲進(jìn)入的數(shù)據(jù)總是有一定規(guī)律的，在輸出的時(shí)候根據(jù)這個(gè)規(guī)律進(jìn)行輸出即可，其代碼可以顯示為：

//創(chuàng)建樹--插入數(shù)據(jù)
void?insert(Tree*?tree,?int?value){
????//創(chuàng)建一個(gè)節(jié)點(diǎn)，讓左右指針全部指向空，數(shù)據(jù)為value
????Node*?node=(Node*)malloc(sizeof(Node));
????node->data?=?value;
????node->left?=?NULL;
????node->right?=?NULL;
??
????//判斷樹是不是空樹，如果是，直接讓樹根指向這一個(gè)結(jié)點(diǎn)即可
????if?(tree->root?==?NULL){
????????tree->root?=?node;
????}?else?{//不是空樹
????????Node*?temp?=?tree->root;//從樹根開始
????????while?(temp?!=?NULL){
????????????if?(value?data){?//小于就進(jìn)左兒子
????????????????if?(temp->left?==?NULL){
????????????????????temp->left?=?node;
????????????????????return;
????????????????}?else?{//繼續(xù)往下搜尋
????????????????????temp?=?temp->left;
????????????????}
????????????}?else?{?//否則進(jìn)右兒子
????????????????if?(temp->right?==?NULL){
????????????????????temp->right?=?node;
????????????????????return;
????????????????}
????????????????else?{//繼續(xù)往下搜尋
????????????????????temp?=?temp->right;
????????????????}
????????????}
????????}
????}
????return;
}

遍歷，顯示樹

代碼如下：

//樹的中序遍歷?In-order?traversal
void?inorder(Node*?node){
????if?(node?!=?NULL)
????{
????????inorder(node->left);
????????printf("%d?",node->data);
????????inorder(node->right);
????}
}

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

遍歷簡介

遍歷是按照一定的規(guī)則性，將數(shù)據(jù)結(jié)構(gòu)中的所有數(shù)據(jù)全部依次訪問，而二叉樹需要通過在各節(jié)點(diǎn)與其孩子之間約定某種局部次序，間接地定義某種全局次序。

• 先序遍歷：根左右

先序遍歷：

先序遍歷就是在訪問二叉樹的結(jié)點(diǎn)的時(shí)候采用，先根，再左，再右的方式，對于一個(gè)最簡單的訪問而言如下圖，先序遍歷的訪問順序就是A，B，C

多個(gè)結(jié)點(diǎn)相互嵌套構(gòu)成的二叉樹如圖所示，在訪問遍歷一開始的時(shí)候，先訪問根結(jié)點(diǎn)A，次訪問左節(jié)點(diǎn)B，由于左結(jié)點(diǎn)中嵌套了一組結(jié)點(diǎn)，因此左節(jié)點(diǎn)又作為下一個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)。

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

代碼實(shí)現(xiàn)

//樹的先序遍歷?Preorder?traversal
void?preorder(Node*?node){
????if?(node?!=?NULL)
????{
????????printf("%d?",node->data);
????????inorder(node->left);
????????inorder(node->right);
????}
}

擴(kuò)展->前綴表達(dá)式

我們?nèi)粘５倪\(yùn)算表達(dá)式通常是如下形式，這種成為中綴表達(dá)式，也就是運(yùn)算符在運(yùn)算數(shù)的中間，如圖，為常規(guī)表達(dá)式：(a+b)*c

其二叉樹的表現(xiàn)形式為：

而前綴表達(dá)式的表達(dá)方式就是 *+cab ，它的一個(gè)特征就是符號遷移，常規(guī)的表達(dá)式是需要大量的括號表達(dá)先后順序的，而這樣的表達(dá)式表達(dá)形式不需要，更容易讓計(jì)算機(jī)處理。

我們常規(guī)的表達(dá)式的計(jì)算是中序的，而計(jì)算機(jī)更方便對前綴表達(dá)式這樣的方式進(jìn)行理解，進(jìn)行這樣的轉(zhuǎn)換首先思路要進(jìn)行轉(zhuǎn)換。

在代碼中我們實(shí)現(xiàn)這樣的轉(zhuǎn)換一般可以利用棧，熟練書些這樣的轉(zhuǎn)換就需要STL的掌握。

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

簡介

• 中序遍歷：左根右

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

多個(gè)結(jié)點(diǎn)構(gòu)成的如圖所示，進(jìn)行第一次訪問的時(shí)候，我們在ABC中進(jìn)行遍歷，由左根右的順序，我們遍歷訪問到B，B同時(shí)又作為BDG的根結(jié)點(diǎn)，因此需要繼續(xù)向下進(jìn)行遍歷。

此時(shí)我們遍歷到DEF，這時(shí)E屬于這一組之中的左結(jié)點(diǎn)，因此我們根據(jù)根左右的先后順序得到了最先的遍歷效果，EDF。

這EDF同時(shí)作為BDG中的左節(jié)點(diǎn)（把EDF看作一個(gè)整體）進(jìn)行回溯，此時(shí)的訪問的結(jié)點(diǎn)順序?yàn)镋DFBG。

同理EDFBG作為ABC的左結(jié)點(diǎn)根據(jù)左根右的順序EDFBGAC，左半部分訪問完畢接著訪問右半部分，我們將^CH（^表示空）看作一組左中右，而C就是由EDFBGAC組合而成，因此最終的遍歷順序?yàn)椋篍DFBGACH

代碼實(shí)現(xiàn)

//樹的中序遍歷?In-order?traversal
void?inorder(Node*?node){
????if?(node?!=?NULL)
????{
????????inorder(node->left);
????????printf("%d?",node->data);
????????inorder(node->right);
????}
}

中綴表達(dá)式（常規(guī)算式）

中綴表達(dá)式是一個(gè)通用的算術(shù)或邏輯公式表示方法。中綴表達(dá)式就是我們最常用的表達(dá)式形式，也是人最容易理解的表達(dá)式形式。

如圖，為常規(guī)表達(dá)式：(a+b)*c

其二叉樹的表現(xiàn)形式為：

由前文可知前綴表達(dá)式的表達(dá)方式就是 *+cab ，我們常規(guī)的表達(dá)式的計(jì)算是中序的，其表達(dá)式就是(a+b)*c。

我們可以理解為將表達(dá)式利用二叉樹化，然后通過中序遍歷的方式進(jìn)行提取，如果需要發(fā)生組合時(shí)，需要我們借助括號的形式表示優(yōu)先級，這樣也有一個(gè)弊端，就是當(dāng)多個(gè)嵌套的時(shí)候需要的括號較多。

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

簡介

• 后序遍歷：左右根

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

多個(gè)結(jié)點(diǎn)相互嵌套構(gòu)成的二叉樹如下圖所示，在訪問遍歷一開始的時(shí)候，先訪問左節(jié)點(diǎn)B再訪問右結(jié)點(diǎn)C最后訪問A；

由于B結(jié)點(diǎn)其中也包含了新的結(jié)點(diǎn)，在面對處理的結(jié)點(diǎn)后還存在有與之相聯(lián)的結(jié)點(diǎn)的時(shí)候，需要優(yōu)先處理其的子結(jié)點(diǎn)，這也是“遞歸”的基本思路；

因此，由于B屬于DG的根結(jié)點(diǎn)，相較于B，應(yīng)該先訪問D結(jié)點(diǎn)，而又由于D結(jié)點(diǎn)屬于EF的根結(jié)點(diǎn)，就又變成先訪問E結(jié)點(diǎn)，E屬于最末端了，根據(jù)后序遍歷左右根的訪問順序，依次生成EFDGB作為一個(gè)整體；

接著我們需要訪問C，由于C又是^HC之中的根結(jié)點(diǎn)，我們先訪問這個(gè)空結(jié)點(diǎn)，又因?yàn)槠涫且粋€(gè)空的結(jié)點(diǎn)，我們會跳過，就變成了HC的訪問順序；

最后在匯總的時(shí)候EFDGB作為左節(jié)點(diǎn)，HC作為右結(jié)點(diǎn)，A作為根結(jié)點(diǎn)，完成我們最終的遍歷順序EFDGBHCA。

代碼實(shí)現(xiàn)

//樹的后序遍歷?Post-order?traversal
void?postorder(Node*?node){
????if?(node?!=?NULL)
????{
????????inorder(node->left);
????????inorder(node->right);
????????printf("%d?",node->data);
????}
}

后綴表達(dá)式

后綴表達(dá)式與前綴表達(dá)式不同，前綴表達(dá)式采用先序遍歷的方式遍歷訪問我們的公式順序，常規(guī)式則就是中序方式，而后綴表達(dá)式采用后續(xù)遍歷的方式進(jìn)行訪問。

如圖，為常規(guī)表達(dá)式：(a+b)*c

其二叉樹的表現(xiàn)形式為：

而后綴表達(dá)式的表達(dá)方式就是ab+c* ，相較于前綴表達(dá)式，后綴表達(dá)式則就是將符號進(jìn)行后移，其在計(jì)算機(jī)中的讀取運(yùn)算概念也符合棧的思路，因此沒有什么特殊的不同。

總結(jié)

樹的概念還有很多，比如DFS（深度優(yōu)先搜索），森林與樹，哈夫曼樹等等，這里小編講一些樹的基礎(chǔ)，幫助大家入門了解。我們下一期，再見！

嵌入式編程專輯
Linux 學(xué)習(xí)專輯
C/C++編程專輯
Qt進(jìn)階學(xué)習(xí)專輯
關(guān)注微信公眾號『技術(shù)讓夢想更偉大』，后臺回復(fù)“m”查看更多內(nèi)容。

長按前往圖中包含的公眾號關(guān)注