?朋友們、伙計(jì)們，我們又見(jiàn)面了，本期來(lái)給大家解讀一下有關(guān)二叉樹(shù)的經(jīng)典例題，如果看完之后對(duì)你有一定的啟發(fā)，那么請(qǐng)留下你的三連，祝大家心想事成！
C 語(yǔ) 言 專(zhuān) 欄：C語(yǔ)言：從入門(mén)到精通
數(shù)據(jù)結(jié)構(gòu)專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)
個(gè)? 人? 主? 頁(yè)?：stackY、
?
目錄
?
前言：
一、
二、
三、
四、
五、
六、
七、
八、
前言：
承接上篇的二叉樹(shù)經(jīng)典例題，本期再來(lái)給大家?guī)?lái)一期關(guān)于二叉樹(shù)的經(jīng)典例題，話不多說(shuō)，直接開(kāi)始！！
一、
1. 設(shè)某種二叉樹(shù)有如下特點(diǎn)：每個(gè)結(jié)點(diǎn)要么是葉子結(jié)點(diǎn)，要么有2棵子樹(shù)。假如一棵這樣的二叉樹(shù)中有m（m>0）個(gè)葉子結(jié)點(diǎn)，那么該二叉樹(shù)上的結(jié)點(diǎn)總數(shù)為（? ）
A.2m+1
B.2(m-1)
C.2m-1
D.2m
?題解： C
根據(jù)二叉樹(shù)的性質(zhì)，在任意的二叉樹(shù)中，度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)多了1個(gè)----見(jiàn)二叉樹(shù)的性質(zhì)
現(xiàn)在葉子節(jié)點(diǎn)為m個(gè)，即度為0的節(jié)點(diǎn)有m個(gè)，那度為2的節(jié)點(diǎn)個(gè)數(shù)就為m-1個(gè)
而題目說(shuō)該二叉樹(shù)中只有度為2和度為0的節(jié)點(diǎn) ，因此總的節(jié)點(diǎn)數(shù)就為：m+m-1 = 2m-1
故選擇C
二、
2. 設(shè)根結(jié)點(diǎn)的深度為1，則一個(gè)擁有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度一定在（???）區(qū)間內(nèi)?
A.[log(n + 1)，n]
B.[logn，n]
C.[log(n + 1)，n - 1]
D.[log(n + 1)，n + 1]
題解： A?
假設(shè)深度為h，則該二叉樹(shù)最多有2^h - 1個(gè)結(jié)點(diǎn)。
因此，我們可以列出不等式： 2^(h-1) <= n <= 2^h - 1 對(duì)不等式兩邊同時(shí)取對(duì)數(shù)
得到： h-1 <= logn <= h-1+log2 因?yàn)閘og2 = 1
所以： h-1 <= logn <= h 將上述不等式轉(zhuǎn)化為區(qū)間表示
則有： h <= logn + 1 <= h+1
因此，選項(xiàng)A是正確的。
三、
3. 對(duì)任意一顆二叉樹(shù)，設(shè)N0、N1、N2分別是度為0、1、2的結(jié)點(diǎn)數(shù)，則下列式子中一定正確的是（? ）
A.N0 = N2 + 1
B.N1 = N0 + 1
C.N2 = N0 + 1
D.N2 = N1 + 1
題解： A?
節(jié)點(diǎn)總數(shù)N： N = N0 + N1 + N2
度和邊的關(guān)系： N - 1 = 0 * N0 + 1 * N1 + 2 * N2
上面兩個(gè)式子可以推出： N0 + N1 + N2 - 1 = N1 + 2 * N2
可得： N0 = N2 + 1
四、
4. 二叉樹(shù)的(? )遍歷相當(dāng)于廣度優(yōu)先遍歷，(? )遍歷相當(dāng)于深度優(yōu)先遍歷?
A.前序 中序
B.中序 前序
C.層序 后序
D.層序 前序
題解：? D?
廣度優(yōu)先需要把下一步所有可能的位置全部遍歷完，才會(huì)進(jìn)行更深層次的遍歷，層序遍歷就是一種廣度優(yōu)先遍歷。
深度優(yōu)先是先遍歷完一條完整的路徑（從根到葉子的完整路徑），才會(huì)向上層折返，再去遍歷下一個(gè)路徑，前序遍歷就是一種深度優(yōu)先遍歷。
五、
5.? 如果一顆二叉樹(shù)的前序遍歷的結(jié)果是ABCD，則滿(mǎn)足條件的不同的二叉樹(shù)有（? ）種
A.13
B.14
C.15
D.16
題解： B
對(duì)于一棵二叉樹(shù)，它的前序遍歷序列的第一個(gè)元素一定是根節(jié)點(diǎn)。因此，對(duì)于給定的前序遍歷序列ABCD，我們可以將它的第一個(gè)元素A作為根節(jié)點(diǎn)，然后考慮將剩余的元素分配到左子樹(shù)和右子樹(shù)中。 由于左子樹(shù)和右子樹(shù)可以為空，因此我們可以按照以下方式嘗試構(gòu)建二叉樹(shù)：
- A作為根節(jié)點(diǎn)，BCD為空樹(shù)。
- A作為根節(jié)點(diǎn)，B作為左子節(jié)點(diǎn)，CD為空樹(shù)。
- A作為根節(jié)點(diǎn)，B作為右子節(jié)點(diǎn)，CD為空樹(shù)。
- A作為根節(jié)點(diǎn)，B作為左子節(jié)點(diǎn)，C作為右子節(jié)點(diǎn)，D為空樹(shù)。
- A作為根節(jié)點(diǎn)，B作為右子節(jié)點(diǎn)，C作為左子節(jié)點(diǎn)，D為空樹(shù)。
- A作為根節(jié)點(diǎn)，B作為左子節(jié)點(diǎn)，C和D作為右子節(jié)點(diǎn)。
- A作為根節(jié)點(diǎn)，B作為右子節(jié)點(diǎn)，C和D作為左子節(jié)點(diǎn)。
- A作為根節(jié)點(diǎn)，C作為左子節(jié)點(diǎn)，BD為空樹(shù)。
- A作為根節(jié)點(diǎn)，C作為右子節(jié)點(diǎn)，BD為空樹(shù)。
- A作為根節(jié)點(diǎn)，C作為左子節(jié)點(diǎn)，B作為右子節(jié)點(diǎn)，D為空樹(shù)。
- A作為根節(jié)點(diǎn)，C作為右子節(jié)點(diǎn)，B作為左子節(jié)點(diǎn)，D為空樹(shù)。
- A作為根節(jié)點(diǎn)，C作為左子節(jié)點(diǎn)，D作為右子節(jié)點(diǎn)，B為空樹(shù)。
- A作為根節(jié)點(diǎn)，C作為右子節(jié)點(diǎn)，D作為左子節(jié)點(diǎn)，B為空樹(shù)。
- A作為根節(jié)點(diǎn)，B和C作為左右子節(jié)點(diǎn)，D為空樹(shù)。
- A作為根節(jié)點(diǎn)，B和C作為右左子節(jié)點(diǎn)，D為空樹(shù)。因此，滿(mǎn)足條件的不同的二叉樹(shù)有14種。
六、
6. 有n個(gè)元素的完全二叉樹(shù)的深度是（???）?
A.nlogn
B.nlogn+1
C.logn
D.logn+1
題解： D?
參考完全二叉樹(shù)的性質(zhì)，高度h = log(n)向上取整 注意：底數(shù)是2
故選擇D
七、
7. 已知某二叉樹(shù)的前序遍歷序列為ABDEC，中序遍歷序列為BDEAC，則該二叉樹(shù)（? ）
A.是滿(mǎn)二叉樹(shù)
B.是完全二叉樹(shù)，不是滿(mǎn)二叉樹(shù)
C.不是完全二叉樹(shù)
D.是所有的結(jié)點(diǎn)都沒(méi)有右子樹(shù)的二叉樹(shù)
題解： C
前序確定根，中序找到根確定根的左右子樹(shù)，最后還原二叉樹(shù)為：
?
八、
8. 一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿(mǎn)足（? ）
A.所有的結(jié)點(diǎn)均無(wú)左孩子
B.所有的結(jié)點(diǎn)均無(wú)右孩子
C.只有一個(gè)葉子結(jié)點(diǎn)
D.至多只有一個(gè)結(jié)點(diǎn)
題解： C?
前序遍歷：根 左 右
后序遍歷：左 右 根
從二叉樹(shù) 前序 和 后序遍歷結(jié)果規(guī)則中可以看出，如果樹(shù)中每個(gè)節(jié)點(diǎn)只有一個(gè)孩子時(shí)，遍歷結(jié)果肯定是反的
比如下面這前序和中序序列所構(gòu)成的樹(shù)的結(jié)構(gòu):
12345
54321
?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-499144.html
朋友們、伙計(jì)們，美好的時(shí)光總是短暫的，我們本期的的分享就到此結(jié)束，最后看完別忘了留下你們彌足珍貴的三連喔，感謝大家的支持！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-499144.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)經(jīng)典例題（單選題）--＞你真的掌握二叉樹(shù)了嗎？（第二彈）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
