【數據結構與算法】數據結構初階：詳解二叉樹（六）—

🔥個人主頁：艾莉絲努力練劍

?專欄傳送門：《C語言》、《數據結構與算法》、C語言刷題12天IO強訓、LeetCode代碼強化刷題

🍉學習方向：C/C++方向

??人生格言：為天地立心，為生民立命，為往圣繼絕學，為萬世開太平

重要提醒：為什么我們要學那么多的數據結構？這是因為沒有一種數據結構能夠去應對所有場景。我們在不同的場景需要選擇不同的數據結構，所以數據結構沒有誰好誰壞之分，而評估數據結構的好壞要針對場景，如果在一種場景下我們需要頻繁地對頭部進行插入刪除操作，那么這個時候我們用鏈表；但是如果對尾部進行插入刪除操作比較頻繁，那我們用順序表比較好。

? ? ? ? 因此，不同的場景我們選擇不同的數據結構。

前言：本篇文章，我們繼續來看二叉樹，來刷一刷選擇題，其實也是對前面學過的知識的一個回顧與練習，畢竟筆試面試已經越來越看重程序員的算法能力，把選擇題作為一個對已學知識的一個快速回顧——比如說加深對數據結構某個重要性質的記憶、降低記憶成本——還是很值得去做的。我們做這些選擇題正有此意：一來加深了對二叉樹性質的理解；二來通過做幾道代表性的選擇題我們將知識點迅速運用了起來，讓知識順利扎根在大腦；三來也是對自己學習二叉樹學習情況的一個小測驗。

正文

一、二叉樹性質相關選擇題

（一）性質

證明：

假設一個二叉樹有 a?個度為2的節點，b 個度為1的節點，c 個葉節點，則這個二叉樹的邊數是 2a+b，另一方面，由于共有 a+b+c 個節點，所以邊數等于 a+b+c-1。

2a + b?= a + b + c?- 1 ，即： a = c-1。

（二）題目

1、題目1?

1、某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（）

A 不存在這樣的二叉樹

B 200

C 198

D 199

解析：

2、題目2

2、在具有 2n 個結點的完全二叉樹中，葉子結點個數為（）

A n

B n+1

C n-1

D n / 2

解析：

在完全二叉樹，有多少度為1的節點個數??

3、題目3

3、一棵完全二叉樹的結點數位為531個，那么這棵樹的高度為（）

A 11

B 10

C 8

D 12

解析：

4、題目4

4、一個具有767個結點的完全二叉樹，其葉子結點個數為（）

A 383

B 384

C 385

D 386

解析：

二叉樹性質相關選擇題答案：

1、B

2、A

3、B

4、B

二、鏈式二叉樹遍歷相關選擇題?

1、題目1?

1、某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH 。

該完全二叉樹的前序序列為（）

A. ABDHECFG

B. ABCDEFGH

C. HDBEAFCG

D. HDEBFGCA

解析：

2、題目2

2、二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。

則二叉樹根結點為（）

A E

B F

C G

D H

解析：先序遍歷打印的一個是就是根節點，知道了先序遍歷，根節點就找到了。

3、題目3

3、設一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，

則二叉樹前序遍歷序列為____。

A adbce

B decab

C debac

D abcde

解析：

方法： 確定一個刪掉一個，也就是說：已知任意兩個求第三個。

根據后序遍歷找到根節點，中序遍歷看左右孩子。如下圖：

1、根據后序遍歷我們確定根節點就是a：

2、確定了，我們就把它刪掉，以免對我們產生干擾：

3、確定了a是根節點，我們看一下中序遍歷，a的左子樹是b，確定的就刪掉：

4、我們看：a的右子樹，中序遍歷的結果是dce，后序遍歷的結果是dec，ab我們都刪掉了，沒有干擾項。dec，根節點是c，既然根節點是c，我們再回到中序遍歷，c的左子樹是d，c的右子樹是e。后面大家做這種題目就可以采用這種方法。

4、題目4

4、某二叉樹的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF，則按層次輸出（同一層從左到右）的序列為（）

A FEDCBA

B CBAFED

C DEFCBA

D ABCDEF

解析：?

只有左子樹，沒有右子樹。?

5、加餐1：題目5

5、已知某二叉樹的中序遍歷序列為JGDHKBAELIMCF，后序遍歷序列為JGKHDBLMIEFCA，則其前序遍歷序列為（）

A.ABDGHJKCEFILM

B.ABDGJHKCEILMF

C.ABDHKGJCEILMF

D.ABDGJHKCEIMLF

解析：

由后序遍歷確定子樹的根，后序遍歷從后向前看，最后一個元素為根，和前序遍歷剛好相反，從后向前看后序遍歷，應該是根，右，左，根據中序遍歷確定子樹的左右區間。

詳解：

我們根據后序遍歷可知，A是根節點——

A的左子樹：JGDHKB，A的右子樹：ELIMCF；

A的左子樹的根：B，A的右子樹的根：C；

B的左子樹：JGDHK，B的右子樹：空，C的左子樹：ELIM，C的右子樹：F；

B的左子樹的根：D，C的左子樹根：E；

D的左子樹的根：G，D的右子樹的根：H，E的右子樹的根：I。

6、加餐2：題目6

6、已知某二叉樹的前序遍歷序列為5 7 4 9 6 2 1，中序遍歷序列為4 7 5 6 9 1 2，

則其后序遍歷序列為（）?

A.4 2 5 7 6 9 1

B.4 2 7 5 6 9 1

C.4 7 6 1 2 9 5

D.4 7 2 9 5 6 1

解析：?

首先根據前序和中序遍歷確定二叉樹結構：
前序遍歷是根左右，可知前序遍歷第一個數5是根節點。
在中序遍歷中找到5，左邊4 7是左子樹，右邊6 9 1 2是右子樹。
前序中5后面是7，7是左子樹的根，中序中7左邊是4，所以7的左子節點是4 。
前序接著是4、9，9是右子樹的一部分，中序中5右邊6在9前，所以9是6的父節點，我們逐步構建出二叉樹。
已知后序遍歷順序是左右根。
正確構建二叉樹后，后序遍歷應為4 7 6 1 2 9 5。

鏈式二叉樹遍歷相關選擇題答案：

1、A

2、A

3、D

4、A

5、B

6、C

三、二叉樹樹度相關選擇題

1、題目1

1、一顆擁有1000個結點的樹度為4，則它的最小深度是（）

A.5

B.6

C.7

D.8

解析·：?

要使樹深度最小，應讓樹盡可能“滿”，即除最后一層，每層結點數達該度下最大值

（度為4，則每層最多4^(i - 1)個結點，i 為層數）。
設深度為h，前h - 1層是滿的，結點數和為(4^(h - 1) - 1) / (4 - 1)?。
當h = 5，前4層和為(4^4 - 1) / 3 = 85；

當h = 6，前5層和為(4^5 - 1) / 3 = 341；

當h = 7，前6層和為(4^6 - 1) / 3 = 1365 > 1000 。
且前5層和341 < 1000，前6層和1365 > 1000，所以最小深度是6?。