15張圖來了解【樹】，面試再也不怕被刷了
我之前的文章
樹的概念
什么是樹？
樹屬于非線性數(shù)據(jù)結構的一種，概念也極多，是由結點或頂點和邊組成的且不存在著任何環(huán)的一種數(shù)據(jù)結構。
沒有結點的樹稱為空樹。一棵非空的樹包括一個根結點，還很可能有多個附加結點，并且所有結點構成一個多級分層結構。
樹的定義
n個節(jié)點組成的有限集合。n=0，空樹；n>0,1個根節(jié)點，m個互不相交的有限集，每個子集為根的子樹，如圖所示為一顆樹：
樹的基本術語
節(jié)點的度：樹中某個節(jié)點的子樹的個數(shù)。
樹的度：樹中各節(jié)點的度的最大值。
分支節(jié)點：度不為零的節(jié)點。
葉子節(jié)點：度為零的節(jié)點。
路徑：i->j；
路徑長度：路徑經(jīng)過節(jié)點數(shù)目減1。
孩子節(jié)點：某節(jié)點的后繼節(jié)點；
雙親節(jié)點：該節(jié)點為其孩子節(jié)點的雙親節(jié)點（父母節(jié)點）；
兄弟節(jié)點：同一雙親的孩子節(jié)點；
子孫節(jié)點：某節(jié)點所有子樹中的節(jié)點；
祖先節(jié)點：從樹節(jié)點到該節(jié)點的路徑上的節(jié)點；
節(jié)點的層次：根節(jié)點為第一層，以此類推；
樹的高度：樹中節(jié)點的最大層次；
有序樹：樹中節(jié)點子樹按次序從左向右安排，次序不能改變；
無序樹：與有序樹相反；
森林：互不相交的樹的集合。
樹的性質(zhì)
樹的節(jié)點樹為所有節(jié)點度數(shù)加1（加根節(jié)點）。
度為m的樹中第i層最多有
m^(i-1)個節(jié)點。高度為h的m次樹至多
(m^h-1)/(m-1)個節(jié)點。具有n個節(jié)點的m次樹的最小高度為
logm( n(m-1) + 1 )向上取整。
二叉樹
二叉樹簡介
二叉樹是n(n>=0)個結點的有限集合，每一個結點中最多擁有一個左結點和一個右結點，并且沒有多余的結點，如圖所示：
二叉樹的特點
根據(jù)二叉樹的定義以及圖示分析得出二叉樹有以下特點：
每個結點最多有兩顆子樹，不存在度大于2的結點。
左子樹和右子樹的次序不能任意顛倒。
即使樹中某結點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。
二叉樹的性質(zhì)
二叉樹具有以下幾種特征
二叉樹第i層上的結點數(shù)目最多為
2{i-1} (i≥1)。深度為k的二叉樹至多有
(2{k}-1)(k≥1)個結點。包含n個結點的二叉樹的高度至少為
log2 (n+1)。在任意一棵二叉樹中，若終端結點的個數(shù)為n0，度為2的結點數(shù)為n2，則
n0=n2+1。
幾種特殊的二叉樹
斜樹
所有的結點都只有左(右)子樹的二叉樹叫左(右)斜樹，統(tǒng)稱為斜樹，如圖所示：
滿二叉樹
在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹，其有以下特點
葉子只能出現(xiàn)在最下一層，否則就不可能達成平衡。
非葉子結點的度一定是2。
在同樣深度的二叉樹中，滿二叉樹的結點個數(shù)最多，葉子數(shù)最多。
完全二叉樹
一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。
二叉樹的存儲
簡介
以創(chuàng)建一顆二叉樹，并實現(xiàn)通過特定的插入順序和讀取順序達成讀取為順序為例子進行簡介。
結點設計
一顆二叉樹的結點設計一定要有如下內(nèi)容：
結點元素，data域，用來存儲數(shù)據(jù)；
左孩子結點，left指針，用來指向當前結點的下一層的左邊結點；
右孩子結點，right指針，用來指向當前結點的下一層的右邊結點；
除此之外，我們使用一棵樹的時候需要建立一顆樹根，由這個根，來進行逐步的向下構建，其代碼如下：
//樹的結點
typedef?struct?node{
????int?data;
????struct?node*?left;
????struct?node*?right;
}?Node;
//樹根
typedef?struct?{
????Node*?root;
}?Tree;
樹的創(chuàng)建
首先創(chuàng)建一個空的結點進行連接，將這個空的結點中的date域賦予數(shù)據(jù)，再判斷tree中是否是一個空樹，如果為空，只需要將整個根指向這一個結點即可，如果不為空，再進行兩個判斷，判斷輸入的數(shù)據(jù)是否大于或者小于當前比對的結點數(shù)據(jù)，根據(jù)其大小進行相應的排列，這樣存儲進入的數(shù)據(jù)總是有一定規(guī)律的，在輸出的時候根據(jù)這個規(guī)律進行輸出即可，其代碼可以顯示為：
//創(chuàng)建樹--插入數(shù)據(jù)
void?insert(Tree*?tree,?int?value){
????//創(chuàng)建一個節(jié)點，讓左右指針全部指向空，數(shù)據(jù)為value
????Node*?node=(Node*)malloc(sizeof(Node));
????node->data?=?value;
????node->left?=?NULL;
????node->right?=?NULL;
??
????//判斷樹是不是空樹，如果是，直接讓樹根指向這一個結點即可
????if?(tree->root?==?NULL){
????????tree->root?=?node;
????}?else?{//不是空樹
????????Node*?temp?=?tree->root;//從樹根開始
????????while?(temp?!=?NULL){
????????????if?(value?data){?//小于就進左兒子
????????????????if?(temp->left?==?NULL){
????????????????????temp->left?=?node;
????????????????????return;
????????????????}?else?{//繼續(xù)往下搜尋
????????????????????temp?=?temp->left;
????????????????}
????????????}?else?{?//否則進右兒子
????????????????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ù)結構中的所有數(shù)據(jù)全部依次訪問，而二叉樹需要通過在各節(jié)點與其孩子之間約定某種局部次序，間接地定義某種全局次序。
先序遍歷：根左右
先序遍歷：
先序遍歷就是在訪問二叉樹的結點的時候采用，先根，再左，再右的方式，對于一個最簡單的訪問而言如下圖，先序遍歷的訪問順序就是A，B，C
多個結點相互嵌套構成的二叉樹如圖所示，在訪問遍歷一開始的時候，先訪問根結點A，次訪問左節(jié)點B，由于左結點中嵌套了一組結點，因此左節(jié)點又作為下一個結點的根結點。
繼續(xù)沿著B訪問到了D，同樣由于D中包含了一組新的結點，D又作為根節(jié)點繼續(xù)訪問，就又訪問到了E，由于E沒有后面的結點了，作為D為根的左結點E訪問結束后，訪問到F，這一組訪問結束之后再回退訪問G，那么這一個二叉樹的先序遍歷訪問順序就是：ABDEFGCH
代碼實現(xiàn)
//樹的先序遍歷?Preorder?traversal
void?preorder(Node*?node){
????if?(node?!=?NULL)
????{
????????printf("%d?",node->data);
????????inorder(node->left);
????????inorder(node->right);
????}
}
擴展->前綴表達式
我們?nèi)粘５倪\算表達式通常是如下形式，這種成為中綴表達式，也就是運算符在運算數(shù)的中間，如圖，為常規(guī)表達式：(a+b)*c
其二叉樹的表現(xiàn)形式為：
而前綴表達式的表達方式就是 *+cab ，它的一個特征就是符號遷移，常規(guī)的表達式是需要大量的括號表達先后順序的，而這樣的表達式表達形式不需要，更容易讓計算機處理。
我們常規(guī)的表達式的計算是中序的，而計算機更方便對前綴表達式這樣的方式進行理解，進行這樣的轉(zhuǎn)換首先思路要進行轉(zhuǎn)換。
在代碼中我們實現(xiàn)這樣的轉(zhuǎn)換一般可以利用棧，熟練書些這樣的轉(zhuǎn)換就需要STL的掌握。
樹的遍歷之中序遍歷二叉樹
簡介
中序遍歷：左根右
如下圖，就一個最簡單的二叉樹遍歷而言，中序遍歷的遍歷訪問過程是先B再A再C。
多個結點構成的如圖所示，進行第一次訪問的時候，我們在ABC中進行遍歷，由左根右的順序，我們遍歷訪問到B，B同時又作為BDG的根結點，因此需要繼續(xù)向下進行遍歷。
此時我們遍歷到DEF，這時E屬于這一組之中的左結點，因此我們根據(jù)根左右的先后順序得到了最先的遍歷效果，EDF。
這EDF同時作為BDG中的左節(jié)點（把EDF看作一個整體）進行回溯，此時的訪問的結點順序為EDFBG。
同理EDFBG作為ABC的左結點根據(jù)左根右的順序EDFBGAC，左半部分訪問完畢接著訪問右半部分，我們將^CH（^表示空）看作一組左中右，而C就是由EDFBGAC組合而成，因此最終的遍歷順序為：EDFBGACH
代碼實現(xiàn)
//樹的中序遍歷?In-order?traversal
void?inorder(Node*?node){
????if?(node?!=?NULL)
????{
????????inorder(node->left);
????????printf("%d?",node->data);
????????inorder(node->right);
????}
}
中綴表達式（常規(guī)算式）
中綴表達式是一個通用的算術或邏輯公式表示方法。中綴表達式就是我們最常用的表達式形式，也是人最容易理解的表達式形式。
如圖，為常規(guī)表達式：(a+b)*c
其二叉樹的表現(xiàn)形式為：
由前文可知前綴表達式的表達方式就是 *+cab ，我們常規(guī)的表達式的計算是中序的，其表達式就是(a+b)*c。
我們可以理解為將表達式利用二叉樹化，然后通過中序遍歷的方式進行提取，如果需要發(fā)生組合時，需要我們借助括號的形式表示優(yōu)先級，這樣也有一個弊端，就是當多個嵌套的時候需要的括號較多。
樹的遍歷之后序遍歷二叉樹
簡介
后序遍歷：左右根
后序遍歷就是在訪問二叉樹的結點的時候采用，先左，再右，再根的方式，對于一個最簡單的訪問而言如圖，先訪問左節(jié)點B，之后訪問右結點C，最后訪問根節(jié)點A，后序遍歷的訪問順序就是BCA
多個結點相互嵌套構成的二叉樹如下圖所示，在訪問遍歷一開始的時候，先訪問左節(jié)點B再訪問右結點C最后訪問A；
由于B結點其中也包含了新的結點，在面對處理的結點后還存在有與之相聯(lián)的結點的時候，需要優(yōu)先處理其的子結點，這也是“遞歸”的基本思路；
因此，由于B屬于DG的根結點，相較于B，應該先訪問D結點，而又由于D結點屬于EF的根結點，就又變成先訪問E結點，E屬于最末端了，根據(jù)后序遍歷左右根的訪問順序，依次生成EFDGB作為一個整體；
接著我們需要訪問C，由于C又是^HC之中的根結點，我們先訪問這個空結點，又因為其是一個空的結點，我們會跳過，就變成了HC的訪問順序；
最后在匯總的時候EFDGB作為左節(jié)點，HC作為右結點，A作為根結點，完成我們最終的遍歷順序EFDGBHCA。
代碼實現(xiàn)
//樹的后序遍歷?Post-order?traversal
void?postorder(Node*?node){
????if?(node?!=?NULL)
????{
????????inorder(node->left);
????????inorder(node->right);
????????printf("%d?",node->data);
????}
}
后綴表達式
后綴表達式與前綴表達式不同，前綴表達式采用先序遍歷的方式遍歷訪問我們的公式順序，常規(guī)式則就是中序方式，而后綴表達式采用后續(xù)遍歷的方式進行訪問。
如圖，為常規(guī)表達式：(a+b)*c
其二叉樹的表現(xiàn)形式為：
而后綴表達式的表達方式就是ab+c* ，相較于前綴表達式，后綴表達式則就是將符號進行后移，其在計算機中的讀取運算概念也符合棧的思路，因此沒有什么特殊的不同。
總結
樹的概念還有很多，比如DFS（深度優(yōu)先搜索），森林與樹，哈夫曼樹等等，這里小編講一些樹的基礎，幫助大家入門了解。我們下一期，再見！
#推薦閱讀： ? ??專輯|Linux文章匯總 ? ??專輯|程序人生 ? ??專輯|C語言
嵌入式Linux 微信掃描二維碼，關注我的公眾號?
