考點6 樹和二叉樹

1.樹的基本概念

樹是一種簡單的非線性結(jié)構(gòu)，直觀地來看樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹是由n（n≥0）個節(jié)點構(gòu)成的有限集合，當(dāng)n=0時，樹稱為空樹。當(dāng)n≠0時，樹中的節(jié)點應(yīng)該滿足以下兩個條件：

●有且僅有一個沒有前驅(qū)的節(jié)點稱之為根；

●其余節(jié)點分成m（m＞0）個互不相交的有限集合 T1,T2,…,Tm，其中每一個集合又都是一棵樹，稱T1,T2,…,Tm為根節(jié)點的子樹。

在樹的結(jié)構(gòu)中主要涉及下面幾個概念。

●每一個節(jié)點只有一個前件，稱為父節(jié)點，沒有前件的節(jié)點只有一個，稱為樹的根節(jié)點，簡稱樹的根。

●每一個節(jié)點可以有多個后件，稱為該節(jié)點的子節(jié)點。沒有后件的節(jié)點稱為葉子節(jié)點。

●一個節(jié)點所擁有的后繼個數(shù)稱為該節(jié)點的度。

●所有節(jié)點最大的度稱為樹的度。

●樹的最大層次稱為樹的深度。

2.二叉樹及其基本性質(zhì)

（1）二叉樹的定義。

二叉樹是一種非線性結(jié)構(gòu)，是一個有限的節(jié)點集合，該集合或者為空，或者由一個根節(jié)點及其兩棵互不相交的左右二叉子樹所組成。當(dāng)集合為空時，稱該二叉樹為空二叉樹。

二叉樹具有以下特點。

●二叉樹可以為空，空的二叉樹沒有節(jié)點，非空二叉樹有且只有一個根節(jié)點。

●每一個節(jié)點最多有兩棵子樹，且分別稱為該節(jié)點的左子樹與右子樹。

（2）滿二叉樹和完全二叉樹。

滿二叉樹：除最后一層外，每一層上的所有節(jié)點都有兩個子節(jié)點，即在滿二叉樹的第k層上有2k-1個節(jié)點，且深度為m的滿二叉樹中有2m-1個節(jié)點。

完全二叉樹：除最后一層外，每一層上的節(jié)點數(shù)都達到最大值；在最后一層上只缺少右邊的若干節(jié)點。

滿二叉樹與完全二叉樹的關(guān)系：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

真考鏈接

考核概率為100%，本節(jié)內(nèi)容屬于必考知識點，特別是關(guān)于二叉樹的遍歷。考生要熟記該考點內(nèi)容，尤其是二叉樹的概念及其相關(guān)術(shù)語，并掌握二叉樹的性質(zhì)以及二叉樹的3種遍歷方法。本知識點是數(shù)據(jù)結(jié)構(gòu)的重要部分。

（3）二叉樹的主要性質(zhì)。

●一棵非空二叉樹的第k層上最多有2k-1個節(jié)點（k≥1）。

●深度為m的滿二叉樹中有2m-1個節(jié)點。

●對任何一棵二叉樹，度為0的節(jié)點（即葉子節(jié)點）總是比度為2的節(jié)點多一個。

●具有n個節(jié)點的完全二叉樹的深度k為［log2n］+1。

3.二叉樹的存儲結(jié)構(gòu)

在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，用于存儲二叉樹中各元素的存儲節(jié)點由數(shù)據(jù)域和指針域組成。由于每一個元素可以有兩個后件（即兩個子節(jié)點），所以用于存儲二叉樹的存儲節(jié)點的指針域有兩個：一個指向該節(jié)點的左子節(jié)點的存儲地址，稱為左指針域；另一個指向該節(jié)點的右子節(jié)點的存儲地址，稱為右指針域。因此，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。

對于滿二叉樹與完全二叉樹可以按層次進行順序存儲。

4.二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有節(jié)點。二叉樹的遍歷主要是針對非空二叉樹的，對于空二叉樹，則結(jié)束返回。

二叉樹的遍歷有前序遍歷、中序遍歷和后序遍歷。

（1）前序遍序（DLR）。

首先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。

（2）中序遍歷（LDR）。

首先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。

（3）后序遍歷（LRD）。

首先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。

小提示

已知一棵二叉樹的前序遍歷序列和中序遍歷序列，可以唯一確定這棵二叉樹。已知一棵二叉樹的后序遍歷序列和中序遍歷序列，也可以唯一確定這棵二叉樹。已知一棵二叉樹的前序遍歷序列和后序遍歷序列，不能唯一確定這棵二叉樹。

真題精選

對如右圖中二叉樹進行后序遍歷的結(jié)果為______。

A）ABCDEF

B）DBEAFC

C）ABDECF

D）DEBFCA

【答案】D

【解析】執(zhí)行后序遍歷，依次執(zhí)行如下操作：

①按照后序遍歷的順序遍歷根節(jié)點的左子樹；

②按照后序遍歷的順序遍歷根節(jié)點的右子樹；

③訪問根節(jié)點。