1.6　樹與二叉樹

考點1　樹的基本概念

（1）樹是一種簡單的非線性結構，在這種結構中，所有數據元素之間的關系具有明顯的層次特性。在樹的圖形表示中，上端結點是前件，下端結點是后件。

（2）在樹結構中，每個結點只有一個前件（父結點），沒有前件的結點只有一個，稱為樹的根結點。每個結點都可以有多個后件（子結點），沒有后件的結點稱為葉子結點。

（3）一個結點擁有的后件個數稱為該結點的度。某結點的度為n，表示該結點有n個分支，每個分支指向一個后件，除根結點外，每個結點都有一個唯一的分支指向它。樹中的結點數為樹中所有結點的度之和再加1。

（4）根結點在第1層，同一層上所有結點的所有子結點都在下一層，樹的最大層次稱為樹的深度

（5）在樹中，葉子結點沒有子樹。

（6）用樹來表示算術表達式的原則：

①表達式中的每一個運算符在樹中對應一個結點，稱為運算符結點；

②運算符的每一個運算對象在樹中為該運算符結點的子樹（在樹中的順序為從左到右）；

③運算對象中的單變量均為葉子結點。

在樹中，葉子結點沒有子樹。

【真題演練】

1下列數據結構中，屬于非線性結構的是（　　）。[2013年3月真題]

A．循環隊列

B．帶鏈隊列

C．二叉樹

D．帶鏈棧

【答案】C

【解析】線性結構要滿足兩個條件：①有且僅有一個根結點；②每個結點最多有一個前驅，也最多有一個后繼。棧和隊列均滿足這兩個條件，屬于線性結構；循環隊列是一個頭結點和尾結點互為前驅結點和后繼結點的特殊的隊列，屬于線性結構；帶鏈隊列、帶鏈棧都是用鏈表形式來實現的，分別滿足隊列和棧的條件，只是存儲結構不連續，屬于線性結構。二叉樹除了葉子結點外，每個結點都可以有兩個后繼結點，屬于非線性結構。答案選擇C選項。

2某二叉樹的中序序列為DCBAEFG，后序序列為DCBGFEA，則該二叉樹的深度（根結點在第1層）為（　　）。[2015年3月真題]

A．5

B．4

C．3

D．2

【答案】B

【解析】二叉樹的后序序列為DCBGFEA，則A為根結點。中序序列為DCBAEFG，則DCB為左子樹結點，EFG為右子樹結點。同理B為C父結點，C為D父結點。根據分析，可畫出左子樹，同理E為F父結點，F為G父結點。根據分析，可畫出右子樹，易知二叉樹深度為4層。答案選擇B選項。

考點2　二叉樹及其基本性質

（1）二叉樹定義

二叉樹是一種很有用的非線性結構，與樹結構很相似，樹結構的所有術語都可以用到叉樹這種數據結構上。

（2）二叉樹的兩個特點

①非空二叉樹只有一個根結點；

②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。

（3）二叉樹的基本性質

①在二叉樹的第k層上，最多有2^k－1（k≥1）個結點。

②深度為m的二叉樹最多有2^m－1個結點。

③在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。

④具有n個結點的二叉樹，其深度至少為[log₂n]＋1，其中[[log₂n]表示取log₂n的整數部分。

（4）滿二叉樹與完全二叉樹

滿二叉樹與完全二叉樹是兩種特殊形態的二叉樹。

①滿二叉樹

除最后一層外，每一層上的所有結點都有兩個子結點。

②完全二叉樹

a．除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。

b．更確切地說，如果從根結點起，對二叉樹的結點自上而下、自左至右用自然數進行連續編號，則深度為m、且有n個結點的二叉樹，當且僅當其每一個結點都與深度為m的滿二叉樹中編號從1到n的結點一一對應時，稱之為完全二叉樹。

對于完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現；對于任何一個結點，若其右分支下的子孫結點的最大層次為P，則其左分支下的子孫結點的最大層次或為P，或為p＋1。

c．滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。

完全二叉樹具有以下兩個性質：

a．具有n個結點的完全二叉樹的深度為[log₂n]＋1。

b．設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，…，n給結點進行編號，則對于編號為k（k＝1，2，…，n）的結點有以下結論：

第一，若k＝1，則該結點為根結點，它沒有父結點；若k＞1，則該結點的父結點編號為INT（k/2）。

第二，若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。

第三，若2k＋1≤n，則編號為k的結點的右子結點編號為2k＋1；否則該結點無右子結點。

根據完全二叉樹的這個性質，如果按從上到下、從左到右順序存儲完全二叉樹的各結點，則很容易確定每一個結點的父結點、左子結點和右子結點的位置。

【真題演練】

1某二叉樹共有13個結點，其中有4個度為1的結點，則葉子結點數為（　　）。[2014年3月真題]

A．5

B．4

C．3

D．2

【答案】A

【解析】對任何一棵二叉樹來說，度為0的結點，即葉子結點，總是比度為2的結點多一個。所以可設葉子結點個數為n，則度為2的結點個數為n-1。13=n+4+n-1，得n=5。答案選擇A選項。

2某二叉樹中有15個度為1的結點，16個度為2的結點，則該二叉樹中總的結點數為（　　）。[2014年9月真題]

A．32

B．46

C．48

D．49

【答案】C

【解析】在樹結構中，一個結點所擁有的后繼個數稱為該結點的度。由二叉樹的基本性質可得，對于任何的二叉樹，葉子結點總是比度為2的結點多一個。因為度為2的結點有16個，所以葉子結點個數為17，因此結點總數為16+17+15=48。答案選擇C選項。

3某二叉樹中共有935個結點，其中葉子結點有435個，則該二叉樹中度為2的結點個數為（　　）。[2014年3月真題]

A．64

B．66

C．436

D．434

【答案】D

【解析】在樹結構中，一個結點所擁有的后件個數稱為該結點的度。對于任何一棵二叉樹來說，度為0的結點總是比度為2的結點多一個。葉子結點有435個，則度為2的結點為434。答案選擇D選項。

4深度為7的完全二叉樹中共有125個結點，則該完全二叉樹中的葉子結點數為（　　）。[2014年9月真題]

A．62

B．63

C．64

D．65

【答案】B

【解析】定義一棵樹的根結點所在的層次為1，其他結點所在的層次等于它的父結點所在的層次加1，樹的最大層次稱為樹的深度。完全二叉樹指除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干結點。本題中，前6層是滿二叉樹，結點個數為26-1=63，所以第7層有125-63=62個葉子結點，分別掛在第6層的左邊62個結點上，所以第6層的最后1個結點為葉子結點，該完全二叉樹共有62+1=63個葉子結點。答案選擇B選項。

考點3　二叉樹的存儲結構

（1）在計算機中，二叉樹采用鏈式存儲結構。

（2）用于存儲二叉樹中各元素的存儲結點由兩部分組成：

①數據域

②指針域

a．左指針：用于指向該結點的左子結點的存儲地址；

b．右指針：指向該結點的右指結點的存儲地址。

【真題演練】

下列敘述中正確的是（　　）。[2014年9月真題]

A．結點中具有兩個指針域的鏈表一定是二叉鏈表

B．結點中具有兩個指針域的鏈表可以是線性結構，也可以是非線性結構

C．二叉樹只能采用鏈式存儲結構

D．循環鏈表是非線性結構

【答案】B

【解析】A項錯誤，具有兩個指針域的鏈表可能是雙向鏈表；B項正確，如雙向鏈表是線性結構，二叉樹為非線性結構，兩者結點中均有兩個指針域；C項錯誤，二叉樹通常采用鏈式存儲結構，也可采用其他結構；D項錯誤，循環鏈表是線性結構，邏輯概念線性非線性與實際存儲結構無關。答案選擇B選項。

考點4　二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。在遍歷二叉樹結點中遵循先左后右的原則。二叉樹的遍歷可分為三種：

（1）前序遍歷（DLR）

在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。該過程是一個遞歸的過程。

（2）中序遍歷（LDR）

在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。因此，中序遍歷二叉樹的過程也是一個遞歸的過程。

（3）后序遍歷（LRD）

在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。因此，后序遍歷二叉樹的過程也是一個遞歸的過程。

如果知道了某二叉樹的前序序列和中序序列，則可以唯一地恢復該二叉樹，如果知道了某二叉樹的后序序列和中序序列，則也可以唯一地恢復該二叉樹。但如果只知道某二叉樹的前序序列和后序序列，是不能唯一恢復該二叉樹的。

【真題演練】

1設二叉樹如下：

則后序遍歷為（　　）。[2014年9月真題]

A．ABDEGCFH

B．DBGEAFHC

C．DGEBHFCA

D．ABCDEFGH

【答案】C

【解析】后序遍歷，先訪問左子樹，再訪問右子樹，最后訪問根結點。法一：本題中，樹不為空，所以先后序遍歷左子樹，得DGEB，再后序遍歷右子樹，得HFC，最后訪問根結點。所以該二叉樹的后序序列為DGEBHFCA。法二：由后序遍歷的過程知，樹的根結點一定是最后遍歷到，即A結點一定在遍歷序列的最后，答案選擇C選項。

2某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為（　　）。[2014年9月真題]

A．BADC

B．DCBA

C．CDAB

D．ABCD

【答案】B

【解析】由前序序列ABCD得A為根結點，又因為中序序列為DCBA，所以DCB是A的左子樹。同理可得B是CD的根結點，DC是B的左子樹，C是D的根結點，所以可以確定二叉樹的形狀，得后序序列為DCBA。答案選擇B選項。