哈工大數(shù)據(jù)結(jié)構(gòu)6

1、第第6章章 樹和二叉樹樹和二叉樹樹是一種重要的非線性結(jié)構(gòu)。樹是一種重要的非線性結(jié)構(gòu)。樹是以分支關(guān)系定義的層次結(jié)構(gòu)，其中以二叉樹最為常用。樹是以分支關(guān)系定義的層次結(jié)構(gòu)，其中以二叉樹最為常用。樹型結(jié)構(gòu)在計(jì)算機(jī)中有廣泛應(yīng)用：樹型結(jié)構(gòu)在計(jì)算機(jī)中有廣泛應(yīng)用： 在微機(jī)操作系統(tǒng)中，文件和文件夾以樹形結(jié)構(gòu)存儲(chǔ)。在微機(jī)操作系統(tǒng)中，文件和文件夾以樹形結(jié)構(gòu)存儲(chǔ)。 在編譯系統(tǒng)中，可以用樹來表示源程序的語法結(jié)構(gòu)。在編譯系統(tǒng)中，可以用樹來表示源程序的語法結(jié)構(gòu)。 在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是信息的重要組織形式。在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是信息的重要組織形式。6.1 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.2 6.2 二

2、叉樹二叉樹6.3 6.3 遍歷二叉樹遍歷二叉樹6.4 6.4 恢復(fù)二叉樹恢復(fù)二叉樹6.7 6.7 樹和森林樹和森林6.8 6.8 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用6.5 6.5 線索二叉樹線索二叉樹6.6 6.6 二叉樹的基本運(yùn)算及其應(yīng)用二叉樹的基本運(yùn)算及其應(yīng)用6.1 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m

3、 (m0)個(gè)互不相交的個(gè)互不相交的 有限集有限集T1, T2, , Tm， 其中每一棵子集本身又是其中每一棵子集本身又是 一棵符合本定義的樹，稱為根一棵符合本定義的樹，稱為根 root 的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：1. 1. 樹的定義樹的定義 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類 Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(jié)點(diǎn) 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最

4、左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p,

5、i, c) / 將以將以c為根的樹插入為結(jié)點(diǎn)為根的樹插入為結(jié)點(diǎn) p 的第的第i 棵子樹棵子樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i 棵子樹棵子樹ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹根例例: : 樹的特點(diǎn)：樹的特點(diǎn)： 在非空樹中：在非空樹中：樹中至少有一個(gè)結(jié)點(diǎn)樹中至少有一個(gè)結(jié)點(diǎn)根。根。樹中各子樹是互不相交的集合。樹中各子樹

6、是互不相交的集合。 樹的定義是樹的定義是遞歸的遞歸的，即在樹的定義中又用到樹的概念，即在樹的定義中又用到樹的概念，正好反映了樹的固有特性。正好反映了樹的固有特性。 A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹() 有確定的根；有確定的根；() 樹根和子樹根之間為有向關(guān)系。樹根和子樹根之間為有向關(guān)系。有向樹：有向樹：有序樹：有序樹：子樹之間存在確定的次序關(guān)系。子樹之間存在確定的次序關(guān)系。無序樹：無序樹：子樹之間不存在確定的次序關(guān)系。子樹之間不存在確定的次序關(guān)系。對(duì)比對(duì)比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型

7、結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )結(jié)點(diǎn)結(jié)點(diǎn)(node)表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的 分支。分支。結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。葉子葉子(leaf)度為度為0的結(jié)點(diǎn)。的結(jié)點(diǎn)。孩子孩子(ch

8、ild)結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子。結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子。雙親雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親或父結(jié)點(diǎn)。孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親或父結(jié)點(diǎn)。兄弟兄弟(sibling)同一雙親的孩子。同一雙親的孩子。樹的度樹的度 一棵樹中各結(jié)點(diǎn)的度的最大值稱為該樹的度。一棵樹中各結(jié)點(diǎn)的度的最大值稱為該樹的度。2.2.樹的基本術(shù)語樹的基本術(shù)語結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)根結(jié)點(diǎn)的層數(shù)為根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于，其余結(jié)點(diǎn)的層數(shù)等于 它雙親結(jié)點(diǎn)的層數(shù)加它雙親結(jié)點(diǎn)的層數(shù)加1。樹的深度樹的深度(depth)樹中結(jié)點(diǎn)的最大層次數(shù)。樹中結(jié)點(diǎn)的最大層次數(shù)。森林森林(fore

9、st)m(m 0)棵互不相交的樹的集合棵互不相交的樹的集合。( (從根到結(jié)點(diǎn)的從根到結(jié)點(diǎn)的) )路徑路徑由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。ABCDEFGHIJMKL任何一棵非空樹是一個(gè)二元組：任何一棵非空樹是一個(gè)二元組： Tree = Tree = （rootroot，F(xiàn) F）其中：其中：root root 被稱為根結(jié)點(diǎn)。被稱為根結(jié)點(diǎn)。 F F 被稱為子樹森林。被稱為子樹森林。森林：是森林：是m m（m0m0）棵互不相棵互不相 交的樹的集合。交的樹的集合。ArootBCDEFGHIJMKLF任何一棵樹，只要?jiǎng)h去根結(jié)點(diǎn)就成了森林。如圖：任何一棵樹，只要?jiǎng)h去根結(jié)點(diǎn)

10、就成了森林。如圖：(a) 樹樹 (b) 移去根結(jié)點(diǎn)后成為森林移去根結(jié)點(diǎn)后成為森林ABCDEFGHIJKLM結(jié)點(diǎn)結(jié)點(diǎn)A的度：的度：3結(jié)點(diǎn)結(jié)點(diǎn)B的度：的度：2結(jié)點(diǎn)結(jié)點(diǎn)M的度：的度：0葉子：葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)結(jié)點(diǎn)A的孩子：的孩子：B，C，D結(jié)點(diǎn)結(jié)點(diǎn)B的孩子：的孩子：E，F(xiàn)結(jié)點(diǎn)結(jié)點(diǎn)I的雙親：的雙親：D結(jié)點(diǎn)結(jié)點(diǎn)L的雙親：的雙親：E結(jié)點(diǎn)結(jié)點(diǎn)B，C，D為兄弟為兄弟結(jié)點(diǎn)結(jié)點(diǎn)K，L為兄弟為兄弟樹的度：樹的度：3結(jié)點(diǎn)結(jié)點(diǎn)A的層次：的層次：1結(jié)點(diǎn)結(jié)點(diǎn)M的層次：的層次：4樹的深度：樹的深度：4結(jié)點(diǎn)結(jié)點(diǎn)F，G為堂兄弟為堂兄弟結(jié)點(diǎn)結(jié)點(diǎn)A是結(jié)點(diǎn)是結(jié)點(diǎn)F，G的祖先的祖先bacghdefij樹型表示樹型表示樹

11、的表示：樹的表示：abdeijfcgh嵌套集合表示嵌套集合表示嵌套括號(hào)表示嵌套括號(hào)表示ijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) ) )6.2 6.2 二叉樹二叉樹1. 二叉樹的定義二叉樹的定義 二叉樹是有二叉樹是有n（n=0）個(gè)結(jié)點(diǎn)的有限集合。）個(gè)結(jié)點(diǎn)的有限集合。 （1）該集合或者為空（）該集合或者為空（n=0）；）； （2）該集合或者只有一個(gè)根結(jié)點(diǎn)；）該集合或者只有一個(gè)根結(jié)點(diǎn)； （3）該集合或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)不相交的分別稱為）該集合或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)不相交的分別稱為 左子樹和右子樹組成的非空樹；左子樹和右子樹組成的非空樹； （4）左子樹和

12、右子樹同樣又都是二叉樹。）左子樹和右子樹同樣又都是二叉樹。二叉樹的定義是遞歸的：二叉樹的定義是遞歸的：在一棵非空的二叉樹中，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，在一棵非空的二叉樹中，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，分別稱為左子樹和右子樹，左子樹和右子樹同樣又都是二分別稱為左子樹和右子樹，左子樹和右子樹同樣又都是二叉樹。叉樹。二叉樹是有序樹：二叉樹是有序樹： 二叉樹的左右子樹的次序不能交換。二叉樹的左右子樹的次序不能交換。ABCDEFGHK根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子樹二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空樹只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左

13、右子左右子樹均不樹均不為空樹為空樹 二叉樹的基本操作：二叉樹的基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrder

14、Traverse(T, Visit(); InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);二叉樹的二叉樹的主要主要基本操作：基本操作： （1） CreateBT（）：（）： 創(chuàng)建一棵二叉樹。創(chuàng)建一棵二叉樹。 （2）ShowTree(BT *T)：按凹入法顯示二叉樹。：按凹入法顯示二叉樹。（3） Preord

15、er(BT *T)：按先序（根、左、右）遍歷二叉樹上：按先序（根、左、右）遍歷二叉樹上 所有結(jié)點(diǎn)。所有結(jié)點(diǎn)。（4） Inorder(BT *T)： 按中序（左、根、右）遍歷二叉樹上按中序（左、根、右）遍歷二叉樹上 所有結(jié)點(diǎn)。所有結(jié)點(diǎn)。（5）Postorder(BT *T)：按后序（左、右、根）遍歷二叉樹上：按后序（左、右、根）遍歷二叉樹上 所有結(jié)點(diǎn)。所有結(jié)點(diǎn)。 （6）Levelorder(BT *T)：按層次遍歷二叉樹上所有結(jié)點(diǎn)。：按層次遍歷二叉樹上所有結(jié)點(diǎn)。（7）Leafnum(BT *T)： 求二叉樹葉子結(jié)點(diǎn)總數(shù)。求二叉樹葉子結(jié)點(diǎn)總數(shù)。（8）TreeDepth(BT *T)： 求二叉樹的深

16、度。求二叉樹的深度。2. 二叉樹的性質(zhì)二叉樹的性質(zhì) 性質(zhì)性質(zhì)1：一棵非空二叉樹的第：一棵非空二叉樹的第 i 層上最多有層上最多有 2i1 個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i 1）。）。證明：用歸納法證明之證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，時(shí)，只有一個(gè)根結(jié)點(diǎn)， 成成立立 假設(shè)對(duì)所有假設(shè)對(duì)所有j(1 ji)命題成立，即第命題成立，即第j層上至多有層上至多有 個(gè)個(gè)結(jié)點(diǎn)結(jié)點(diǎn)。那么，第那么，第i-1層至多有層至多有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。須證明須證明 j=i 時(shí)命題也成立。時(shí)命題也成立。 因?yàn)橐驗(yàn)槎鏄涿總€(gè)結(jié)點(diǎn)的度至多為二叉樹每個(gè)結(jié)點(diǎn)的度至多為2 第第i層上最大結(jié)點(diǎn)數(shù)是第層上最大結(jié)點(diǎn)數(shù)是第i-1層的層的2倍，即

17、倍，即 故命題得證故命題得證。12201i12j22i12222ii性質(zhì)性質(zhì)2： 深度為深度為 k 的二叉樹中，最多具有的二叉樹中，最多具有 2k - 1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。證明：證明： 根據(jù)性質(zhì)根據(jù)性質(zhì)1，當(dāng)深度為，當(dāng)深度為 k 的二叉樹每一層都達(dá)到最多結(jié)點(diǎn)的二叉樹每一層都達(dá)到最多結(jié)點(diǎn)時(shí)，它的和最大，即：時(shí)，它的和最大，即：122)(111kkikiii層的最大結(jié)點(diǎn)數(shù)第兩類特殊的二叉樹：兩類特殊的二叉樹：滿二叉樹：滿二叉樹：定義：一棵深度為定義：一棵深度為 k 且有且有 2k 1個(gè)結(jié)點(diǎn)的二叉樹稱為個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹滿二叉樹。特點(diǎn)：滿二叉樹每一層上的結(jié)點(diǎn)都具有最大的結(jié)點(diǎn)數(shù)。特點(diǎn)：滿二叉樹

18、每一層上的結(jié)點(diǎn)都具有最大的結(jié)點(diǎn)數(shù)。123114589121367101415深度為深度為 k=4 k=4 的滿二叉樹的滿二叉樹完全二叉樹：完全二叉樹：定義：定義：深度為深度為 k k，有有 n n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn) 都與深度為都與深度為 k k 的滿二叉樹中編號(hào)從的滿二叉樹中編號(hào)從 1 1 至至 n n 的結(jié)點(diǎn)一一對(duì)的結(jié)點(diǎn)一一對(duì) 應(yīng)時(shí)，稱為應(yīng)時(shí)，稱為完全二叉樹。完全二叉樹。特點(diǎn)：特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。 對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次

19、為 L L，則其左分則其左分 支下子孫的最大層次必為支下子孫的最大層次必為 L L 或或 L+1L+1完全二叉樹完全二叉樹1231145891267101234567123456特點(diǎn)：完全二叉樹除最后一層外，其余各層都是滿的；特點(diǎn)：完全二叉樹除最后一層外，其余各層都是滿的； 并且最后一層或者為滿，或者僅在右邊缺少連續(xù)若干并且最后一層或者為滿，或者僅在右邊缺少連續(xù)若干 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)3：1log2nn深度為個(gè)結(jié)點(diǎn)的完全二叉樹的具有不大于不大于x的的最大整數(shù)最大整數(shù)證明：證明：設(shè)完全二叉樹的深度為設(shè)完全二叉樹的深度為 k k，結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為 n n， 由性質(zhì)由性質(zhì)2 2和完全二叉樹的定

20、義可知：和完全二叉樹的定義可知： 2k-1-1n 2k-1 即即 2k-1 n 2k 兩邊取對(duì)數(shù)有：兩邊取對(duì)數(shù)有： k-1 log2n 1, 1, 則序號(hào)為則序號(hào)為 i i 的結(jié)點(diǎn)的父結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的父結(jié)點(diǎn)的序號(hào)為 i/2i/2。(2)(2)若若 2 2i in n， 則序號(hào)為則序號(hào)為 i i 的結(jié)點(diǎn)無左孩子。的結(jié)點(diǎn)無左孩子。(3)(3)若若 2 2i+1i+1n n，則序號(hào)為則序號(hào)為 i i 的結(jié)點(diǎn)無右孩子。的結(jié)點(diǎn)無右孩子。性質(zhì)性質(zhì)5：對(duì)任何一棵二叉樹對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為如果其終端結(jié)點(diǎn)數(shù)為 n0，度為度為 2 的的 結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為 n2，則則 n0=n2+1 。證明：

21、證明：n1為二叉樹為二叉樹 T 中度為中度為 1 的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2 所以：其結(jié)點(diǎn)總數(shù)所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè) 分支進(jìn)入分支進(jìn)入 設(shè)設(shè)B為分支總數(shù)，則為分支總數(shù)，則 n=B+1 又：分支由度為又：分支由度為1和度為和度為2的結(jié)點(diǎn)射出，的結(jié)點(diǎn)射出， B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+13. 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)(1)(1) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 一維數(shù)

22、組存儲(chǔ)法：一維數(shù)組存儲(chǔ)法：實(shí)現(xiàn)：按完全二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素。實(shí)現(xiàn)：按完全二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素。特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中（特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中（i 的左子的左子2i，右子，右子2i+1）。）。abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11特點(diǎn)：特點(diǎn)： 浪費(fèi)空間，適于存滿二叉樹和完全二叉樹。浪費(fèi)空間，適于存滿二叉樹和完全二叉樹。aceda 0 c 0 0 0 d 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1400e無須無須按完全

23、二叉樹的結(jié)點(diǎn)層次編號(hào)，依次按編號(hào)存放二叉樹中的數(shù)據(jù)按完全二叉樹的結(jié)點(diǎn)層次編號(hào)，依次按編號(hào)存放二叉樹中的數(shù)據(jù)元素即可。元素即可。結(jié)點(diǎn)數(shù)據(jù)，左子編號(hào)，右子編號(hào)均要存儲(chǔ)。故可采用長度為結(jié)點(diǎn)數(shù)據(jù)，左子編號(hào)，右子編號(hào)均要存儲(chǔ)。故可采用長度為 n 的結(jié)構(gòu)的結(jié)構(gòu) 數(shù)組存放。數(shù)組存放。n為結(jié)點(diǎn)個(gè)數(shù)。為結(jié)點(diǎn)個(gè)數(shù)。結(jié)構(gòu)數(shù)組相當(dāng)于一個(gè)二維構(gòu)造結(jié)構(gòu)數(shù)組相當(dāng)于一個(gè)二維構(gòu)造, 第一維是結(jié)構(gòu)數(shù)組元素第一維是結(jié)構(gòu)數(shù)組元素, 每個(gè)元素是一每個(gè)元素是一 個(gè)結(jié)構(gòu)變量個(gè)結(jié)構(gòu)變量, 第二維是結(jié)構(gòu)成員。第二維是結(jié)構(gòu)成員。 abcdefg0123456Data0Lno1Rno20a121b342c-1-13d-1-14e565f-1-16

24、g-1-1 二維數(shù)組存儲(chǔ)法：二維數(shù)組存儲(chǔ)法：順序存儲(chǔ)結(jié)構(gòu)小結(jié)：順序存儲(chǔ)結(jié)構(gòu)小結(jié)：滿二叉樹或完全二叉樹可采用一維數(shù)組；滿二叉樹或完全二叉樹可采用一維數(shù)組；結(jié)點(diǎn)少，層數(shù)高可采用二維數(shù)組；結(jié)點(diǎn)少，層數(shù)高可采用二維數(shù)組；查找方便，找孩子結(jié)點(diǎn)及父結(jié)點(diǎn)均方便；查找方便，找孩子結(jié)點(diǎn)及父結(jié)點(diǎn)均方便；缺點(diǎn)：空間擴(kuò)充不便；插入和刪除須大量移動(dòng)數(shù)據(jù)。缺點(diǎn)：空間擴(kuò)充不便；插入和刪除須大量移動(dòng)數(shù)據(jù)。 二叉鏈表：二叉鏈表：結(jié)點(diǎn)組成：結(jié)點(diǎn)組成：lchild data rchild ABCDEFG AB C D E F G其中：其中：data為數(shù)據(jù)域；為數(shù)據(jù)域； lchild為左指針域，放左子樹的地址；為左指針域，放左子樹的

25、地址； rchild為右指針域，放右子樹的地址；為右指針域，放右子樹的地址；BT：名字，根，入口：名字，根，入口(2)(2) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表的定義：二叉鏈表的定義：typedef struct node datatype data; struct node *lchild, *rchild;BT;三叉鏈表：三叉鏈表：三叉鏈表的定義：三叉鏈表的定義： typedef struct node datatype data; struct node *lchild, *rchild, *parent;TT;lchild data parent rchildABCDEFG A B C

26、 D E F G結(jié)點(diǎn)組成：結(jié)點(diǎn)組成：三叉鏈表的靜態(tài)結(jié)構(gòu)：三叉鏈表的靜態(tài)結(jié)構(gòu)：ABCDFErootdata parent leftChild rightChild012345 6.3 遍歷二叉樹遍歷二叉樹1.1.問題的提出問題的提出 順著某一條搜索路徑順著某一條搜索路徑巡訪巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次均被訪問一次，而且而且僅被訪問一次僅被訪問一次。 訪問的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。訪問的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。 遍歷是任何類型均有的操作。遍歷是任何類型均有的操作。 對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(

27、 (因?yàn)槊總€(gè)結(jié)點(diǎn)均只有因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼一個(gè)后繼) )，故不需要另加討論。，故不需要另加討論。 而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。遍歷即按什么樣的搜索路徑遍歷的問題。 對(duì)二叉樹而言，可以有三條搜索路徑：對(duì)二叉樹而言，可以有三條搜索路徑： 1先上后下的按層次遍歷；先上后下的按層次遍歷； 2先左（子樹）后右（子樹）的遍歷；先左（子樹）后右（子樹）的遍歷； 3先右（子樹）后左（子樹）的遍歷。先右（子樹）后左（子樹）的遍歷。先先序（根）的遍歷算法序（根）的遍歷算法中中序（根）的遍歷算法序（

28、根）的遍歷算法后后序（根）的遍歷算法序（根）的遍歷算法2. 先左后右遍歷二叉樹的算法先左后右遍歷二叉樹的算法(1) 先序（根）遍歷先序（根）遍歷 （DLR）先序遍歷也稱為先根遍歷。其遞歸過程為：先序遍歷也稱為先根遍歷。其遞歸過程為：若二叉樹為空，則遍歷結(jié)束，返回。若二叉樹為空，則遍歷結(jié)束，返回。否則：否則： （1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2）先序遍歷根結(jié)點(diǎn)的左子樹；）先序遍歷根結(jié)點(diǎn)的左子樹； （3）先序遍歷根結(jié)點(diǎn)的右子樹。）先序遍歷根結(jié)點(diǎn)的右子樹。3. 遍歷二叉樹的遞歸算法遍歷二叉樹的遞歸算法void Preorder(BT *T) / 先序遍歷先序遍歷 T 所指向的二叉樹所指向的二叉樹

29、 if (T= =NULL) return; / 本函數(shù)調(diào)用結(jié)束本函數(shù)調(diào)用結(jié)束 printf(T-data); / 輸出結(jié)點(diǎn)的數(shù)據(jù)域輸出結(jié)點(diǎn)的數(shù)據(jù)域 Preorder(T-lchild); / 先序遞歸遍歷左子樹先序遞歸遍歷左子樹 Preorder(T-rchild); / 先序遞歸遍歷右子樹先序遞歸遍歷右子樹 / 本函數(shù)調(diào)用結(jié)束本函數(shù)調(diào)用結(jié)束typedef struct node datatype data; struct node *lchild, *rchild;BT;算法描述：算法描述：ADBCD L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C

30、先序遍歷先序遍歷:void preorder(BT *T) if(T=NULL) return; printf(%dt,T-data); preorder(T-lchild); preorder(T-rchild); 主程序主程序Pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返

31、回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D C(2) 中序（根）遍歷中序（根）遍歷 （LDR）中序遍歷也稱為中根遍歷。其遞歸過程為：中序遍歷也稱為中根遍歷。其遞歸過程為：若二叉樹為空，則遍歷結(jié)束，返回。若二叉樹為空，則遍歷結(jié)束，返回。否則：否則： （1）中序遍歷根結(jié)點(diǎn)的左子樹；）中序遍歷根結(jié)點(diǎn)的左子樹； （2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （3）中序遍歷根結(jié)點(diǎn)的右子樹。）中序遍歷根結(jié)點(diǎn)的右子樹。算法描述：算法描述：typedef struct node datatype data; struct node *lchild, *rchild;BT;void

32、Inorder(BT *T) / 中序遍歷中序遍歷 T 所指向的二叉樹所指向的二叉樹 if (T = =NULL) return; / 本函數(shù)調(diào)用結(jié)束本函數(shù)調(diào)用結(jié)束 Inorder(T-lchild); / 中序遞歸遍歷左子樹中序遞歸遍歷左子樹 printf(T-data); / 輸出結(jié)點(diǎn)的數(shù)據(jù)域輸出結(jié)點(diǎn)的數(shù)據(jù)域 Inorder(T-rchild); / 中序遞歸遍歷右子樹中序遞歸遍歷右子樹 / 本函數(shù)調(diào)用結(jié)束本函數(shù)調(diào)用結(jié)束 ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A C 中序遍歷中序遍歷:(3) 后序（根）遍歷后序（根）遍歷 （LRD）后序

33、遍歷也稱為后根遍歷。其遞歸過程為：后序遍歷也稱為后根遍歷。其遞歸過程為：若二叉樹為空，則遍歷結(jié)束，返回。若二叉樹為空，則遍歷結(jié)束，返回。否則：否則： （1）后序遍歷根結(jié)點(diǎn)的左子樹；）后序遍歷根結(jié)點(diǎn)的左子樹； （2）后序遍歷根結(jié)點(diǎn)的右子樹。）后序遍歷根結(jié)點(diǎn)的右子樹。 （3）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；算法描述：算法描述：typedef struct node datatype data; struct node *lchild, *rchild;BT;void Postorder(BT *T) / 后序遍歷后序遍歷 T 所指向的二叉樹所指向的二叉樹 if (T = =NULL) return; /

34、 本函數(shù)調(diào)用結(jié)束本函數(shù)調(diào)用結(jié)束 Postorder(T-lchild); / 后序遞歸遍歷左子樹后序遞歸遍歷左子樹 Postorder(T-rchild); / 后序遞歸遍歷右子樹后序遞歸遍歷右子樹 printf(T-data); / 輸出結(jié)點(diǎn)的數(shù)據(jù)域輸出結(jié)點(diǎn)的數(shù)據(jù)域 / 本函數(shù)調(diào)用結(jié)束本函數(shù)調(diào)用結(jié)束ADBC L R DL R DL R DADCL R D后序遍歷序列：后序遍歷序列： D B C A 后序遍歷后序遍歷:B（1 1）先序遍歷的非遞歸算法）先序遍歷的非遞歸算法* * 提高運(yùn)算效率提高運(yùn)算效率基于棧先序遍歷的非遞歸算法：基于棧先序遍歷的非遞歸算法：引入棧保存每個(gè)結(jié)點(diǎn)的右指針引入棧保存

35、每個(gè)結(jié)點(diǎn)的右指針?biāo)惴ǎ核惴ǎ? 1）訪問結(jié)點(diǎn)。）訪問結(jié)點(diǎn)。2 2）結(jié)點(diǎn)的右指針入棧。）結(jié)點(diǎn)的右指針入棧。3 3）若結(jié)點(diǎn)的左指針不空，遍歷左子樹。）若結(jié)點(diǎn)的左指針不空，遍歷左子樹。4 4）右指針出棧。）右指針出棧。5 5）若結(jié)點(diǎn)的右指針不空，遍歷右子樹。）若結(jié)點(diǎn)的右指針不空，遍歷右子樹。4. 遍歷二叉樹的非遞歸算法遍歷二叉樹的非遞歸算法（2 2）中序遍歷的非遞歸算法）中序遍歷的非遞歸算法基于棧中序遍歷的非遞歸算法：基于棧中序遍歷的非遞歸算法： 引入棧保存每個(gè)結(jié)點(diǎn)及右指針，由于知道結(jié)點(diǎn)的指針便引入棧保存每個(gè)結(jié)點(diǎn)及右指針，由于知道結(jié)點(diǎn)的指針便可知結(jié)點(diǎn)和其右指針，故只須結(jié)點(diǎn)的指針入棧?？芍Y(jié)點(diǎn)和其右指

36、針，故只須結(jié)點(diǎn)的指針入棧。算法：算法：1 1）結(jié)點(diǎn)右指針入棧。）結(jié)點(diǎn)右指針入棧。2 2）若結(jié)點(diǎn)的左指針不空，遍歷左子樹。）若結(jié)點(diǎn)的左指針不空，遍歷左子樹。3 3）指針出棧。）指針出棧。4 4）訪問結(jié)點(diǎn)，若結(jié)點(diǎn)的右指針不空，遍歷右子樹。）訪問結(jié)點(diǎn)，若結(jié)點(diǎn)的右指針不空，遍歷右子樹。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：void inorderse(BT *bt) int i=0; /棧的初始化棧的初始化 BT *p, *sM; /保存每個(gè)結(jié)點(diǎn)的指針的棧保存每個(gè)結(jié)點(diǎn)的指針的棧 p=bt; do while ( p!=NULL ) si+=p; /結(jié)點(diǎn)的指針入棧結(jié)點(diǎn)的指針入棧 p=p-lchild; /進(jìn)入左子樹進(jìn)入左

37、子樹 /左子樹為空，退出左子樹為空，退出 if ( i0 ) /如果棧不空如果棧不空 p=s-i; /結(jié)點(diǎn)的指針結(jié)點(diǎn)的指針出棧出棧 printf(“%dt”,p-data); /訪問出棧的結(jié)點(diǎn)訪問出棧的結(jié)點(diǎn) p=p-rchild; while(i0|p!=NULL); /右子樹為空同時(shí)棧右子樹為空同時(shí)?？眨Y(jié)束循環(huán)空，結(jié)束循環(huán)非遞歸算法棧操作圖非遞歸算法棧操作圖ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)P=nullABCDEFGiP-AP-B訪問：訪問：C(4)pABCDEFGiP-A訪問：訪問：C B(5)ABCDEFGiP-

38、AP-D訪問：訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：訪問：C Bp(7)ABCDEFGiP-AP-D訪問：訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：訪問：C B E Gp(10)ABCDEFGiP-A訪問：訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：訪問：C B E G D F Ap(14)i訪問：訪問：C B E G D F A

39、p=NULLABCDEFG(15)5. 層次遍歷二叉樹的算法層次遍歷二叉樹的算法 按照自上而下（從根結(jié)點(diǎn)開始），從左到右的順序逐層訪問按照自上而下（從根結(jié)點(diǎn)開始），從左到右的順序逐層訪問二叉樹上的所有結(jié)點(diǎn)，稱為按層次遍歷。二叉樹上的所有結(jié)點(diǎn)，稱為按層次遍歷。 按層次遍歷時(shí)，當(dāng)一層結(jié)點(diǎn)訪問完后，接著訪問下一層的結(jié)按層次遍歷時(shí)，當(dāng)一層結(jié)點(diǎn)訪問完后，接著訪問下一層的結(jié)點(diǎn)，先遇到的結(jié)點(diǎn)先訪問，這與點(diǎn)，先遇到的結(jié)點(diǎn)先訪問，這與隊(duì)列隊(duì)列的操作原則是一致的。在層的操作原則是一致的。在層次遍歷時(shí)，可設(shè)置一個(gè)數(shù)組來模擬隊(duì)列，用于保存次遍歷時(shí)，可設(shè)置一個(gè)數(shù)組來模擬隊(duì)列，用于保存被訪問結(jié)點(diǎn)被訪問結(jié)點(diǎn)的的子結(jié)點(diǎn)的地址

40、子結(jié)點(diǎn)的地址。 遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)指針入隊(duì)列根結(jié)點(diǎn)指針入隊(duì)列，然，然后從隊(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：后從隊(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：（1）訪問該元素所指結(jié)點(diǎn)；）訪問該元素所指結(jié)點(diǎn)；（2）若該元素所指結(jié)點(diǎn)的）若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空左、右孩子結(jié)點(diǎn)非空，則將該元素所，則將該元素所 指結(jié)點(diǎn)的左孩子指針和右孩子指針依次入隊(duì)。指結(jié)點(diǎn)的左孩子指針和右孩子指針依次入隊(duì)。 此過程不斷進(jìn)行，直到隊(duì)空為止。此過程不斷進(jìn)行，直到隊(duì)空為止。 在層次遍歷算法中，以二叉鏈表方式存儲(chǔ)，在層次遍歷算法中，以二叉鏈表方式

41、存儲(chǔ)，lchild和和rchild分別是被訪問結(jié)點(diǎn)的左、右指針。一維數(shù)組分別是被訪問結(jié)點(diǎn)的左、右指針。一維數(shù)組 qMAXLEN 用用以實(shí)現(xiàn)隊(duì)列。以實(shí)現(xiàn)隊(duì)列。算法描述：算法描述： void Levelorder(BT *T) / 按層次遍歷二叉樹按層次遍歷二叉樹BT, T 為指向根結(jié)點(diǎn)的指針為指向根結(jié)點(diǎn)的指針 int i,j; BT *qMAXLEN,*p; / q為指針數(shù)組用以模擬隊(duì)列為指針數(shù)組用以模擬隊(duì)列,每個(gè)元素均為指向每個(gè)元素均為指向BT類型的類型的 指針指針, 用來存放結(jié)點(diǎn)地址用來存放結(jié)點(diǎn)地址 p=T; if (p!=NULL) / 若二叉樹非空，則根結(jié)點(diǎn)地址入隊(duì)若二叉樹非空，則根結(jié)點(diǎn)

42、地址入隊(duì) i=1;qi=p;j=2; / i 指向?qū)︻^，指向?qū)︻^，j 指向?qū)ξ仓赶驅(qū)ξ?while (i!=j) / 當(dāng)隊(duì)列不為空時(shí)執(zhí)行循環(huán)當(dāng)隊(duì)列不為空時(shí)執(zhí)行循環(huán) p=qi; printf(p-data); / 訪問隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)域訪問隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)域 if( p-lchild!=NULL) qj=p-lchild; j+; / 將出隊(duì)結(jié)點(diǎn)的左孩子的地址入隊(duì)將出隊(duì)結(jié)點(diǎn)的左孩子的地址入隊(duì) if(p-rchild!=NULL) qj=p-rchild; j+; / 將出隊(duì)結(jié)點(diǎn)的右孩子的地址入隊(duì)將出隊(duì)結(jié)點(diǎn)的右孩子的地址入隊(duì) i+; 層次遍歷層次遍歷:ABCDEHIFGK層次遍歷的序列層次遍歷的序列:

43、 A B C D E F G H I K例：例： 有二叉樹如圖所示，求它的先根遍歷、中根遍歷、后根遍歷和有二叉樹如圖所示，求它的先根遍歷、中根遍歷、后根遍歷和層次遍歷的輸出序列。層次遍歷的輸出序列。ABCIKFEDHG先根遍歷的序列：先根遍歷的序列： A B D G E H C F I K中根遍歷的序列：中根遍歷的序列： D G B H E A F K I C后根遍歷的序列：后根遍歷的序列： G D H E B K I F C A層次遍歷的序列：層次遍歷的序列： A B C D E F G H I K例：設(shè)表達(dá)式例：設(shè)表達(dá)式AB*（C+D）+E/（F+G）的二叉樹表示如圖所示。）的二叉樹表示如

44、圖所示。試寫出它的先根遍歷、中根遍歷和后根遍歷輸出序列。試寫出它的先根遍歷、中根遍歷和后根遍歷輸出序列。A*/EF+BDC-+G先根遍歷結(jié)果（即前綴表達(dá)式）：先根遍歷結(jié)果（即前綴表達(dá)式）： + A * B + C D / E + F G中根遍歷結(jié)果：中根遍歷結(jié)果： A B * C + D + E / F + G后根遍歷結(jié)果（即后綴表達(dá)式）：后根遍歷結(jié)果（即后綴表達(dá)式）： A B C D + * E F G + / +6.4 6.4 恢復(fù)二叉樹恢復(fù)二叉樹 根據(jù)已知的先根序列、中根序列、后根序列得到一棵二根據(jù)已知的先根序列、中根序列、后根序列得到一棵二叉樹稱為叉樹稱為恢復(fù)二叉樹恢復(fù)二叉樹。問題的由

45、來：問題的由來： 在數(shù)據(jù)量很大的結(jié)構(gòu)中，如在繪圖軟件中，如何存儲(chǔ)一在數(shù)據(jù)量很大的結(jié)構(gòu)中，如在繪圖軟件中，如何存儲(chǔ)一個(gè)用個(gè)用樹樹表示的圖形結(jié)構(gòu)？處理方法：表示的圖形結(jié)構(gòu)？處理方法： 對(duì)于鏈表結(jié)構(gòu)的圖形結(jié)構(gòu)：對(duì)于鏈表結(jié)構(gòu)的圖形結(jié)構(gòu)： （1 1）把每個(gè)結(jié)點(diǎn)去掉指針項(xiàng)，把每個(gè)結(jié)點(diǎn)去掉指針項(xiàng)，將結(jié)點(diǎn)的數(shù)據(jù)按將結(jié)點(diǎn)的數(shù)據(jù)按中序中序存存儲(chǔ)于數(shù)組中得到中序結(jié)點(diǎn)表。儲(chǔ)于數(shù)組中得到中序結(jié)點(diǎn)表。 （2 2）把每個(gè)結(jié)點(diǎn)去掉指針項(xiàng)，把每個(gè)結(jié)點(diǎn)去掉指針項(xiàng)，將結(jié)點(diǎn)的數(shù)據(jù)按將結(jié)點(diǎn)的數(shù)據(jù)按先序先序或或后序后序存儲(chǔ)于數(shù)組中得到序表。存儲(chǔ)于數(shù)組中得到序表。 圖形結(jié)構(gòu)調(diào)入內(nèi)存時(shí)要恢復(fù)二叉樹。有二種方法：圖形結(jié)構(gòu)調(diào)入內(nèi)存時(shí)要恢復(fù)二叉樹

46、。有二種方法： （1 1）根據(jù)根據(jù)中序中序數(shù)組、數(shù)組、先序先序數(shù)組恢復(fù)二叉樹。數(shù)組恢復(fù)二叉樹。 （2 2）根據(jù)根據(jù)中序中序數(shù)組、數(shù)組、后序后序數(shù)組數(shù)組恢復(fù)二叉樹。恢復(fù)二叉樹。1. 1. 由先根、中根恢復(fù)二叉樹由先根、中根恢復(fù)二叉樹步驟：步驟：（1 1）根據(jù)根據(jù)先根序列的先根序列的第一個(gè)元素第一個(gè)元素確定根結(jié)點(diǎn)確定根結(jié)點(diǎn)； 在在中根序列中根序列中找到該中找到該根結(jié)點(diǎn)根結(jié)點(diǎn)， 確定該根結(jié)點(diǎn)的確定該根結(jié)點(diǎn)的左、右左、右 子樹的中根序列子樹的中根序列； 再在先根序列中確定再在先根序列中確定此左、右子樹的先根序列此左、右子樹的先根序列；（2 2）根據(jù)根據(jù)左、右子樹的先根序列左、右子樹的先根序列分別找出左

47、子樹和右子樹分別找出左子樹和右子樹 的的根結(jié)點(diǎn)根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去；，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去；（3 3）再對(duì)左再對(duì)左、右子樹按此方法找出根結(jié)點(diǎn)和左、右子樹；右子樹按此方法找出根結(jié)點(diǎn)和左、右子樹； 如此遞歸下去，當(dāng)取盡先根序列中的結(jié)點(diǎn)時(shí)，便恢復(fù)了如此遞歸下去，當(dāng)取盡先根序列中的結(jié)點(diǎn)時(shí)，便恢復(fù)了一棵二叉樹。一棵二叉樹。例：由下列先根序列和中根序列恢復(fù)二叉樹。例：由下列先根序列和中根序列恢復(fù)二叉樹。 先根序列：先根序列：A C B R S E D F M L KA C B R S E D F M L K 中根序列：中根序列：R B S C E A F D L K

48、 MR B S C E A F D L K M例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K M前序：前序： A A C B R S E D F M L KC B R S E D F M L K中序：中序： R B S C ER B S C E A A F D L K MF D L K MA左子樹左子樹右子樹右子樹左子樹左子樹右子樹右子樹例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：

49、中序：R B S C E A F D L K MR B S C E A F D L K M前序：前序： A A C C B R S E D F M L KB R S E D F M L K中序：中序： R B SR B S C E A F D L K MC E A F D L K MA左子樹左子樹右子樹右子樹左子樹左子樹右子樹右子樹CD例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K M前序：前序： A C B R S E D F M L KA C

50、 B R S E D F M L K中序：中序： R B S C E A F D L K MR B S C E A F D L K MA左左子子樹樹左左子子樹樹右右子子樹樹右右子子樹樹CD左左子子樹樹右右子子樹樹左左子子樹樹右右子子樹樹例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K MA左左子子樹樹左左子子樹樹右右子子樹樹右右子子樹樹CD左左子子樹樹右右子子樹樹左左子子樹樹右右子子樹樹BEFM前序：前序： A C B R S E D F M L

51、KA C B R S E D F M L K中序：中序： R B S C E A F D L K MR B S C E A F D L K M例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K MA左左子子樹樹左左子子樹樹右右子子樹樹CDBEFM左左子子樹樹右右子子樹樹左左子子樹樹前序：前序： A C B R S E D F M L KA C B R S E D F M L K中序：中序： R B S C E A F D L K MR B S C E

52、 A F D L K M例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K MA左左子子樹樹左左子子樹樹右右子子樹樹CDBEFMRS左左子子樹樹右右子子樹樹左左子子樹樹LK前序：前序： A A C C B R S E B R S E D D F M L F M L K K中序：中序： R B S C E A F D L K MR B S C E A F D L K M2.2.由后根、中根恢復(fù)二叉樹由后根、中根恢復(fù)二叉樹步驟：步驟：（1 1）根據(jù)根據(jù)后

53、根序列的后根序列的最后一個(gè)元素最后一個(gè)元素確定根結(jié)點(diǎn)確定根結(jié)點(diǎn)； 在在中根序列中根序列中找到該中找到該根結(jié)點(diǎn)根結(jié)點(diǎn)， 確定該根結(jié)點(diǎn)的確定該根結(jié)點(diǎn)的左、右左、右 子樹的中根序列子樹的中根序列； 再在后根序列中確定再在后根序列中確定此左、右子樹的后根序列此左、右子樹的后根序列；（2 2）根據(jù)根據(jù)左、右子樹的后根序列左、右子樹的后根序列分別找出左子樹和右子樹分別找出左子樹和右子樹 的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去；的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去；（3 3）再對(duì)左再對(duì)左、右子樹按此方法找出根結(jié)點(diǎn)和左、右子樹；右子樹按此方法找出根結(jié)點(diǎn)和左、右子樹； 如此遞歸下去，當(dāng)取盡后根

54、序列中的結(jié)點(diǎn)時(shí)，便恢復(fù)了如此遞歸下去，當(dāng)取盡后根序列中的結(jié)點(diǎn)時(shí)，便恢復(fù)了一棵二叉樹。一棵二叉樹。例：由下列中根序列和后根序列恢復(fù)二叉樹。例：由下列中根序列和后根序列恢復(fù)二叉樹。 后根序列：后根序列：C E D B H G J I F AC E D B H G J I F A 中根序列：中根序列：C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IA左子樹左子樹右子樹右子樹左子樹左子樹右

55、子樹右子樹后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IA左子樹左子樹右子樹右子樹左子樹左子樹右子樹右子樹BF后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H

56、 F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IABF左左子子樹樹左左子子樹樹右右子子樹樹右右子子樹樹左左子子樹樹右右子子樹樹左左子子樹樹右右子子樹樹后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B

57、 E D A G H F J IC B E D A G H F J IABF左左子子樹樹左左子子樹樹右右子子樹樹右右子子樹樹左左子子樹樹右右子子樹樹左左子子樹樹右右子子樹樹CDGI后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IABF左左子子樹樹左左子子樹樹右右子子樹樹CDGIE

58、HJ后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I6.5 6.5 線索二叉樹線索二叉樹 對(duì)二叉樹的遍歷可得到三種序列：先序、中序、后序序列。對(duì)二叉樹的遍歷可得到三種序列：先序、中序、后序序列。均為線性序列。結(jié)點(diǎn)至多有一個(gè)直接前驅(qū)和直接后繼。均為線性序列。結(jié)點(diǎn)至多有一個(gè)直接前驅(qū)和直接后繼。 在二叉鏈表中找孩子結(jié)點(diǎn)容易，但找這樣的直接前驅(qū)和直接后在二叉鏈表中找孩子結(jié)點(diǎn)容易，但找這樣的直接前驅(qū)和直接后繼不行。繼不行。 利用二叉鏈表中的空指針域，存儲(chǔ)直接前驅(qū)和直接后繼的

59、指針利用二叉鏈表中的空指針域，存儲(chǔ)直接前驅(qū)和直接后繼的指針（為區(qū)別起見此時(shí)指針稱為線索）。（為區(qū)別起見此時(shí)指針稱為線索）。 帶有線索的二叉樹稱為帶有線索的二叉樹稱為線索二叉樹線索二叉樹。 對(duì)二叉樹以某種次序遍歷改變空指針域?yàn)榫€索，使其變?yōu)榫€索對(duì)二叉樹以某種次序遍歷改變空指針域?yàn)榫€索，使其變?yōu)榫€索二叉樹的過程稱為二叉樹的過程稱為線索化線索化。1. 線索二叉樹線索二叉樹 A B A 兩個(gè)結(jié)點(diǎn)的二叉鏈表兩個(gè)結(jié)點(diǎn)的二叉鏈表 單結(jié)點(diǎn)的二叉鏈表圖單結(jié)點(diǎn)的二叉鏈表圖 在二叉鏈表存儲(chǔ)的二叉樹中：在二叉鏈表存儲(chǔ)的二叉樹中： 單個(gè)結(jié)點(diǎn)的二叉樹有單個(gè)結(jié)點(diǎn)的二叉樹有 2 個(gè)空指針域，如圖所示。個(gè)空指針域，如圖所示。

60、兩個(gè)結(jié)點(diǎn)的二叉樹有兩個(gè)結(jié)點(diǎn)的二叉樹有 3 個(gè)空指針域，如圖所示。個(gè)空指針域，如圖所示?？梢宰C明：可以證明： 一個(gè)具有一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹，若采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，個(gè)結(jié)點(diǎn)的二叉樹，若采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，在總共在總共2n個(gè)指針域中，只有個(gè)指針域中，只有n-1個(gè)指針域用來存儲(chǔ)結(jié)點(diǎn)子樹的個(gè)指針域用來存儲(chǔ)結(jié)點(diǎn)子樹的地址，另外地址，另外n+1個(gè)都是空指針域。個(gè)都是空指針域。證明：度為證明：度為 0 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n0 每個(gè)結(jié)點(diǎn)有每個(gè)結(jié)點(diǎn)有 2 個(gè)空鏈域。個(gè)空鏈域。 度為度為 1 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n1 每個(gè)結(jié)點(diǎn)有每個(gè)結(jié)點(diǎn)有 1 個(gè)空鏈域。個(gè)空鏈域。 度為度為 2 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n2 每個(gè)結(jié)點(diǎn)沒有空鏈域。每個(gè)結(jié)點(diǎn)沒有空鏈域。 所以空鏈域數(shù)所以空鏈域數(shù)=2n0+ n1 把性質(zhì)