快速樹的遍歷前序中序后序課件

1、樹（二）2012初賽知識點梳理4、設有一棵k叉樹，其中只有度為0和k兩種結點，設n 0 ，n k ，分別表示度為0和度為k的結點個數(shù)，試求出n 0 和n k之間的關系（n 0 = 數(shù)學表達式，數(shù)學表達式僅含n k 、k和數(shù)字）。答：n0和nk之間的關系為：n0=(k-1) nk+1。k=2n0=n2+1k=3n0=2n3+1k=4n0=3n4+110tg 滿二叉樹的葉結點個數(shù)為N，則它的結點總數(shù)為（ C ）。 A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 115tg 一個包含n個分支結點（非葉結點）的非空滿k叉樹，k=1，它的葉結點數(shù)目為：A）nk+1

2、 B）nk-1 C）(k+1)n-1 D）(k-1)n+1【分析】選擇 D考多叉樹的性質(zhì)，N0=(K-1)N+1，考試的時帶入K=2時候，驗證二叉樹能得到結果。概念：滿二叉數(shù)、完全二叉樹、均衡二叉樹、平衡二叉樹已知節(jié)點數(shù)計算二叉樹的不同形態(tài)的個數(shù)二叉樹度為0的節(jié)點個數(shù)與度為2的節(jié)點個數(shù)的關系每層節(jié)點最多是多少樹的深度為h，與樹的節(jié)點數(shù)的關系。高度為n的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹對于N2的平衡二叉樹，其前N-2層必然是完全二叉樹，又稱AVL樹二叉樹的存儲結構結點的位置與結點編號的關系：如果i=1，則i為根，無父結點；如果i1，則父結點為i/2。如

3、果2*i=N，則i的左兒子的編號為2*i。如果2*i+1BDCD L R先序遍歷序列：A B D C先序遍歷ABCDGEFH先序遍歷：ABDGCEFH順時針路徑中，第一次（左邊）遇到某個節(jié)點記錄下來中序遍歷ADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C投影DGBAECH中序遍歷：ABCDGEFHF后序遍歷ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C ABABCDGEFH順時針路徑中，遇到某個節(jié)點右邊時，記錄下來后序遍歷：CGFDHBEA表達式a+b*(c-d)-e/f 用二叉樹表示-+/a*b-efcd先序遍歷：-+a

4、*b-cd/ef波蘭式表達式a+b*(c-d)-e/f 用二叉樹表示-+/a*b-efcd中序遍歷：-+a*b-cd/ef中綴表示表達式a+b*(c-d)-e/f 用二叉樹表示-+/a*b-efcd后序遍歷：-+a*b-cd/ef逆波蘭式三種遍歷算法的比較相同點： 如果把訪問根結點這個不涉及遞歸的語句拋開，則三個遞歸算法走過的路線是一樣的。三種遍歷算法的比較不同點： 前序遍歷是每進入一層遞 歸調(diào)用時先訪問根結點， 然后再依次向它的左、右 子樹執(zhí)行遞歸調(diào)用； 中序遍歷是在執(zhí)行完左子 樹遞歸調(diào)用后再訪問根結 點，然后向它的右子樹遞 歸調(diào)用； 后序遍歷則是在從右子樹 遞歸調(diào)用退出后訪問根結 點。AE

5、BCDFHIGJ 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。AFHIGJBECD 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。AFHIGJBECD 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。AFHIGJBDEC 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。AFHIGJBECD 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAF

6、HIGJ試畫出這顆二叉樹。AHIGJBECDF 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。AHIBECDFGJ 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。ABECDFGHJI思考：先序、中序、后序序列中任意給定兩個 序列就可以畫出該二叉樹嗎？為什么？ 已知一棵二叉樹 先序遍歷序列為ABECDFGHIJ 中序遍歷序列為EBCDAFHIGJ試畫出這顆二叉樹。按層次遍歷ABECDFGHJI按層次遍歷序列：ABFECGDHJI 給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍

7、歷：DGEBHIFCA，畫出此二叉樹。【問題分析】后序遍歷中最后訪問的是根結點，所以后序遍歷DGEBHIFCA序列中A是根結點；根據(jù)中序遍歷的算法，先中序遍歷左子樹，然后再訪問根結點，最后再中序遍歷右子樹，所以中序遍歷DBGEACHFI序列中，根結點A的兩側分別是左子樹和右子樹：DBGE、CHFI。由中根序列和后根序列來確定二叉樹的結構，從而判斷先根遍歷序列及其它。例1：(NOIP 2001提高組試題)已知一棵二叉樹的結點名為大寫英文字母，其中序與后序遍歷的順序分別為：C B G E A F H D I J與C G E B H F JI D A則該二叉樹的先序遍歷的順序為解析：已知中序序列為C

8、 B G E A F H D I (1) 后序序列為C G EBH F JI D A。(2)由(2)知：根結點為A 由(1)知：A的左子樹中序序列為C B G E (3)A的右子樹中序序列為F H D I J(4)由(2)知：A的左子樹后序序列為C G E B(5) A的右子樹后序序列為H F J I D(6)由(5)(6)知：A的左子樹根結點為B，A的右子樹根結點為D由(3)(4)知：B的左子樹為C，右子樹中序序列為G E D的左子樹中序序列為F H，右子樹中序序列為I J由(5)(6)知：B的右子樹后序序列為G E，即根結點為ED的左子樹后序序列為H F，即根結點為FD的右子樹后序序列為J

9、I，即根結點為I綜上可推出二叉樹的結構如圖所示故該二叉樹的先序遍歷序列為：A B C E G D F H I J 由前序序列和中序序列來確定一棵二叉樹，從而判斷后序序列及其它例2：(NOIP 2004提高組試題)二叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為( )。 A4 2 5 7 6 3 1 B4 2 7 5 6 3 1 C4 2 7 5 3 6 1 D4 7 2 3 5 6 1 E4 5 2 6 3 7 l 解析：已知前序遍歷序列為1 2 4 3 5 7 6 (1) 中序遍歷序列為4 2 l 5 7 3 6 (2)

10、由(1)知：根結點為1由(2)知：1的左子樹中序序列為4 2 (3) 右子樹中序序列為5 7 3 6 (4)由(1)知1的左子樹先序序列為2 4 (5) 1的右子樹先序序列為3 5 7 6 (6) 由(3)(5)知：1的左子樹根結點為2，2的左子樹為4由(4)(6)知：1的右子樹根結點為3由(4)知：3的左子樹中序序列為5 7 (7) 3的右子樹為6 由(6)(7)知：3的左子樹根結點為5，且5的右子樹為7 綜上對應的一棵二叉樹的結構如圖所示： 故其后序遍歷序列為：4 2 7 5 6 3 1 從而答案選B 由先根序列和后根序列來推斷二叉樹的結構，從而判斷中根遍歷序列以及其他例3：(NOIP 2

11、007提高組第14題)已知7個結點的二叉樹的先根遍歷是1 2 4 5 6 3 7 f數(shù)字為結點的編號，以下同)，后根遍歷是4 6 5 27 3 1，則該二叉樹的可能的中根遍歷是( )。A4 2 6 5 1 7 3 B4 2 5 6 1 3 7 C4 2 3 1 5 4 7 D4 2 5 6 1 7 3解析：先根遍歷序列是1 2 4 5 6 3 7 (1) 后根遍歷序列是4 6 5 2 7 3 1(2)由(1)和(2)知：根結點為l，1的左子樹根結點是2，右子樹根結點是3，結點4是結點2的左子樹，可以判斷結點5是結點2的右子樹的根結點，但結點6可能是結點5的左子樹，也可能是它的右子樹，同樣結點7

12、可能是結點3的左子樹，也可能是它的右子樹。對應的二叉樹的結構可能是如下四種：圖的中序遍歷序列是：4 2 6 5 1 7 3 圖的中序遍歷序列是：4 2 5 6 1 7 3 圖的中序遍歷序列是：4 2 6 5 1 3 7 圖的中序遍歷序列是：4 2 5 6 1 3 7 故此題的答案應選A B D 通過二叉樹的寬度優(yōu)先遍歷和樹中結點的最大深度及結點之間的關系來判斷樹的結構，從而解決有關問題。例5：(NOIP 2005提高組試題)二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結點，D是G的父結點，F(xiàn)是I的父結點，樹中所有結點的最大深度為3(根結點深度設為0)，可知E的

13、父結點可能是 ( )。 A B B C C D D E F 解析：二叉樹的寬度優(yōu)先遍歷就是按層遍歷，從根結點自上而下，自左向右訪問樹中的每一個結點。由題目可知A是根結點，又知A是C的父結點，可以推知B是A的左子樹的根結點，C是A的右子樹的根結點。又知D是G的父結點，F(xiàn)是I的父結點，樹中所有結點的最大深度為3，故E結點可能是B結點的右子樹，也可能是G結點的左子樹。二叉樹的部分結構圖為下圖所示： 故E的父結點可能是B，也可能是C。歷屆試題(13tg)已知7個節(jié)點的二叉樹的先根遍歷是1 2 4 5 6 3 7（數(shù)字為節(jié)點的編號，以下同），中根遍歷是4 2 6 5 1 7 3，則該二叉樹的后根遍歷是（

14、 ）。 A4 6 5 2 7 3 1 B4 6 5 2 1 3 7 C4 2 3 1 5 4 7 D4 6 5 3 1 7 2(12tg_多項)已知 6 個結點的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結點的編號，以下同），后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5(11tg _多項)二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結點，D 是G 的父結點，F(xiàn) 是I 的父結點，樹中所有結點的最大深度為3（根結點深度設為0），可知E的父結點可能是（ ）。 A. A B. B C. C D. D E. FA B C B C 歷屆試題(10tg) 滿二叉樹的葉結點個數(shù)為N，則它的結點總數(shù)為（ ）。 A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 1(10tg) 叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2