資源簡(jiǎn)介

專題15　樹
知識(shí)點(diǎn)一　樹的性質(zhì)
1.假設(shè)完全二叉樹的樹根為第1層，樹中第10層有5個(gè)葉子結(jié)點(diǎn)，則完全二叉樹最多有個(gè)結(jié)點(diǎn)(　　)
A.511 B.516
C.2037 D.2047
2.下列Python表達(dá)式用于表示“一棵n個(gè)節(jié)點(diǎn)的二叉樹的葉子節(jié)點(diǎn)最大可能數(shù)量”，正確的是(　　)
A.n－1 B.n//2
C.n//2＋1 D.n/2
3.某二叉樹的結(jié)構(gòu)如圖所示，下列說法不正確的是(　　)
A.該二叉樹是一棵完全二叉樹
B.該二叉樹的葉子節(jié)點(diǎn)數(shù)是3個(gè)
C.該二叉樹的中序遍歷結(jié)果是DCBEAF
D.該二叉樹的度為2
4.某樹的結(jié)構(gòu)如右，下列說法正確的是(　　)
A.該樹的度為4 B.該樹的高度為4
C.該樹的葉子節(jié)點(diǎn)為3個(gè) D.節(jié)點(diǎn)F和G是兄弟節(jié)點(diǎn)
5.一棵有n(n>0)個(gè)節(jié)點(diǎn)的二叉樹，其節(jié)點(diǎn)為0度或2度，則此樹的最大高度是(　　)
A.(n＋1)//2 B.n//2
C.(n－1)//2 D.int(log2n＋1)
6.若一棵二叉樹具有10個(gè)度為2的節(jié)點(diǎn)，5個(gè)度為1的節(jié)點(diǎn)，則該樹形結(jié)構(gòu)的總邊數(shù)是(　　)
A.14 B.25
C.23 D.不能確定
7.將一棵有1000個(gè)節(jié)點(diǎn)的完全二叉樹按照從上到下、從左到右的順序依次進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為35的節(jié)點(diǎn)的右孩子編號(hào)為(　　)
A.36 B.70
C.72 D.71
8.下列有關(guān)二叉樹的論述中，正確的是(　　)
A.只有一個(gè)節(jié)點(diǎn)的二叉樹的度為0
B.二叉樹的度為2
C.二叉樹的左右子樹可任意交換
D.完全二叉樹的所有節(jié)點(diǎn)的度均為2
9.若一棵二叉樹具有10個(gè)葉子節(jié)點(diǎn)，則樹形結(jié)構(gòu)度為2的節(jié)點(diǎn)數(shù)為(　　)
A.8 B.9
C.10 D.11
10.若一棵二叉樹共有10個(gè)節(jié)點(diǎn)，其中4個(gè)是葉子節(jié)點(diǎn)，則度為1的節(jié)點(diǎn)數(shù)量為(　　)
A.3 B.4
C.5 D.6
知識(shí)點(diǎn)二　樹的遍歷
1.如圖所示的二叉樹，若要得到一個(gè)遞增序列，可以用下列遍歷方式是(　　)
A.前序遍歷 B.中序遍歷
C.后序遍歷 D.逐層遍歷
2.有一棵二叉樹如圖所示：關(guān)于該樹，以下說法正確的是(　　)
A.該二叉樹是一棵完全二叉樹，樹的高度為4
B.該二叉樹的前序遍歷為25、15、46、6、18、28、58、12、22、35、60
C.該二叉樹的葉子節(jié)點(diǎn)有8個(gè)
D.若用數(shù)組(第一個(gè)元素下標(biāo)為0)來表示該樹，則節(jié)點(diǎn)“46”在數(shù)組中下標(biāo)為2
3.某二叉樹的樹形結(jié)構(gòu)如圖所示，其后序遍歷結(jié)果為FBCEAD，則前序遍歷結(jié)果為(　　)
A.ABCDEF B.FEDCBA
C.DFACBE D.FDBCAE
4.某二叉樹的前序遍歷結(jié)果為ABCDEF，后序遍歷結(jié)果為CDBFEA，下列關(guān)于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度可能為4
B.該二叉樹的中序遍歷結(jié)果可能為CBDAEF
C.該二叉樹可能的形態(tài)有3種
D.該二叉樹度為2的節(jié)點(diǎn)可能有3個(gè)
5.已知一棵二叉樹如圖所示，下列說法正確的是(　　)
A.樹的高度是4，節(jié)點(diǎn)F是唯一的葉子節(jié)點(diǎn)
B.中序、后序的遍歷方式，節(jié)點(diǎn)F先于節(jié)點(diǎn)D、E訪問
C.前序遍歷的結(jié)果為A－B－C－D－E－F
D.使用數(shù)組可以表示為[‘A’，‘B’，‘C’，‘D’，‘E’，‘F’]
6.用一維數(shù)組來表示某二叉樹如表所示，則下列說法不正確的是(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
A.該二叉樹的深度為4
B.節(jié)點(diǎn)B有兩個(gè)孩子節(jié)點(diǎn)，分別為E和F
C.該二叉樹的中序遍歷結(jié)果為DBGEAFHC
D.葉子節(jié)點(diǎn)的數(shù)量比度為2的節(jié)點(diǎn)數(shù)量多1
7.如圖所示，將二叉樹A的根節(jié)點(diǎn)與二叉樹B的根節(jié)點(diǎn)連接，使得二叉樹A成為二叉樹B的左子樹，合并為一棵新的二叉樹C。下列說法中正確的是(　　)
A.二叉樹C的高度為3
B.二叉樹C的葉子節(jié)點(diǎn)數(shù)量為3
C.二叉樹C是一棵完全二叉樹
D.二叉樹C中序遍歷的結(jié)果是一個(gè)有序序列
8.已知一棵二叉樹的前序遍歷序列為ABCDEFG，則該二叉樹中序遍歷序列可能為(　　)
A.CABDEFG B.ABCDEFG
C.DACEFBG D.ADBCFEG
9.某二叉樹從根節(jié)點(diǎn)開始，按從上到下、自左往右的順序用A－G字母表示，若補(bǔ)全為完全二叉樹后，用一維數(shù)組表示如圖所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列關(guān)于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度為3
B.節(jié)點(diǎn)E的父節(jié)點(diǎn)是B
C.該二叉樹的中序遍歷結(jié)果為BFDGACE
D.該二叉樹的葉子節(jié)點(diǎn)為D、E、F、G
10.二叉樹的中序遍歷為BAEDFC，后序遍歷為BEFDCA，其前序遍歷為(　　)
A.ABDEFC B.ABDCEF
C.ABCDEF D.ABCDFE
11.已知某二叉樹的后序遍歷結(jié)果為BCGEFDA，中序遍歷結(jié)果為CBAEGDF，下列說法不正確的是(　　)
A.該二叉樹不是完全二叉樹
B.該二叉樹的深度為4
C.該二叉樹的前序遍歷結(jié)果為ACBDEGF
D.該二叉樹所對(duì)應(yīng)的一維數(shù)組表示為：
0 1 2 3 4 5 6 7 8 9 10 11
A C D B E F G
12.如圖所示二叉樹的前序遍歷序列是(　　)
A.A－B－C－D－E－G－H－F－I
B.A－B－D－E－G－H－C－F－I
C.D－B－E－G－H－A－C－F－I
D.B－D－G－H－E－A－F－I－C
13.某二叉樹用數(shù)組表示，如圖所示，下列說法正確的是(　　)
A.該二叉樹是完全二叉樹
B.該二叉樹的深度是3
C.該二叉樹的葉子節(jié)點(diǎn)有2個(gè)
D.該二叉樹的中序遍歷為A－D－E－F－G－C－B
14.有一棵二叉樹，如圖所示，下列說法正確的是(　　)
A.此二叉樹是完全二叉樹
B.此二叉樹的深度是3
C.此二叉樹的中序遍歷為H－D－B－E－A－C－F
D.此二叉樹用一維數(shù)組表示為['A'，'B'，''，'C'，'D'，'E'，''，'F'，''，'H']
15.某表達(dá)式樹如圖所示，則該樹的后序遍歷結(jié)果是(　　)
A.3＋7*5－8/2 B.8/2*5＋37－
C.37＋5*82/－ D.82/5－3＋7*
16.用數(shù)組表示二叉樹的示意圖如下所示，則該二叉樹的中序遍歷序列為(　　)
A.BEDFAC B.ABDEFC
C.DBEAFC D.BDAECF
17.已知二叉樹T節(jié)點(diǎn)的前序遍歷序列為A－B－D－E－F－G－C，中序遍歷序列是D－B－F－E－G－A－C，則其后序遍歷序列是(　　)
A.F－D－G－E－B－C－A B.D－F－G－E－B－C－A
C.B－F－D－G－B－C－A D.C－G－F－E－D－B－A
18.某二叉樹前序遍歷的結(jié)果為“大好河山”，則中序遍歷的結(jié)果不可能是(　　)
A.大好河山 B.河山好大
C.好山大河 D.山河好大
19.已知二叉樹的后序遍歷序列是DCBAE，中序遍歷序列是BDCEA，它的前序遍歷序列是(　　)
A.EBDCA B.ACDBE
C.ECDBA D.EBCDA
20.某二叉樹的前序遍歷為A－B－D－E－C－F－G，中序遍歷為B－D－E－A－F－C－G，則下列說法正確的是(　　)
A.該二叉樹的葉子節(jié)點(diǎn)有4個(gè)
B.該二叉樹的后序遍歷為E－D－B－F－G－C－A
C.該二叉樹的高度為4，是一棵完全二叉樹
D.用數(shù)組來表示該樹，若A的下標(biāo)為0，則E的下標(biāo)為5
21.某二叉樹的前序遍歷和后序遍歷正好相反，則該二叉樹一定是(　　)
A.空或只有一個(gè)節(jié)點(diǎn) B.高度等于其節(jié)點(diǎn)數(shù)
C.任一節(jié)點(diǎn)無左孩子 D.任一節(jié)點(diǎn)無右孩子
22.某二叉樹前序遍歷為ABDCE，后序遍歷為DBECA，則該二叉樹可能情況數(shù)量是(　　)
A.1 B.2
C.4 D.6
23.有二叉樹的前序遍歷序列為A－B－C－E－F－G－D，中序遍歷序列為A－E－C－F－G－B－D，則關(guān)于該二叉樹的說法正確的是(　　)
A.該二叉樹根節(jié)點(diǎn)的度為1
B.該二叉樹的高度為4
C.該二叉樹中節(jié)點(diǎn)G是節(jié)點(diǎn)C的左孩子
D.該二叉樹中葉子節(jié)點(diǎn)的個(gè)數(shù)為4
專題15　樹
知識(shí)點(diǎn)一
1.C　[本題考查樹的性質(zhì)。在完全二叉樹中，葉子節(jié)點(diǎn)出現(xiàn)在最后一層或倒數(shù)第二層中。當(dāng)樹有11層時(shí)，達(dá)到最多有211個(gè)結(jié)點(diǎn)。完全二叉樹倒數(shù)第二層是滿二叉樹，最后一層從左向右分布節(jié)點(diǎn)，因此最后一層缺少10個(gè)葉子節(jié)點(diǎn)。211－1－10＝2037。]
2.C　[本題考查二叉樹的性質(zhì)。由n0＝n2＋1和n0＋n1＋n2＝n可得到n0＋n1＋n0－1＝n，二叉樹度為1的節(jié)點(diǎn)個(gè)數(shù)n1為0時(shí)，葉子節(jié)點(diǎn)個(gè)數(shù)n0達(dá)到最多，得到n0＝(n＋1)/2。總節(jié)點(diǎn)個(gè)數(shù)是奇數(shù)個(gè)，(n＋1)/2等價(jià)于n//2＋1。]
3.A　[本題考查二叉樹的性質(zhì)。該樹不是完全二叉樹。葉子節(jié)點(diǎn)有DEF，節(jié)點(diǎn)中最大的度為2。]
4.B　[本題考查樹的性質(zhì)。A選項(xiàng)數(shù)的度取決于節(jié)點(diǎn)的最大度數(shù)，因此該樹的度為3。]
5.A　[本題考查二叉樹基本性質(zhì)。該二叉樹的節(jié)點(diǎn)的度都為0或2，即除根節(jié)點(diǎn)外，其余每個(gè)節(jié)點(diǎn)都有一個(gè)兄弟節(jié)點(diǎn)。題目要求樹的最大高度，每層就只有2個(gè)節(jié)點(diǎn)(除了根節(jié)點(diǎn))，若總節(jié)點(diǎn)數(shù)加上1，相當(dāng)于令第1層也變成兩個(gè)節(jié)點(diǎn)，那么總層數(shù)就是(n＋1)//2。]
6.B　[根據(jù)題目已知度為2的節(jié)點(diǎn)為10個(gè)，則葉子節(jié)點(diǎn)為11個(gè)，所以總的節(jié)點(diǎn)數(shù)為10＋5＋11＝26，在二叉樹的所有節(jié)點(diǎn)中，除了根節(jié)點(diǎn)沒有前驅(qū)外，每個(gè)節(jié)點(diǎn)均有且只有一個(gè)前驅(qū)節(jié)點(diǎn)，因此26個(gè)節(jié)點(diǎn)的二叉樹的總邊數(shù)為25條。]
7.D　[在一棵完全二叉樹中，若父節(jié)點(diǎn)的編號(hào)為n，則它的左孩子編號(hào)為2*n，右孩子的編號(hào)為2*n＋1，則編號(hào)為35的節(jié)點(diǎn)的右孩子編號(hào)為71。]
8.A　[節(jié)點(diǎn)所擁有的子樹個(gè)數(shù)稱為該節(jié)點(diǎn)的度，只有一個(gè)節(jié)點(diǎn)的二叉樹的度為0，二叉樹的度小于等于2，完全二叉樹最下面兩層的節(jié)點(diǎn)度數(shù)小于2，二叉樹的左右子樹交換會(huì)改變數(shù)據(jù)的層次關(guān)系。]
9.B　[根據(jù)二叉樹的性質(zhì)，任意一棵二叉樹中，若度為2節(jié)點(diǎn)數(shù)量為n2，葉子節(jié)點(diǎn)數(shù)為n0，則n0＝n2＋1，故題目中度為2的節(jié)點(diǎn)數(shù)是9個(gè)。]
10.A　[二叉樹的所有節(jié)點(diǎn)的度都小于或者等于2，題目中已知葉子節(jié)點(diǎn)數(shù)為4，則度為2的節(jié)點(diǎn)數(shù)是4－1＝3，因此度為1的節(jié)點(diǎn)數(shù)是10－4－3＝3。]
知識(shí)點(diǎn)二
1.B　[最小的數(shù)是3，是最下層的左子樹，因此是中序遍歷。]
2.D　[D選項(xiàng)25的索引是0，第二層中索引分別是1和2。]
3.C　[根據(jù)樹的形態(tài)，畫出后序遍歷的路徑，從而確定每個(gè)節(jié)點(diǎn)的值。]
4.B　[A為樹的根節(jié)點(diǎn)，在后序遍歷中，B沒有緊跟在A的前面，因此B是A的左孩子，CD是B的子樹，F(xiàn)E是A的右子樹。因此樹的形態(tài)可能有如圖所示的兩種情況。]
5.B　[A選項(xiàng)B和E也是葉子節(jié)點(diǎn)。B選項(xiàng)F是D的左子樹，在中序、后序遍歷中，F(xiàn)先于D，D和E分別是C的左右子樹，D肯定先于E。]
6.B　[構(gòu)建的二叉樹如圖。深度為4，B的兩個(gè)孩子節(jié)點(diǎn)為D和E。]
7.C　[本題考查二叉樹的性質(zhì)和遍歷。新二叉樹高度為4；葉子節(jié)點(diǎn)數(shù)量為4，是一棵完全二叉樹；中序遍歷的結(jié)果為84251637，不是一個(gè)有序序列。]
8.B　[本題考查二叉樹的相關(guān)知識(shí)。前序遍歷找出根A，中序遍歷根據(jù)根的位置，區(qū)別左右子樹。A選項(xiàng)左子樹為C，但C在前序遍歷中后于B訪問，不正確。C選項(xiàng)同A選項(xiàng)。D選項(xiàng)該樹沒有左子樹，在右子樹中，B為根，D為B的左孩子，但在前序中D后于C訪問，不正確。B選項(xiàng)前序遍歷為根左右，中序遍歷為左根右，當(dāng)樹缺失左孩子時(shí)，前中序遍歷是一樣的。]
9.C　[本題考查二叉樹性質(zhì)和遍歷。根據(jù)題意畫出二叉樹如圖所示：該二叉樹的深度為4，E的父節(jié)點(diǎn)是C，中序遍歷是B－F－D－G－A－C－E，該二叉樹的葉子節(jié)點(diǎn)是F，G，E。]
10.C　[本題考查二叉樹的相關(guān)知識(shí)。后序遍歷確定根節(jié)點(diǎn)，中序遍歷區(qū)分左右子樹。根據(jù)二叉樹的中序遍歷和后序遍歷可知，該二叉樹的形狀如圖所示，前序遍歷為：ABCDEF。]
11.D　[本題考查二叉樹的性質(zhì)和遍歷。后序遍歷確定根節(jié)點(diǎn)，中序遍歷由根節(jié)點(diǎn)位置劃分左右子樹。根節(jié)點(diǎn)A的左右子樹分別為CB和EGDF，C為子樹根，B為右節(jié)點(diǎn)。同理可以得到整棵樹的結(jié)構(gòu)。該樹深度為4但不是完全二叉樹，前序遍歷結(jié)果為ACBDEGF，對(duì)應(yīng)的一維數(shù)組為]
0 1 2 3 4 5 6 7 8 9 10 11 12
A C D B E F G
12.B　[本題考查二叉樹的遍歷。前序遍歷的順序?yàn)楦螅遥谝粋€(gè)遍歷的節(jié)點(diǎn)一定是A，接下來遍歷A的左子樹，最后遍歷A的右子樹，遍歷結(jié)果應(yīng)為A－B－D－E－G－H－C－F－I。]
13.D　[根據(jù)存儲(chǔ)結(jié)構(gòu)畫出二叉樹如圖所示。A選項(xiàng)該二叉樹不是完全二叉樹。B選項(xiàng)該樹深度為4。C選項(xiàng)葉子節(jié)點(diǎn)有3個(gè)。]
14.C　[本題考查二叉樹的相關(guān)知識(shí)。A選項(xiàng)節(jié)點(diǎn)C缺少左子樹，不是完全二叉樹。B選項(xiàng)該二叉樹的深度是4。D選項(xiàng)節(jié)點(diǎn)C前沒有空節(jié)點(diǎn)。]
15.C　[本題考查樹的遍歷。訪問順序左、右、根，從最左最高層子樹開始遍歷。最后訪問根結(jié)點(diǎn)。]
16.A　[本題考查樹的存儲(chǔ)和遍歷。D是B的右孩子，C節(jié)點(diǎn)沒有孩子，D的左右孩子為E和F。中序遍歷是左根右，B的左孩子缺失，因此先訪問B再訪問B的右子樹EDF，接著訪問根節(jié)點(diǎn)A，再訪問右孩子C。]
17.B　[本題考查二叉樹的遍歷。根據(jù)前序可以確定根節(jié)點(diǎn)為A，把中序分為(DBFEG)A(C)，B為子樹DBFEG根節(jié)點(diǎn)，E為子樹FEG的根節(jié)點(diǎn)，畫出二叉樹，并確定后序遍歷。]
18.C　[本題考查樹的遍歷。前序遍歷為根左右，A選項(xiàng)任一節(jié)點(diǎn)沒有左節(jié)點(diǎn)，則前中序均為根右。B選項(xiàng)河是第1個(gè)左節(jié)點(diǎn)，則好是大的左節(jié)點(diǎn)，是河的根，山為河的兄弟。D選項(xiàng)任一節(jié)點(diǎn)沒有右節(jié)點(diǎn)。C選項(xiàng)好是大的左節(jié)點(diǎn)，山是右節(jié)點(diǎn)，或山是大的左節(jié)點(diǎn)，是好的父節(jié)點(diǎn)，則前序遍歷不對(duì)了。]
19.D　[本題考查二叉樹的遍歷。從后序遍歷來看，E為根節(jié)點(diǎn)，因此把中序遍歷分成(BDC)E(A)三部分，在子樹BDC中，B為根節(jié)點(diǎn)，DC為右子樹，在子樹DC中，C為根節(jié)點(diǎn)。]
20.B　[本題考查二叉樹的性質(zhì)、存儲(chǔ)和遍歷。根據(jù)前序遍歷，可知A為根節(jié)點(diǎn)，中序序列可以劃分為(BDE)A(FCG)，則左子樹BDE中，B為根節(jié)點(diǎn)，DE為右子樹，DE子樹中，E為D的右節(jié)點(diǎn)。右子樹FCG中，C為根節(jié)點(diǎn)，F(xiàn)和G分別為左右子樹。根據(jù)上述描述，畫出樹，可知葉子節(jié)點(diǎn)有EFG3個(gè)，后序遍歷為EDBFGCA，樹的高度為4，但不是完全二叉樹。]
21.B　[本題考查二叉樹的遍歷。二叉樹的前序遍歷是：根－左－右，后序遍歷是：左－根－右，當(dāng)前序遍歷和后序遍歷恰好相反的時(shí)候，可以是沒有左子樹，也可以是沒有右子樹，因此二叉樹的高度等于節(jié)點(diǎn)數(shù)。]
22.C　[本題考查二叉樹遍歷的相關(guān)知識(shí)。左右子樹的根節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)，以下四種情況的前序和后序遍歷都符合題目要求：]
23.A　[本題考查二叉樹的性質(zhì)和遍歷。根據(jù)二叉樹的前序遍歷和中序遍歷畫出二叉樹。該二叉樹的根節(jié)點(diǎn)A的度為1，高度為5，節(jié)點(diǎn)G是節(jié)點(diǎn)F的右孩子。該二叉樹的葉子節(jié)點(diǎn)是E、G、D。]

展開更多......

收起↑