二叉樹(shù)的遍歷

（圖1）

（圖2）

二叉樹(shù)的遍歷運(yùn)算（遞歸定義）
(1) 先序遍歷：　　根，左子樹(shù)，右子樹(shù)　　根在先

例如圖1：271653894；圖2：ABCKDEHFJG

(2) 中序遍歷：　　左子樹(shù)，根，右子樹(shù)  　根在中

例如圖1：175632849；圖2：BKCAHEDHFG

(3) 后序遍歷：　　左子樹(shù)，右子樹(shù)，根　　根在后

例如圖1：153674982；圖2：KCBHEJGFDA

題型一：已知其中一些遍歷結(jié)果，求其他遍歷結(jié)果

題型二：統(tǒng)計(jì)ｎ個(gè)不同的點(diǎn)可以構(gòu)造多少棵不同的二叉樹(shù)?  Catalan數(shù)=C(n,2*n)/(n+1)

題型三：中綴表達(dá)式向前綴和后綴表達(dá)式的轉(zhuǎn)化

每日練習(xí)

注：題1已知先序和中序，二叉樹(shù)是唯一的。

題2已知后序和中序，二叉樹(shù)是唯一的。

題3已知先序和后序，二叉樹(shù)不是唯一的。

1、已知先序：1 2 4 3 5 7 6，  中序：2 4 1 7 5 3 6，請(qǐng)畫(huà)出整棵二叉樹(shù)。

2、已知后序：4 5 2 6 7 3 1，  中序：4 2 5 7 6 3 1，請(qǐng)畫(huà)出整棵二叉樹(shù)。

3、已知先序：1 2 3 4 5 6，    后序：3 2 5 6 4 1，請(qǐng)畫(huà)所有二叉樹(shù)的情況。

4、如果只知道先序ａｂｃ，畫(huà)出所有可能二叉樹(shù)形狀，并且計(jì)算多少種？

5、如果只知道中序ａｂｃ，畫(huà)出所有可能二叉樹(shù)形狀，并且計(jì)算多少種？

6、如果只知道后序ａｂｃ，畫(huà)出所有可能二叉樹(shù)形狀，并且計(jì)算多少種？

往年真題

1. 一顆二叉樹(shù)的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可能是（   ）。

   A．0         B．2         C．4         D． 6

2. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是：

   A) abcd*+-   B) abc+*d-   C) abc*+d-   D) -+*abcd

3. 二叉樹(shù)T，已知其先序遍歷是1 2 4 35 7 6（數(shù)字為節(jié)點(diǎn)編號(hào)，以下同），后序遍歷是4 2 7 56 3 1，則該二叉樹(shù)的中根遍歷是（    ）

 A．4 2 1 7 5 3 6    B．2 4 1 7 5 3 6     C．4 2 1 75 6 3    D．2 4 1 57 3 6

4. 二叉樹(shù)T，已知其先根遍歷是1 2 4 35 7 6（數(shù)字為結(jié)點(diǎn)編號(hào)，以下同），中根遍歷是2 4 1 57 3 6，則該二叉樹(shù)的后根遍歷是（     ）

 A. 4 2 5 7 6 3 1     B. 4 2 7 5 6 3 1     C. 7 4 2 5 6 3 1    D. 4 2 7 6 5 3 1

5. 已知7個(gè)節(jié)點(diǎn)的二叉樹(shù)的先根遍歷是1 2 4 5 6 3 7(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同), 后根遍歷是4 6 5 2 7 3 1,則該二叉樹(shù)的可能的中根遍歷是(      ) 
 A. 4 2 6 5 1 7 3      B. 4 2 5 6 1 3 7   C. 4 2 3 1 5 6 7     D. 4 2 5 6 1 7 3

6. 已知7個(gè)節(jié)點(diǎn)的二叉樹(shù)的先根遍歷是1 2 4 5 6 3 7（數(shù)字為節(jié)點(diǎn)的編號(hào)，以下同），中根遍歷是4 2 6 51 7 3，則該二叉樹(shù)的后根遍歷是（     ）
 A．4 6 5 27 3 1     B．4 6 5 2 1 3 7    C．4 2 3 1 5 4 7    D．4 6 5 3 1 7 2

7. 已知6個(gè)結(jié)點(diǎn)的二叉樹(shù)的先根遍歷是1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是3 2 5 64 1，則該二叉樹(shù)的可能的中根遍歷是（     ）

   A. 3 2 1 46 5       B. 3 21 5 4 6      C. 2 3 1 5 4 6       D. 2 31 4 6 5

二叉樹(shù)的性質(zhì)

性質(zhì)1：二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為。

性質(zhì)2：深度為k的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)(k≥1)。

性質(zhì)3：二叉樹(shù)中，葉子節(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

滿(mǎn)二叉樹(shù)

定義：一棵深度為k且有個(gè)結(jié)點(diǎn)的二又樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。

特點(diǎn)：每層都飽滿(mǎn)。

完全二叉樹(shù)

定義：除了最下層，其他每層都飽滿(mǎn)，最下層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上。

特點(diǎn)：

① 滿(mǎn)二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)；

② 在滿(mǎn)二叉樹(shù)的最下層上，從最右邊開(kāi)始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹(shù)仍然是一棵完全二叉樹(shù)。

③ 在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。④若I為結(jié)點(diǎn)編號(hào)則 如果I<>1，則其父結(jié)點(diǎn)的編號(hào)為I/2；若2*I<=n，則其左兒子（即左子樹(shù)的根結(jié)點(diǎn)）的編號(hào)為2*i；若2*i>N，則無(wú)左兒子若2*I+1<=n，則其右兒子的結(jié)點(diǎn)編號(hào)為2*i+1；若2*i+1>N，則無(wú)右兒子。

 例題1：畫(huà)一個(gè)深度為4的滿(mǎn)二叉樹(shù)。畫(huà)一個(gè)深度為4的完全二叉樹(shù)。

 例題2：具有3個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（   ）

         具有6個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（   ）

          具有8個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（   ）

          具有125個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（   ）

          具有1024個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（   ）

 例題3：完全二叉樹(shù)的結(jié)點(diǎn)數(shù)為n，求該完全二叉樹(shù)的深度（層數(shù)）。

 解：設(shè)所求完全二叉樹(shù)的深度為k。

   深度為k得完全二叉樹(shù)的前k-1層是深度為k-1的滿(mǎn)二叉樹(shù)，一共有2^(k-1)-1個(gè)結(jié)點(diǎn)。

    由于完全二叉樹(shù)深度為k，故第k層上還有若干個(gè)結(jié)點(diǎn)，因此該完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)： n>2^(k-1)-1。

   另一方面，假設(shè)節(jié)點(diǎn)最多，

由此可推出：

又因k-1和k是相鄰的兩個(gè)整數(shù)，故有。

 每日練習(xí)

1.完全二叉樹(shù)對(duì)每個(gè)節(jié)點(diǎn)從上往下，從左往右編號(hào)，第i層的第j個(gè)節(jié)點(diǎn)的編號(hào)是（ ）

A 2^i+j    B 2^i+j-1     C 2^(i-1)+j        D 2^(i-1)+j-1

2.一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的高度是（  ）

3.二叉樹(shù)是重要的數(shù)據(jù)結(jié)構(gòu)，5個(gè)點(diǎn)的不同的二叉樹(shù)有（  ）個(gè)。

A22        B 30         C  40         D 42

4.完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（  ）。

  A  2*N   B 2*N-1   C 2*N+1   D  2*N-2   E  2*N+2

5.滿(mǎn)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（  ）。

  A  N      B 2*N      C 2*N–1    D  2*N+1    E  2N–1

6.在有N個(gè)葉子節(jié)點(diǎn)的哈夫曼樹(shù)中，其節(jié)點(diǎn)總數(shù)為（?。?/span>

 A  不確定　　B  2N-1　   　C  2N+1　   　D  2N

7.一棵二叉樹(shù)高度為h，所有結(jié)點(diǎn)的度為0，或?yàn)?，則此樹(shù)最少有( )個(gè)結(jié)點(diǎn)

　  A2^(h-1)      B 2^h-1 　    C 2^h+1 　    D h+1

8.按照二叉樹(shù)的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有(    ) 種。

  A  3      B  4      C  5       D 6

9、[多選題]對(duì)一個(gè)滿(mǎn)二叉樹(shù)，m個(gè)樹(shù)葉，K個(gè)分枝結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，則：（   ）

   A．n=K+m    B．K+m=2n   C．m=K-1   D．n=2K-1

10. [多選題]關(guān)于二叉樹(shù)的正確說(shuō)法是（  ）。

A 完全二叉樹(shù)一定是滿(mǎn)二叉樹(shù)     B 滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)

C 深度為h的二叉樹(shù)最多有2^h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)

D 對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1

E 在二叉樹(shù)中，第i層的結(jié)點(diǎn)總數(shù)不超過(guò)2^(i-1)；

11. 完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為11，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（ ）

A.4    B.3   C.5    D.2    E. 6

12. 一個(gè)高度為h 的二叉樹(shù)最少結(jié)點(diǎn)數(shù)目是（         ）。

   A  2^h+1     B h    C 2^h-1    D  2^h    E  2^(h-1)

13. 設(shè)有一棵k叉樹(shù),其中只有度為0和k兩種結(jié)點(diǎn),設(shè)n0,nk分別表示度為0和度為k的結(jié)點(diǎn)個(gè)數(shù),試求出n0,nk之間的關(guān)系(n0=數(shù)學(xué)表達(dá)式,數(shù)學(xué)表達(dá)式僅含nk,k和數(shù)字)

14. 如果一棵m度樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…….有nm個(gè)度為m的結(jié)點(diǎn),則該樹(shù)中葉結(jié)點(diǎn)的的個(gè)數(shù)=______________.

棧與卡特蘭數(shù)往年真題參考答案：

1ACD 2C 3D 4D 5C 6C