資源簡(jiǎn)介

專題15　樹(shù)
學(xué)業(yè)要求 知　識(shí)　點(diǎn) 學(xué)業(yè)水平等級(jí)
1.抽象二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)形式，掌握二叉樹(shù)的概念及性質(zhì) 3
2.通過(guò)數(shù)組和鏈表實(shí)現(xiàn)樹(shù)的創(chuàng)建，理解數(shù)組和鏈表相應(yīng)位置的方法 4
3.掌握前序遍歷、中序遍歷和后序遍歷等規(guī)則 4
知識(shí)點(diǎn)一　樹(shù)的性質(zhì)
【知識(shí)梳理】
1.________可以描述為由n(n≥0)個(gè)節(jié)點(diǎn)(Node)構(gòu)成的一個(gè)有限集合以及在該集合上定義的一種節(jié)點(diǎn)關(guān)系。
2.集合中的元素稱為樹(shù)的________，n＝0的樹(shù)稱為_(kāi)_______；樹(shù)中某個(gè)節(jié)點(diǎn)下面的所有節(jié)點(diǎn)所構(gòu)成的樹(shù)稱為該節(jié)點(diǎn)的________。
3.樹(shù)的兩個(gè)節(jié)點(diǎn)之間如果有一條邊連接，那么稱這兩個(gè)節(jié)點(diǎn)之間存在一條________，對(duì)于一棵具有n個(gè)節(jié)點(diǎn)的樹(shù)，它有n－1條邊。
4.樹(shù)的一個(gè)節(jié)點(diǎn)所擁有的子樹(shù)個(gè)數(shù)稱為該節(jié)點(diǎn)的________，最大的節(jié)點(diǎn)的度稱為樹(shù)的度。線性表是度為1的特殊樹(shù)狀結(jié)構(gòu)。
5.在樹(shù)狀結(jié)構(gòu)中，沒(méi)有前驅(qū)節(jié)點(diǎn)的稱為_(kāi)_______，又稱為開(kāi)始節(jié)點(diǎn)。度為0的節(jié)點(diǎn)稱為_(kāi)_______，也稱為終端節(jié)點(diǎn)。
6.在樹(shù)形結(jié)構(gòu)中，對(duì)于兩個(gè)以邊直接連接的節(jié)點(diǎn)，上端節(jié)點(diǎn)稱為下端節(jié)點(diǎn)的________或雙親節(jié)點(diǎn)(Parent)。相應(yīng)地，下端節(jié)點(diǎn)稱為上端節(jié)點(diǎn)的孩子節(jié)點(diǎn)(Child)。
7.樹(shù)中節(jié)點(diǎn)的________從根開(kāi)始計(jì)算，根的層數(shù)為1，其余節(jié)點(diǎn)的層數(shù)等于其父節(jié)點(diǎn)的層數(shù)加1。樹(shù)中節(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的________________。
8.________是一個(gè)具有n(n≥0)個(gè)節(jié)點(diǎn)的有限集合，它的所有節(jié)點(diǎn)的度都小于或等于2。當(dāng)n＝0時(shí)，二叉樹(shù)是一棵空樹(shù)；當(dāng)n不等于0時(shí)，它是一棵由根節(jié)點(diǎn)和兩棵互不相交的，分別稱作這個(gè)根節(jié)點(diǎn)的________和________組成的二叉樹(shù)。
9.____________至多只有最下面兩層中的節(jié)點(diǎn)度數(shù)小于2，且最下面一層的葉子節(jié)點(diǎn)都依次排列在該層的最左邊位置。
10.二叉樹(shù)的性質(zhì)：①二叉樹(shù)的第k層最多有________(k≥1)個(gè)節(jié)點(diǎn)；②深度為k的二叉樹(shù)最多有2k－1(k≥1)個(gè)節(jié)點(diǎn)；③在任意一棵二叉樹(shù)中，若度為2的節(jié)點(diǎn)數(shù)量為n2，葉子節(jié)點(diǎn)(度為0的節(jié)點(diǎn))數(shù)為n0，則n0＝n2＋1。
【經(jīng)典案例】
樹(shù)是n(n>＝0)個(gè)節(jié)點(diǎn)的有限集合，有且僅有一個(gè)稱為根的節(jié)點(diǎn)，沒(méi)有后繼的節(jié)點(diǎn)稱為“葉子節(jié)點(diǎn)”，有后繼的節(jié)點(diǎn)稱為“分支節(jié)點(diǎn)”，除了根節(jié)點(diǎn)外，任何一個(gè)節(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)，每個(gè)節(jié)點(diǎn)可以有0個(gè)或多個(gè)后繼，任何一個(gè)樹(shù)都可以被看作是由一個(gè)根節(jié)點(diǎn)和若干不相交的子樹(shù)組成的，因此樹(shù)是一種遞歸定義的數(shù)據(jù)結(jié)構(gòu)。
樹(shù)的屬性：節(jié)點(diǎn)的層次(深度)，從上往下數(shù)，默認(rèn)從1開(kāi)始。節(jié)點(diǎn)的高度，從下往上數(shù)，總共有多少層。節(jié)點(diǎn)的度指當(dāng)前節(jié)點(diǎn)有幾個(gè)孩子(分支)，樹(shù)的度指各節(jié)點(diǎn)的度的最大值。
【例1】 有一棵樹(shù)，節(jié)點(diǎn)的度和個(gè)數(shù)如下表所示。
度 0 1 2 3 4
節(jié)點(diǎn)個(gè)數(shù) x 4 3 2 1
則葉子節(jié)點(diǎn)x的個(gè)數(shù)為(　　)
A.8 B.9
C.10 D.11
思維點(diǎn)撥
精點(diǎn)撥 樹(shù)中所有節(jié)點(diǎn)的度之和加1為節(jié)點(diǎn)總數(shù)，因此1*4＋2*3＋3*2＋4*1＝21。節(jié)點(diǎn)數(shù)為x＋4＋3＋2＋1＝x＋10，因此可以得到葉子節(jié)點(diǎn)數(shù)為11個(gè)
聽(tīng)課筆記：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 已知一棵完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)為12，則有關(guān)該二叉樹(shù)的說(shuō)法正確的是(　　)
A.樹(shù)的度為12 B.樹(shù)的層數(shù)為3
C.葉子節(jié)點(diǎn)數(shù)為5 D.最后一層有5個(gè)節(jié)點(diǎn)
【例2】 已知一棵完全二叉樹(shù)有8個(gè)葉子節(jié)點(diǎn)，下列說(shuō)法正確的是(　　)
A.該完全二叉樹(shù)的高度最大為3
B.該完全二叉樹(shù)的形態(tài)只有一種
C.該完全二叉樹(shù)可能有1個(gè)度為1的節(jié)點(diǎn)
D.該完全二叉樹(shù)有9個(gè)度為2的節(jié)點(diǎn)
思維點(diǎn)撥
明考向 本題考查樹(shù)的性質(zhì)。根據(jù)樹(shù)的性質(zhì)，2度節(jié)點(diǎn)個(gè)數(shù)為葉子節(jié)點(diǎn)個(gè)數(shù)減1，因此2度節(jié)點(diǎn)有7個(gè)。由于是完全二叉樹(shù)，1度節(jié)點(diǎn)的個(gè)數(shù)為0或1，因此總共節(jié)點(diǎn)數(shù)為15或16個(gè)
精點(diǎn)撥 A 根據(jù)總共節(jié)點(diǎn)數(shù)，可知該樹(shù)可能是3層，也可以是4層
B 當(dāng)總節(jié)點(diǎn)是3層時(shí)，是一棵滿二叉樹(shù)，當(dāng)節(jié)點(diǎn)為16時(shí)，在4層下有一個(gè)節(jié)點(diǎn)
C 當(dāng)總節(jié)點(diǎn)為16時(shí)，有一個(gè)1度節(jié)點(diǎn)
D 2度節(jié)點(diǎn)個(gè)數(shù)為7個(gè)
聽(tīng)課筆記：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 已知完全二叉樹(shù)T共有78個(gè)節(jié)點(diǎn)，則其葉子節(jié)點(diǎn)數(shù)量為(　　)
A.15 B.32
C.39 D.40
知識(shí)點(diǎn)二　樹(shù)的遍歷
【知識(shí)梳理】
1.____________的操作，可以按照層的順序進(jìn)行，先由第1層開(kāi)始，依次到下一層，在每一層中按照從左到右的順序創(chuàng)建節(jié)點(diǎn)。二叉樹(shù)的建立可以用數(shù)組或者鏈表數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。
2.____________________，從根節(jié)點(diǎn)開(kāi)始，按從上而下、自左往右的順序?qū)個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為0，最后一個(gè)節(jié)點(diǎn)的編號(hào)為n－1。然后依次將二叉樹(shù)的節(jié)點(diǎn)用一組連續(xù)的數(shù)組元素來(lái)表示，節(jié)點(diǎn)編號(hào)與數(shù)組的下標(biāo)一一對(duì)應(yīng)。
3.________________________，先將它補(bǔ)全為一棵完全二叉樹(shù)，補(bǔ)上的節(jié)點(diǎn)及分支用虛線表示，數(shù)據(jù)存儲(chǔ)時(shí)對(duì)應(yīng)位置空缺，其它節(jié)點(diǎn)在數(shù)組中的位置參照完全二叉樹(shù)。
4.________________，每個(gè)節(jié)點(diǎn)至少需要3個(gè)域，一個(gè)數(shù)據(jù)域和兩個(gè)指針域。數(shù)據(jù)域用于存放本節(jié)點(diǎn)的數(shù)據(jù)信息，左右兩個(gè)指針域分別指向左右孩子節(jié)點(diǎn)。
5.________________，是指按照一定的規(guī)則和次序訪問(wèn)二叉樹(shù)中的所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)都被訪問(wèn)一次且僅被訪問(wèn)一次。
6.________，若二叉樹(shù)為空，則空操作返回；否則先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)。
7.________，若二叉樹(shù)為空，則空操作返回；否則先訪問(wèn)左子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。
8.________，若二叉樹(shù)為空，則空操作返回；否則先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。
【經(jīng)典案例】
二叉樹(shù)的建立可以用數(shù)組或者鏈表數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)時(shí)，需把二叉樹(shù)補(bǔ)全為一棵完全二叉樹(shù)，優(yōu)點(diǎn)是能快速地檢索到某個(gè)節(jié)點(diǎn)的值，如果根節(jié)點(diǎn)編號(hào)為1，則第i個(gè)節(jié)點(diǎn)的左孩子編號(hào)為2*i，右孩子編號(hào)為2*i＋1。缺點(diǎn)是當(dāng)這棵二叉樹(shù)不是完全二叉樹(shù)時(shí)，會(huì)造成存儲(chǔ)空間的浪費(fèi)。
二叉樹(shù)的遍歷實(shí)現(xiàn)用線性結(jié)構(gòu)來(lái)描述層次化、分支化的非線性結(jié)構(gòu)。二叉樹(shù)的遍歷是按照一定的規(guī)則和次序(先訪問(wèn)左節(jié)點(diǎn)，后訪問(wèn)右節(jié)點(diǎn))訪問(wèn)二叉樹(shù)中的所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)都被訪問(wèn)一次且僅被訪問(wèn)一次。一棵二叉樹(shù)必定先訪問(wèn)左節(jié)點(diǎn)，再訪問(wèn)右節(jié)點(diǎn)，將根節(jié)點(diǎn)所有位置分為前、中、后序三種遍歷方式。
【例1】 某二叉樹(shù)的樹(shù)形結(jié)構(gòu)如圖所示，其前序遍歷結(jié)果為BDEFCA，則中序遍歷結(jié)果為(　　)
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
思維點(diǎn)撥
明考向 本題考查二叉樹(shù)的遍歷
精點(diǎn)撥 前序遍歷可知B為二叉樹(shù)根節(jié)點(diǎn)，D和左子樹(shù)根節(jié)點(diǎn)，E和F為左子樹(shù)的左右孩子。C為F的左孩子，A為樹(shù)的右子樹(shù)。該樹(shù)結(jié)構(gòu)如圖所示。因此中序遍歷為EDCFBA
聽(tīng)課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 下列二叉樹(shù)中，中序遍歷結(jié)果為BAEDFC的是(　　)
【例2】 某二叉樹(shù)用一維數(shù)組來(lái)表示如下表所示。該二叉樹(shù)從根節(jié)點(diǎn)開(kāi)始，按照從上到下，從左到右的順序依次用A－H字母表示，該二叉樹(shù)的中序遍歷為(　　)
下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素 A B C D E F G H
A.DBGEACFH B.DBGEACHF
C.DBEGACHF D.ABCDEFGH
思維點(diǎn)撥
明考向 本題考查二叉樹(shù)的相關(guān)概念
精點(diǎn)撥 根據(jù)題意，可以構(gòu)建出如下圖的二叉樹(shù)。該樹(shù)的中序遍歷為DBGEACFH。
聽(tīng)課筆記：_____________________________________________________________
______________________________________________________________________
【變式2】 某表達(dá)式樹(shù)如圖所示，下列說(shuō)法錯(cuò)誤的是(　　)
A.該表達(dá)式樹(shù)是一棵二叉樹(shù)，樹(shù)的度是2，高度是5
B.該樹(shù)的葉子節(jié)點(diǎn)數(shù)比度為2的節(jié)點(diǎn)數(shù)多1個(gè)
C.若采用完全二叉樹(shù)數(shù)組從0號(hào)位開(kāi)始存儲(chǔ)，則節(jié)點(diǎn)b存儲(chǔ)在6號(hào)位
D.該表達(dá)式樹(shù)的前序遍歷序列是×d＋/fc－ab
1.下列關(guān)于二叉樹(shù)的說(shuō)法，不正確的是(　　)
A.二叉樹(shù)的數(shù)據(jù)元素之間呈非線性關(guān)系
B.二叉樹(shù)的第k層上最多有2k－1(k≥1)個(gè)節(jié)點(diǎn)
C.由前序遍歷和中序遍歷序列能唯一確定一棵二叉樹(shù)
D.具有100個(gè)節(jié)點(diǎn)的完全二叉樹(shù)有50個(gè)度為2的節(jié)點(diǎn)
2.有一棵二叉樹(shù)如圖所示，下列說(shuō)法正確的是(　　)
A.該二叉樹(shù)是一棵完全二叉樹(shù)，樹(shù)的高度為3
B.該二叉樹(shù)的前序遍歷為A，B，D，C，E
C.該二叉樹(shù)的葉子節(jié)點(diǎn)有4個(gè)
D.該二叉樹(shù)的建立只能使用數(shù)組來(lái)實(shí)現(xiàn)
3.有樹(shù)結(jié)構(gòu)的示意圖如圖所示，下列關(guān)于該樹(shù)的描述正確的是(　　)
A.該樹(shù)的度為6 B.該樹(shù)的葉子節(jié)點(diǎn)數(shù)量是7
C.節(jié)點(diǎn)I、J互為兄弟節(jié)點(diǎn) D.該樹(shù)的深度為5
4.對(duì)于如圖所示的二叉樹(shù)，下列說(shuō)法正確的是(　　)
A.葉子節(jié)點(diǎn)有4個(gè)
B.是完全二叉樹(shù)，樹(shù)的高度為4
C.前序遍歷的結(jié)果是一個(gè)遞增序列
D.可以使用數(shù)組[2，5，10，7，8，13，9，15]存儲(chǔ)
5.某二叉樹(shù)如下圖所示，下列說(shuō)法正確的是(　　)
A.該二叉樹(shù)共有5個(gè)葉子節(jié)點(diǎn)
B.該二叉樹(shù)是一棵完全二叉樹(shù)
C.對(duì)該二叉樹(shù)進(jìn)行中序遍歷后的計(jì)算結(jié)果是32
D.該二叉樹(shù)的后序遍歷序列為731＋*426＋/－
6.某二叉樹(shù)中序遍歷為ABCDEF，則下列不可能是此二叉樹(shù)的是(　　)
7.有一種二叉樹(shù)，它的任何一個(gè)當(dāng)前節(jié)點(diǎn)，左子樹(shù)的數(shù)據(jù)都比該節(jié)點(diǎn)的數(shù)據(jù)小，右子樹(shù)的數(shù)據(jù)都比該節(jié)點(diǎn)的數(shù)據(jù)大。下列有關(guān)該二叉樹(shù)遍歷說(shuō)法正確的是(　　)
A.采用前序遍歷，遍歷到的節(jié)點(diǎn)元素升序排列
B.采用中序遍歷，遍歷到的節(jié)點(diǎn)元素升序排列
C.采用中序遍歷，遍歷到的節(jié)點(diǎn)元素降序排列
D.采用后序遍歷，遍歷到的節(jié)點(diǎn)元素降序排列
8.某二叉樹(shù)的樹(shù)形結(jié)構(gòu)如圖所示，其后序遍歷結(jié)果為“物技化數(shù)英語(yǔ)”，則中序遍歷結(jié)果為(　　)
A.語(yǔ)數(shù)英物化技 B.物數(shù)技化語(yǔ)英
C.語(yǔ)數(shù)物化技英 D.化物技英數(shù)語(yǔ)
9.某二叉樹(shù)的數(shù)組表示示意圖如圖所示，該二叉樹(shù)的后序遍歷序列為(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
10.已知某二叉樹(shù)的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBDAEF，則下列說(shuō)法正確的是(　　)
A.其后序遍歷結(jié)果為DCBFEA
B.該二叉樹(shù)為完全二叉樹(shù)
C.該二叉樹(shù)深度為3，葉子節(jié)點(diǎn)數(shù)為3
D.該二叉樹(shù)用一維數(shù)組實(shí)現(xiàn)需要6個(gè)節(jié)點(diǎn)的存儲(chǔ)空間才能表示
11.某二叉樹(shù)前序遍歷的結(jié)果為“ABCD”，則中序遍歷的結(jié)果不可能是(　　)
A.ABCD B.CDBA
C.BDAC D.DCBA
12.數(shù)學(xué)表達(dá)式3/(5*2)可用二叉樹(shù)表示，如圖所示。下列關(guān)于該二叉樹(shù)的說(shuō)法，正確的是(　　)
A.是完全二叉樹(shù) B.葉子節(jié)點(diǎn)數(shù)為2
C.前序遍歷結(jié)果為352*/ D.用數(shù)組表示為
專題15　樹(shù)
知識(shí)點(diǎn)一
知識(shí)梳理
1.樹(shù)(Tree)　2.節(jié)點(diǎn)　空樹(shù)　子樹(shù)　3.邊 4.度(Degree)　5.根節(jié)點(diǎn)(Root)　葉節(jié)點(diǎn)(Leaf) 6.父節(jié)點(diǎn)　7.層數(shù)(Level)　高度或深度(Depth) 8.二叉樹(shù)　左子樹(shù)　右子樹(shù)　9.完全二叉樹(shù) 10.2k－1
經(jīng)典案例
例1　D
變式1　D　[本題考查二叉樹(shù)的基本性質(zhì)。符合完全二叉樹(shù)的兩個(gè)條件為：①只有最下二層中的節(jié)點(diǎn)度數(shù)小于2；②最下一層的葉子節(jié)點(diǎn)都依次排列在該層最左邊位置。A選項(xiàng)度指樹(shù)的最大節(jié)點(diǎn)數(shù)。B選項(xiàng)若為滿二叉樹(shù)，第3層及前面所有節(jié)點(diǎn)數(shù)和為7，因此至少4層。C選項(xiàng)最后一層上有5個(gè)節(jié)點(diǎn)，即有葉子節(jié)點(diǎn)數(shù)為5，但第3層上還有一個(gè)葉子節(jié)點(diǎn)。]
例2　C
變式2　C　[設(shè)二叉樹(shù)0度、1度和2度的節(jié)點(diǎn)個(gè)數(shù)分別為t0，t1，t2，有等式t0＋t1＋t2＝78和t0＝t2＋1成立，代入可得t0＋t1＋t0－1＝78，且完全二叉樹(shù)1度節(jié)點(diǎn)個(gè)數(shù)為0或1，因此t1值為1。]
知識(shí)點(diǎn)二
知識(shí)梳理
1.建立二叉樹(shù)　2.用數(shù)組表示完全二叉樹(shù)　3.用數(shù)組表示非完全二叉樹(shù)　4.用鏈表實(shí)現(xiàn)二叉樹(shù)　5.二叉樹(shù)的遍歷　6.前序遍歷　7.中序遍歷　8.后序遍歷
經(jīng)典案例
例1　A
變式1　C　[本題考查二叉樹(shù)遍歷。中序遍歷的方法：左子樹(shù)－根－右子樹(shù)，每個(gè)子樹(shù)，都遵循以上規(guī)定。A選項(xiàng)中序遍歷結(jié)果為EDFBAC。B選項(xiàng)中序遍歷結(jié)果為BEDFAC。C選項(xiàng)中序遍歷結(jié)果為BAEDFC。D選項(xiàng)中序遍歷結(jié)果為BACEDF。]
例2　A
變式2　D　[本題考查樹(shù)與二叉樹(shù)相關(guān)知識(shí)。樹(shù)的度是最大的節(jié)點(diǎn)的度，樹(shù)的高度是節(jié)點(diǎn)最大的層數(shù)，A選項(xiàng)在任意一棵二叉樹(shù)中都有n0＝n2＋1的性質(zhì)，即葉子節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)多一個(gè)；非完全二叉樹(shù)若用完全二叉樹(shù)保存時(shí)需將樹(shù)補(bǔ)成完全二叉樹(shù)，即第3層需補(bǔ)全d節(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)b存儲(chǔ)在第6號(hào)位置上。D選項(xiàng)該表達(dá)式樹(shù)的前序遍歷序列是×d＋/f－cab，對(duì)節(jié)點(diǎn)“－”而言先于其子節(jié)點(diǎn)c。]
當(dāng)堂過(guò)關(guān)檢測(cè)
1.D　[本題考查樹(shù)的性質(zhì)。A選項(xiàng)樹(shù)表現(xiàn)一種層次性的非線性關(guān)系。D選項(xiàng)設(shè)二叉樹(shù)0度、1度和2度的節(jié)點(diǎn)個(gè)數(shù)分別為t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉樹(shù)1度節(jié)點(diǎn)個(gè)數(shù)為0或1，因此t2值為49。]
2.B　[本題考查樹(shù)的性質(zhì)。A選項(xiàng)完全二叉樹(shù)第n－1層為滿二叉樹(shù)，不符合。C選項(xiàng)葉子節(jié)點(diǎn)有2個(gè)。D選項(xiàng)可以用數(shù)組或鏈表實(shí)現(xiàn)。]
3.B　[本題考查樹(shù)的基本概念。A選項(xiàng)度是指節(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)，其中最大的節(jié)點(diǎn)的度就是樹(shù)的度。B選項(xiàng)共有H、I、J、C、K、L、M，7個(gè)葉子。C選項(xiàng)父節(jié)點(diǎn)是同一個(gè)的，才是兄弟節(jié)點(diǎn)。D選項(xiàng)該樹(shù)共4層，所以深度是4。]
4.C　[本題考查二叉樹(shù)相關(guān)知識(shí)。A選項(xiàng)葉子節(jié)點(diǎn)有7，9，15，共3個(gè)。B選項(xiàng)完全二叉樹(shù)要求葉子節(jié)點(diǎn)從右開(kāi)始，且最多只出現(xiàn)在最下面2層。C正確，前序遍歷時(shí)2－5－7－8－9－10－13－15，是一個(gè)遞增序列。D選項(xiàng)用數(shù)組表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15]。]
5.D　[A選項(xiàng)共有6個(gè)葉子節(jié)點(diǎn)。C選項(xiàng)中序遍歷為7*(3＋1)－(4/(2＋6))＝28－0.5＝27.5。]
6.C　[C選項(xiàng)中序遍歷為ACBDEF。]
7.B　[本題考查二叉樹(shù)的遍歷。畫(huà)出如題描述的二叉樹(shù)，根為5，故前序遍歷和后序遍歷都不可能實(shí)現(xiàn)升序或者降序。若采用中序遍歷，因?yàn)橹行虮闅v的結(jié)果是左根右，以左子樹(shù)為例，左根右的結(jié)果是234，升序，故答案選B。]
8.B　[本題考查二叉樹(shù)遍歷。后序遍歷是“物技化數(shù)英語(yǔ)”可知，根節(jié)點(diǎn)為語(yǔ)，數(shù)英分別是語(yǔ)節(jié)點(diǎn)的左右孩子。物為數(shù)的左孩子，技為最高層的左孩子，化為數(shù)的右孩子。]
9.B　[本題考查二叉樹(shù)的遍歷。根據(jù)題意畫(huà)出二叉樹(shù)如下。
后序遍歷是：BFDGECA。]
10.C　[本題考查樹(shù)的性質(zhì)和遍歷。
根據(jù)前序遍歷確定根節(jié)點(diǎn)，中序遍歷區(qū)分左右子樹(shù)，畫(huà)出二叉樹(shù)。其后序遍歷結(jié)果為CDBFEA，該二叉樹(shù)最后一層葉子節(jié)點(diǎn)不是從左向右分布。該二叉樹(shù)深度為3，葉子節(jié)點(diǎn)數(shù)為3。]
11.C　[本題考查二叉樹(shù)相關(guān)概念。前序遍歷為根左右，中序遍歷為左根右。A選項(xiàng)當(dāng)左子樹(shù)缺失時(shí)，遍歷序列相同。D選項(xiàng)當(dāng)右子樹(shù)缺失時(shí)，遍歷序列正好相反。節(jié)點(diǎn)D可能是整棵樹(shù)的右子樹(shù)，也可能是左子樹(shù)中的一個(gè)右孩子，但節(jié)點(diǎn)C一定先于節(jié)點(diǎn)D訪問(wèn)，因此C選項(xiàng)不可能。B選項(xiàng)當(dāng)D是C的右孩子，C缺失左孩子，整棵樹(shù)沒(méi)有右子樹(shù)。]
12.D　[本題考查二叉樹(shù)的遍歷。A選項(xiàng)完全二叉樹(shù)是指一棵深度為k的有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，編號(hào)為i(1≤i≤n)的節(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的節(jié)點(diǎn)在二叉樹(shù)中的位置相同。3所在節(jié)點(diǎn)缺少葉子節(jié)點(diǎn)，故該二叉樹(shù)不是完全二叉樹(shù)。B選項(xiàng)3、5、2所在節(jié)點(diǎn)為葉子節(jié)點(diǎn)，數(shù)量為3。C選項(xiàng)前序遍歷結(jié)果為/3*52。D選項(xiàng)將圖中二叉樹(shù)補(bǔ)全為完全二叉樹(shù)，依次把完全二叉樹(shù)中原二叉樹(shù)的節(jié)點(diǎn)用一維數(shù)組的各元素表示。]

展開(kāi)更多......

收起↑