建站
咨詢
售后
建站咨詢
新聞中心
0. 前言
到目前為止，我們已經講述了順序表、鏈表、棧、隊列四種數據結構，它們有一個共同的特點，就是它們都是線性表，換句話來說，它們都是線性結構，像一根繩子一樣。
創(chuàng)新互聯(lián)-專業(yè)網站定制、快速模板網站建設、高性價比燈塔網站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式燈塔網站制作公司更省心,省錢,快速模板網站建設找我們，業(yè)務覆蓋燈塔地區(qū)。費用合理售后完善，10多年實體公司更值得信賴。
四種線性數據結構
在文章【線性表】已經介紹過線性表的定義了，即由若干元素按照線性結構(一對一的關系)組成的有限序列。
關鍵詞是一對一的關系。
顯然，在復雜的現(xiàn)實社會中，這種一對一的關系是不能較好的滿足我們的需求的。
比如說，父母和多個孩子之間的關系，一個父親/母親對應多個孩子，這顯然不是一對一，而是一對多的關系。那么此時我們如何來描述這種一對多的關系呢?
當然是使用具有一對多關系的數據結構啦!有這種數據結構嗎?有!本文就來介紹這種數據結構 —— 樹及其特殊形式的二叉樹。
1. 識樹
1.0. 什么是樹?
提到樹(Tree)，大家腦海中首先浮出的畫面應該是類似這樣的：
圖片來自網絡
之所以我們會用“樹”這個名詞來命名具有“一對多關系”特性的數據結構，是因為樹剛好能夠很形象地詮釋這種特性。我們來分析一下。
看一下上圖中的樹(土地以上的部分)，它有一個樹根，從樹根開始往上分叉，主樹干分叉成許多次樹干，次樹干又繼續(xù)分叉為許多小樹枝，小樹枝上有許多葉子……
主樹干對次樹干、次樹干對小樹枝、小樹枝對葉子都是一對多的關系，我們用圓圈代表樹干和葉子，把自然界的樹倒過來進行一次抽象，得下圖(為了方便起見，我們的數據全為字符類型)：
一棵樹
可以看到，現(xiàn)實中的樹完美契合我們需要的數據結構，所以我們稱這種數據結構為樹(Tree)。
1.1. 名詞與概念
我們按圖索驥，來認識樹的相關名詞。
子樹：樹是一個有限集合，子樹則是該集合的子集。就像套娃一樣，一棵樹下面還包含著其子樹。
比如，樹T1 的子樹為 樹T2、T3、T4，樹T2的子樹為 T5、T6. 上圖中還有許多子樹沒有標記出來。
結點(Node)：一個結點包括一個數據元素和若干指向其子樹分支。
比如，在樹T1 中，結點A 包括一個數據元素A 和 三個指向其子樹的分支。上圖中共有 17 個結點。
根結點(Root)：一顆樹只有一個樹根，這是常識。在數據結構中，“樹根”即根節(jié)點。
比如，結點A 是樹 T1 的根結點;結點C 是樹T1 的子結點，是樹 T3 的根結點。
度(Degree)：一個結點擁有的子樹數。
比如，結點A 的度為 3，結點G 的度為 3，結點H 的度為 1.
葉子(Leaf)/ 終端結點：度為 0 的結點被稱為葉子結點，很形象吧。
比如，對于樹 T1來說，結點F、I、K、L、M、N、O、P、Q 均為葉子。
分支結點 / 非終端結點：和葉子結點相對，即度不為 0 的結點。
內部結點：顧名思義，在樹內部的結點，即不是根結點和葉子結點的結點。
孩子(Child)、雙親(Parent)、兄弟(Sibling)、堂兄弟、祖先、子孫這些概念和族譜上的相同。
比如，對于結點B 來說：結點A 是其雙親結點，結點E、F 是其孩子結點，結點C、D 是其兄弟結點，結點K 是其子孫結點。
層次(Level)：從根結點開始，根為第一次，根的孩子為第二層，依次往下。
比如，結點K 在樹 T1 中的層次為 4.
深度(Depth)/ 高度：指樹的最大層次。
比如，樹 T1 的深度為 4.
有序樹：如果結點的各子樹從左到右是有次序的、不能顛倒，則為有序樹，否則為無序樹。對于有序樹的孩子來說，最左邊的孩子稱為第一個孩子，最右邊的孩子稱為最后一個孩子。
比如，如果樹T1是一個有序樹，則其根結點的第一個孩子為結點B，最后一個孩子為結點D.
1.2. 樹的遞歸概念
前面已經介紹了樹的輪廓和相關名詞概念，為了回答什么是樹這個問題，我們這里還需要介紹三種常見的樹結構。
【空樹】：一顆空樹，即沒有結點的樹。
空樹
【只有根結點的樹】：只有一個根節(jié)點，沒有其他結點。
只有根結點的樹
【普通的樹】
普通樹
現(xiàn)在我們能來回答什么是樹了：
樹(Tree)是由 N (N >= 0) 個結點構成的有限集合。
- 當 N = 0 時，樹為空樹
- 當 N = 1 時，樹只有一個根結點
- 當 N > 1 時，樹除了一個根結點外，其余結點又可分為若干個不相交的有限集合，我們稱之為子樹。
非空樹有且僅有一個根結點。
樹的一對多的關系存在于雙親結點和孩子結點之間。
在樹中，因為存在樹、子樹的概念，所以樹的子樹仍是一顆樹，子樹的子樹仍是一棵樹。
- 舉個例子：人類的孩子仍是人類，人類的孩子的孩子仍是人類。
因為存在雙親、孩子、子孫的概念，所以根結點的孩子結點可以其子樹的根結點。
- 舉個例子：一個人，在其孩子看來是父親，在其父母看來是兒子。
這種概念，就是遞歸的概念。
即，對于某個“事物”而言，它的“孩子”和它本身并無實質區(qū)別，它做的事，它的“孩子”也會做、也要做。一直向下，“孫子”“曾孫”“玄孫”皆是如此。
為了說明遞歸這個概念，我們將上圖的樹遞歸地分解為子樹，下圖中每個區(qū)域都是一顆樹(或子樹)：
遞歸解樹
分解到最后，我們最終得到的，可以說是葉子結點，也可以說是只有根結點的樹。如結點F、K、L.
在分解的過程中，我們還可以發(fā)現(xiàn)，對于每個結點來說，我們都可以將其看作某棵樹(子樹)的根結點。比如結點E、I都是某棵子樹的根結點。這與樹有且只有一個根結點并不矛盾。
- 這就好比我們說，小明只能有一個親生父親，但不影響他成為別人的父親。
整個過程就像在族譜上從祖宗找到子孫一樣。所以如果對樹的概念有啥不了解的，可以找個族譜翻翻看。
到此，我們可以說，樹的定義是一個遞歸的定義，樹是由根結點和它的若干子樹組成的，子樹也是由根結點和它的若干子樹組成的……即在樹的定義中又用到樹的定義。
1.3. 樹和線性表的比較
比較
看圖直觀體驗何為(前驅結點和后繼結點間)一對一的關系，何為(雙親結點和孩子結點之間)一對多的關系。
2. 識二叉樹
2.0. 什么是二叉樹?
何為二叉樹?首先它得是顆樹，其次它得是二叉的。
前面已經初步認識了樹，它的結點的孩子數量是沒有限制的，即，你想要幾個孩子就要幾個孩子，想分幾個叉就分幾個叉。
而二叉樹，則是限制了孩子數量，即每個結點最多只能有兩個孩子(左孩子和右孩子)，打個比方就是“二胎樹”。
二叉樹
結點A 的左孩子是結點B，右孩子是結點C.
二叉樹是一種每個結點至多有兩棵子樹(即每個結點的度最大為 2 )的有序樹。
2.1. 二叉樹的幾種形態(tài)
一、空二叉樹
二、僅有根結點的二叉樹
三、左子樹為空的二叉樹
四、右子樹為空的二叉樹
五、左右子樹都不為空的二叉樹
2.2. 滿二叉樹和完全二叉樹
滿二叉樹的特點在于“滿”，即每層的結點數都是最大結點數。
滿二叉樹
T2 的第 3 層次沒有達到最大結點數，缺了 1 個;T3 的第 4 層次沒有達到最大結點數，缺了 7 個。
完全二叉樹是相對于滿二叉樹來說的，見下圖：
紅色部分為編號
二叉樹是有序樹，對一顆滿二叉樹和一顆完全二叉樹按「自上向下，自左向右」的順序進行編號，如上圖。
完全二叉樹中的所有結點的編號必須和滿二叉樹的相同編號的結點在位置上完全相同。
換句話說，完全二叉樹的結點按「自上向下，自左向右」的順序不能中斷。T3 的結點C 沒有左孩子，顯然按那個順序是中斷的。
3. 二叉樹的遍歷
3.0. 如何遍歷?
在線性表中，我們的遍歷非常簡單粗暴，找到線性表頭，使用循環(huán)直接一股腦的到線性表尾，即完成遍歷了。在樹中，我們不能在做這么簡單粗暴的事了，因為樹是一對多的關系，所以從頭到尾的遍歷是不可能的。
遍歷的實質是，將線性排列的元素順序打印出來。(遍歷不止干打印的事，為了方便起見，我們的遍歷是打印元素)
而遍歷樹的矛盾在于，我們的樹不是線性的，為了解決這個矛盾，我們可不可以約定好某種順序，將樹的元素按這種順序線性排列起來，然后遍歷就是從頭到尾的簡單粗暴之事了?答案是可以的。
我們知道樹是遞歸的定義，二叉樹是由根結點、左子樹、右子樹這三部分遞歸地組合而成的。 所以我們要約定的就是這三部分誰先誰后。
按照人們寫字先左后右的約定，我們也約定先左子樹后右子樹的順序(當然你可以先右后左)，那么根結點就只有三個位置可以放了。
根結點 >> 左子樹 >> 右子樹，稱為先序(根)遍歷
左子樹 >> 根結點 >> 右子樹，稱為中序(根)遍歷
左子樹 >> 右子樹 >> 根結點，稱為后序(根)遍歷
約定好之后，只需要按照順序遞歸地來就好了，就像找族譜一樣。
下面以遍歷下圖二叉樹為例：
為了方便起見，我們將 null 畫出來，且將所有子樹用顏色標志出來。
3.1. 先序遍歷
先序遍歷的遞歸描述如下：
若二叉樹為空，則空操作;否則：
- 訪問根結點
- 先序遍歷左子樹
- 先序遍歷右子樹
你可能會問，怎么只有訪問根結點這一步?左孩子和右孩子結點呢?前面說過一句話：對于每個結點來說，我們都可以將其看作某棵樹(子樹)的根結點。就像你的兒子會成為別人的父親一樣。所以只要遞歸地訪問根結點，將每個結點遞歸地變?yōu)椤案Y點”，我們就能完成遍歷。
所以與其說是在遍歷結點，不如說是在遍歷「根結點」，我們只是在遞歸地把「所有根結點」找出來并輸出而已。(因為每個結點都可以看做是根結點)
所以遍歷的重點，在于將所有結點轉化為根結點看待，又因為每棵樹有且僅有一個根結點，所以我們要不斷地遞歸分解子樹(先左子樹后右子樹)，直到分解到 NULL為止。
過程如下：
先序遍歷的順序為：A B D E G C F
如果你感覺文字描述不直觀，可以在我以前寫過的文章中找到二叉樹遍歷過程的動態(tài)圖[1]。
3.2. 中序遍歷
中序遍歷的遞歸描述如下：
若二叉樹為空，則空操作;否則：
中序遍歷左子樹
訪問根結點
中序遍歷右子樹
過程如下：
中序遍歷的順序為：D B G E A C F
3.3. 后序遍歷
后序遍歷的遞歸描述如下：
若二叉樹為空，則空操作;否則：
- 后序遍歷左子樹
- 后序遍歷右子樹
- 訪問根結點
過程不再描述，后序遍歷的順序為：D G E B F C A
4. 總結
概念和原理是進行實踐的基礎，如果這些不了解，那么代碼實現(xiàn)就無從下手。
二叉樹的概念和原理先介紹到這里。
參考資料
[1]二叉樹遍歷過程的動態(tài)圖:
https://blog.csdn.net/m0_47335900/article/details/106157797
[2]GitHub:
https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo
[3]Gitee:
https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo
本文標題：【數據結構之二叉樹】二叉樹的相關概念及原理
瀏覽路徑：http://m.5511xx.com/article/dhhjpcp.html
