數(shù)據(jù)結(jié)構(gòu)第6章(1)

1、數(shù) 據(jù) 結(jié) 構(gòu) 第第6 6章章 樹和二叉樹樹和二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作目 標(biāo)理解樹、二叉樹的定義、相關(guān)術(shù)語；理解樹、二叉樹的定義、相關(guān)術(shù)語；掌握二叉樹的二叉鏈表存儲(chǔ)方式、二叉樹性質(zhì)；掌握二叉樹的二叉鏈表存儲(chǔ)方式、二叉樹性質(zhì)；掌握二叉樹的四種遍歷方式及遍歷的實(shí)現(xiàn)算法；掌握二叉樹的四種遍歷方式及遍歷的實(shí)現(xiàn)算法；理解二叉樹的線索化方法；理解二叉樹的線索化方法；靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題 理解樹、森林和二叉樹間的轉(zhuǎn)換理解樹、森林和二叉樹間的轉(zhuǎn)換理解樹、森林的遍歷理解樹、森林的遍歷北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作本章內(nèi)容本章內(nèi)容6.1

2、樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.2 二叉樹二叉樹6.3 二叉樹的遍歷和線索二叉樹二叉樹的遍歷和線索二叉樹6.4 樹和森林樹和森林6.5 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.2 二叉樹 6.2.1 二叉樹的定義 6.2.2 二叉樹的性質(zhì) 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作1 1二叉樹二叉樹 二叉樹（二叉樹（Binary TreeBinary Tree）是個(gè)有限元素的集合）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為，該集合或者為空、或者由一個(gè)稱為根根(root)(root)的的元素及兩個(gè)互不相交的、被分別稱為元素及兩個(gè)互不相交的

3、、被分別稱為左子樹左子樹和和右右子樹子樹的二叉樹組成。的二叉樹組成。 當(dāng)集合為空時(shí)，稱該二叉樹為當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹空二叉樹。 在二叉樹中，元素稱作在二叉樹中，元素稱作結(jié)點(diǎn)結(jié)點(diǎn)。 二叉樹是二叉樹是有序樹有序樹。 二叉樹有二叉樹有五種五種形態(tài)。形態(tài)。6.2.1 二叉樹的基本概念北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作 二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：6.2.1 二叉樹的基本概念北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作2 2二叉樹的相關(guān)概念二叉樹的相關(guān)概念 結(jié)點(diǎn)的度結(jié)點(diǎn)的度；葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)；分支結(jié)點(diǎn)分支結(jié)點(diǎn)； 左孩子、右孩子、雙親、兄弟左孩子、右孩子、雙親、兄弟； 路徑、路徑長度路徑、路徑

4、長度； 祖先、子孫祖先、子孫； 結(jié)點(diǎn)的層數(shù)結(jié)點(diǎn)的層數(shù)；樹的深度樹的深度；樹的度樹的度； 滿二叉樹；完全二叉樹滿二叉樹；完全二叉樹 6.2.1 二叉樹的基本概念北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.2 二叉樹的定義與性質(zhì) 6.2.1 二叉樹的基本概念 6.2.2 二叉樹的性質(zhì) 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.2.2 二叉樹的主要性質(zhì) 性質(zhì)性質(zhì)1 1 一棵非空二叉樹的第一棵非空二叉樹的第i層上最多有層上最多有2i-1個(gè)個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)（i1）。）。 性質(zhì)性質(zhì)2 2 一棵深度為一棵深度為k的二叉樹中，最多具有的二叉樹中，最多具有2k1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 證明 設(shè)第i層的結(jié)點(diǎn)數(shù)為x

5、i（1ik），深度為k的二叉樹的結(jié)點(diǎn)數(shù)為M，xi最多為2i-1，則有：北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作 性質(zhì)性質(zhì)3 3 對(duì)于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)對(duì)于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為數(shù)為n n0，度數(shù)為，度數(shù)為2 2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n n2，則有，則有:n:n0n n21 1。證明：證明：結(jié)點(diǎn)總數(shù)結(jié)點(diǎn)總數(shù)n nn n0 0n n1 1n n2 2 （6-16-1） 在二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)只有唯一在二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)只有唯一的一個(gè)前驅(qū)。則有：的一個(gè)前驅(qū)。則有：分支數(shù)分支數(shù)n n1 1 （6-26-2） 這些分支是由度為這些分支是由度為1 1和度為和度為2 2的結(jié)

6、點(diǎn)發(fā)出的，所的結(jié)點(diǎn)發(fā)出的，所以：以：分支數(shù)分支數(shù)n n1 12n2n2 2 （6-36-3） 綜合上三式可得：綜合上三式可得：n n0 0n n2 21 16.2.2 二叉樹的主要性質(zhì)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作性質(zhì)性質(zhì)4 4 具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為為 log2n +1。 證明證明：當(dāng)一棵完全二叉樹的深度為：當(dāng)一棵完全二叉樹的深度為k k、結(jié)點(diǎn)個(gè)、結(jié)點(diǎn)個(gè)數(shù)為數(shù)為n n時(shí)，滿足時(shí)，滿足2 2k k1 1n2n2k k。 對(duì)不等式取對(duì)數(shù)，有對(duì)不等式取對(duì)數(shù)，有k k1log1log2 2nkn1i1，則雙親結(jié)點(diǎn)的序號(hào)為，則雙親結(jié)點(diǎn)的序號(hào)為i/2i/2；如果；

7、如果i i1 1，則，則i i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。 如果如果2in2in，則左孩子結(jié)點(diǎn)的序號(hào)為，則左孩子結(jié)點(diǎn)的序號(hào)為2i2i；如果；如果2in2in，則無左孩子；如果，則無左孩子；如果2i2i1n1n，則右孩子結(jié)點(diǎn)，則右孩子結(jié)點(diǎn)的序號(hào)為的序號(hào)為2i2i1 1；如果；如果2i2i1n1n，則無右孩子。，則無右孩子。 注意：若對(duì)二叉樹的根結(jié)點(diǎn)從注意：若對(duì)二叉樹的根結(jié)點(diǎn)從0 0開始編號(hào)，都會(huì)發(fā)開始編號(hào)，都會(huì)發(fā)生變化。生變化。6.2.2 二叉樹的主要性質(zhì)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作選擇題選擇題1 1、按二叉樹的定義，具有、按二叉樹的定義，具有3 3個(gè)結(jié)點(diǎn)的二叉樹有（個(gè)結(jié)點(diǎn)的二

8、叉樹有（ ）種。種。 A A、3 B3 B、4 C4 C、5 D5 D、6 62 2、深度為、深度為5 5的二叉樹至多有（的二叉樹至多有（ ）個(gè)結(jié)點(diǎn)。）個(gè)結(jié)點(diǎn)。 A A、16 B16 B、31 C31 C、32 D32 D、10103 3、對(duì)一個(gè)滿二叉樹，、對(duì)一個(gè)滿二叉樹，m m個(gè)樹葉，個(gè)樹葉，n n個(gè)結(jié)點(diǎn)，深度為個(gè)結(jié)點(diǎn)，深度為h h，則（則（ ）。）。 A A、n=h+mn=h+m B B、h+mh+m=2n C=2n C、m=h-1 Dm=h-1 D、n=2n=2h h-1-1答案：答案：1 1（C C） 2 2（B B） 3 3（D D）6.2.2 二叉樹的主要性質(zhì)北華航天工業(yè)學(xué)院計(jì)算機(jī)

9、系 制作選擇題選擇題4 4、設(shè)高度為、設(shè)高度為h h的二叉樹上只有度為和度為的二叉樹上只有度為和度為2 2的結(jié)點(diǎn)，的結(jié)點(diǎn)，則此類二叉樹中包含的結(jié)點(diǎn)數(shù)至少為（則此類二叉樹中包含的結(jié)點(diǎn)數(shù)至少為（ ）。）。 A A、2h B2h B、2h-1 C2h-1 C、2h+1 D2h+1 D、h+1h+15 5、對(duì)于一棵深度為、對(duì)于一棵深度為4 4的三叉樹，最多具有（的三叉樹，最多具有（ ）個(gè)結(jié)）個(gè)結(jié)點(diǎn)。點(diǎn)。 A A、30 B30 B、36 C36 C、40 D40 D、5454答案：答案：1 1（B B） 2 2（C C） 6.2.2 二叉樹的主要性質(zhì)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作填空題填空題1 1、深度

10、為、深度為k k的完全二叉樹至少有（的完全二叉樹至少有（ ）個(gè)結(jié)點(diǎn)，至多）個(gè)結(jié)點(diǎn)，至多有（有（ ）個(gè)結(jié)點(diǎn)，若自上而下，從左到右次序給結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)，若自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從編號(hào)（從1 1開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是（ ）。）。2 2、一棵有、一棵有n n（n0n0）個(gè)結(jié)點(diǎn)的滿二叉樹共有（）個(gè)結(jié)點(diǎn)的滿二叉樹共有（ ）個(gè)）個(gè)葉子結(jié)點(diǎn)和（葉子結(jié)點(diǎn)和（ ）個(gè)非葉子結(jié)點(diǎn)。）個(gè)非葉子結(jié)點(diǎn)。答案：答案：1(21(2k-1k-1, 2, 2k k-1,2-1,2k-1k-1) 2(n/2) 2(n/2 , n/2+1, n/2+1 ) ) 6.2.2 二

11、叉樹的主要性質(zhì)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.2 二叉樹 6.2.1 二叉樹的定義 6.2.2 二叉樹的性質(zhì) 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)1順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)實(shí)現(xiàn)：順序存儲(chǔ)實(shí)現(xiàn)： 用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)。 關(guān)系依據(jù)二叉樹的性質(zhì)性質(zhì)5 5存儲(chǔ)。利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置及結(jié)點(diǎn)間的關(guān)系。完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適。完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適。采用順序存儲(chǔ)方式的最壞情況是單分支樹。采用順序存儲(chǔ)方式的最壞情況是單分支樹。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作完全二叉樹的順序存

12、儲(chǔ)示意：完全二叉樹的順序存儲(chǔ)示意：6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作一般二叉樹的順序存儲(chǔ)示意一般二叉樹的順序存儲(chǔ)示意：6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作 一棵深度為一棵深度為k k的右單支樹，需分配的右單支樹，需分配2 2k k1 1個(gè)存儲(chǔ)單元。個(gè)存儲(chǔ)單元。6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1 1）二叉鏈表存儲(chǔ)）二叉鏈表存儲(chǔ) 鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，結(jié)點(diǎn)的存儲(chǔ)結(jié)鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)為：構(gòu)為： 其中，其中，datadata域存放結(jié)點(diǎn)信息；域存放結(jié)點(diǎn)信息；lchildlch

13、ild 與與rchildrchild分別存放指向左孩子和右孩子的指針。分別存放指向左孩子和右孩子的指針。6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作 二叉樹的二叉鏈表示（鏈表也可以帶頭結(jié)點(diǎn)）。二叉樹的二叉鏈表示（鏈表也可以帶頭結(jié)點(diǎn)）。6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作（2 2）三叉鏈表存儲(chǔ)）三叉鏈表存儲(chǔ) 每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為： 其中，其中，datadata、lchildlchild以及以及rchildrchild三個(gè)域的意義三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；同二叉鏈表結(jié)構(gòu)； parentparent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親

14、結(jié)點(diǎn)的指針。域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作 二叉樹的三叉鏈表示。二叉樹的三叉鏈表示。6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作 二叉鏈表是最常用的二叉樹存儲(chǔ)方式。二叉鏈表是最常用的二叉樹存儲(chǔ)方式。 二叉鏈表存儲(chǔ)表示二叉鏈表存儲(chǔ)表示 typedef struct Node ElemType data; struct Node *lchild;*rchild; BiTNode,*BiTree; BiTree bt； /btbt被定義為根指針被定義為根指針6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.2.3 二

15、叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的基本操作二叉樹的基本操作（1 1）創(chuàng)建操作）創(chuàng)建操作（2 2）遍歷二叉樹）遍歷二叉樹 先序遍歷、中序遍歷先序遍歷、中序遍歷 后序遍歷、按層遍歷后序遍歷、按層遍歷北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作小 結(jié)理解樹、二叉樹定義及相關(guān)術(shù)語理解樹、二叉樹定義及相關(guān)術(shù)語掌握二叉樹的性質(zhì)，并用性質(zhì)解題掌握二叉樹的性質(zhì)，并用性質(zhì)解題掌握二叉鏈表存儲(chǔ)形式掌握二叉鏈表存儲(chǔ)形式北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作本章內(nèi)容本章內(nèi)容6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.2 二叉樹二叉樹6.3 二叉樹的遍歷和線索二叉樹二叉樹的遍歷和線索二叉樹6.4 樹和森林樹和森林6.5 哈夫曼樹及其應(yīng)用哈夫曼樹及其

16、應(yīng)用北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3 二叉樹的遍歷線索二叉樹二叉樹的遍歷線索二叉樹 6.3.1 6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式 6.3.2 6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法 6.3.3 6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 6.3.4 6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法 6.3.5 6.3.5 線索二叉樹線索二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式 二叉樹的遍歷二叉樹的遍歷：指按照某種順序訪問二：指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)

17、點(diǎn)被訪問一次且僅被訪問一次。且僅被訪問一次。 遍歷是二叉樹中遍歷是二叉樹中常用常用到的一種操作。到的一種操作。 通過一次完整的遍歷，可使二叉樹中結(jié)通過一次完整的遍歷，可使二叉樹中結(jié)點(diǎn)信息由點(diǎn)信息由非線性排列變?yōu)槟撤N意義上的線性非線性排列變?yōu)槟撤N意義上的線性序列序列。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式二叉樹的遍歷方式有二叉樹的遍歷方式有四種四種： 先序、中序、后序和層次遍歷先序、中序、后序和層次遍歷先序遍歷（先序遍歷（DLRDLR）定義定義： 若二叉樹為空，遍歷結(jié)束。否則，若二叉樹為空，遍歷結(jié)束。否則，訪問訪問根結(jié)點(diǎn)根結(jié)點(diǎn)；先序遍歷根結(jié)點(diǎn)的先序遍歷根結(jié)點(diǎn)的

18、左子樹左子樹；先序遍歷根結(jié)點(diǎn)的先序遍歷根結(jié)點(diǎn)的右子樹右子樹。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式二叉樹的遍歷方式有二叉樹的遍歷方式有四種四種： 先序、中序、后序和層次遍歷先序、中序、后序和層次遍歷中序遍歷（中序遍歷（LDRLDR）定義定義： 若二叉樹為空，遍歷結(jié)束。否則，若二叉樹為空，遍歷結(jié)束。否則，中序遍歷根結(jié)點(diǎn)的中序遍歷根結(jié)點(diǎn)的左子樹左子樹；訪問訪問根結(jié)點(diǎn)根結(jié)點(diǎn)；中序遍歷根結(jié)點(diǎn)的中序遍歷根結(jié)點(diǎn)的右子樹右子樹。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式二叉樹的遍歷方式有二叉樹的遍歷方式有四種四種： 先序、中序、后序和層次遍

19、歷先序、中序、后序和層次遍歷后序遍歷（后序遍歷（LRDLRD）定義定義： 若二叉樹為空，遍歷結(jié)束。否則，若二叉樹為空，遍歷結(jié)束。否則，后序遍歷根結(jié)點(diǎn)的后序遍歷根結(jié)點(diǎn)的左子樹左子樹；后序遍歷根結(jié)點(diǎn)的后序遍歷根結(jié)點(diǎn)的右子樹右子樹。訪問訪問根結(jié)點(diǎn)根結(jié)點(diǎn)；北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式二叉樹的遍歷方式有二叉樹的遍歷方式有四種四種： 先序、中序、后序和層次遍歷先序、中序、后序和層次遍歷層次遍歷層次遍歷定義定義： 若二叉樹為空，遍歷結(jié)束。否則，從二若二叉樹為空，遍歷結(jié)束。否則，從二叉樹的叉樹的第一層第一層（根結(jié)點(diǎn)）開始，（根結(jié)點(diǎn)）開始，從上至下從上至下逐逐層遍歷

20、，同一層，則按層遍歷，同一層，則按從左到右從左到右的順序逐個(gè)的順序逐個(gè)訪問結(jié)點(diǎn)。訪問結(jié)點(diǎn)。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式練習(xí)練習(xí)1 1： 給 出 下 面給 出 下 面指定二叉樹的指定二叉樹的四種遍歷方式四種遍歷方式下的結(jié)點(diǎn)序列。下的結(jié)點(diǎn)序列。 A B D E I K C G N F 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式練習(xí)練習(xí)2 2： 根據(jù)給定的遍歷結(jié)點(diǎn)序列恢復(fù)二叉樹。根據(jù)給定的遍歷結(jié)點(diǎn)序列恢復(fù)二叉樹。 LDRLDR：DCBGEAHFIJK DLR DLR：ABCDEGFHJIK 哪些遍歷組合可哪些遍歷組合可以唯

21、一確定一棵以唯一確定一棵二叉樹？二叉樹？北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式結(jié)論結(jié)論 DLRDLR，LDRLDR可以確定一棵二叉樹；可以確定一棵二叉樹； LDRLDR，LRDLRD可以確定一棵二叉樹；可以確定一棵二叉樹； LDRLDR，層次遍歷可以確定一棵二叉樹，層次遍歷可以確定一棵二叉樹 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式練習(xí)練習(xí)3 3： 根據(jù)給定的遍歷結(jié)點(diǎn)序列恢復(fù)二叉樹。根據(jù)給定的遍歷結(jié)點(diǎn)序列恢復(fù)二叉樹。 LDRLDR： B C A E D G H F I LRD LRD： C B E H G I F D A北華

22、航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3 二叉樹的遍歷二叉樹的遍歷 6.3.1 6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式 6.3.2 6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法 6.3.3 6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 6.3.4 6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法 6.3.5 6.3.5 線索二叉樹線索二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法先序遍歷遞歸算法：先序遍歷遞歸算法： void PreOrder（BiTree bt） if (bt=NULL) return; Visite（bt-da

23、ta）; PreOrder（bt-lchild）; PreOrder（bt-rchild）; 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法中序遍歷遞歸算法：中序遍歷遞歸算法： void InOrder（BiTree bt） if (bt=NULL) return; InOrder（bt-lchild）; Visite（bt-data）; InOrder（bt-rchild）; 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法后序遍歷遞歸算法：后序遍歷遞歸算法： void PostOrder（BiTree bt） if (b

24、t=NULL) return; PostOrder（bt-lchild）; PostOrder（bt-rchild）; Visite（bt-data）; 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法 根據(jù)根據(jù)二叉樹的遞歸定義二叉樹的遞歸定義，很容易寫出二叉，很容易寫出二叉樹先序、中序和后序遍歷的遞歸算法。但并樹先序、中序和后序遍歷的遞歸算法。但并非所有非所有程序設(shè)計(jì)語言程序設(shè)計(jì)語言都允許遞歸；另一方面，都允許遞歸；另一方面，遞歸程序雖然簡潔，但遞歸程序雖然簡潔，但可讀性不好，執(zhí)行效可讀性不好，執(zhí)行效率也不高率也不高。 因此，就存在如何把一個(gè)遞歸算法因此，就

25、存在如何把一個(gè)遞歸算法轉(zhuǎn)化為轉(zhuǎn)化為非遞歸算法非遞歸算法的問題。的問題。分析二叉樹的先序、中序和后序遍歷的遞分析二叉樹的先序、中序和后序遍歷的遞歸算法的執(zhí)行過程。歸算法的執(zhí)行過程。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3 二叉樹的遍歷二叉樹的遍歷 6.3.1 6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式 6.3.2 6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法 6.3.3 6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 6.3.4 6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法 6.3.5 6.3.5 線索二叉樹線索二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.3 二叉樹遍歷的

26、非遞歸算法二叉樹遍歷的非遞歸算法 遞歸算法的執(zhí)行過程：遞歸算法的執(zhí)行過程： 從根結(jié)點(diǎn)開始從根結(jié)點(diǎn)開始沿左子樹深入沿左子樹深入下去，當(dāng)深下去，當(dāng)深入到最左端，無法再深入下去時(shí)，則返回，入到最左端，無法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回再進(jìn)行如此的深入和返回，直到最后從根結(jié)，直到最后從根結(jié)點(diǎn)的右子樹返回到點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止根結(jié)點(diǎn)為止。 先序遍歷先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問，是在深入時(shí)遇到結(jié)點(diǎn)就訪問，中序遍歷中序遍歷是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問，是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問，后序遍歷后序遍歷是在從右子

27、樹返回時(shí)遇到結(jié)點(diǎn)訪問。是在從右子樹返回時(shí)遇到結(jié)點(diǎn)訪問。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 遞歸算法的執(zhí)行過程：遞歸算法的執(zhí)行過程： 在這一過程中，返回結(jié)點(diǎn)的順序與深入結(jié)點(diǎn)在這一過程中，返回結(jié)點(diǎn)的順序與深入結(jié)點(diǎn)的順序相反，即的順序相反，即后深入先返回后深入先返回，可以用棧來幫助實(shí)，可以用棧來幫助實(shí)現(xiàn)這一遍歷路線。現(xiàn)這一遍歷路線。 先序遍歷過程先序遍歷過程：先訪問結(jié)點(diǎn)，將該結(jié)點(diǎn)入棧，：先訪問結(jié)點(diǎn)，將該結(jié)點(diǎn)入棧，然后沿左子樹深入，深入一個(gè)結(jié)點(diǎn)同樣重復(fù)剛才過然后沿左子樹深入，深入一個(gè)結(jié)點(diǎn)同樣重復(fù)剛才過程；當(dāng)沿左分支深入不下去時(shí)，則返回，即從棧中程；當(dāng)

28、沿左分支深入不下去時(shí)，則返回，即從棧中彈出一個(gè)結(jié)點(diǎn)，然后從該結(jié)點(diǎn)的右子樹開始繼續(xù)深彈出一個(gè)結(jié)點(diǎn)，然后從該結(jié)點(diǎn)的右子樹開始繼續(xù)深入；仍為入；仍為訪問、入棧、繼續(xù)深入訪問、入棧、繼續(xù)深入，深入不下去時(shí)再，深入不下去時(shí)再返回，直到棧中無結(jié)點(diǎn)為止。返回，直到棧中無結(jié)點(diǎn)為止。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 先序遍歷的非遞歸算法：先序遍歷的非遞歸算法：說明：說明：二叉樹以二叉鏈表形式存放；二叉樹以二叉鏈表形式存放； 定義一個(gè)順序棧定義一個(gè)順序棧SeqStack s; void NRPreOrder（BiTree bt） SeqStack s; Ini

29、t_SeqStack( s ); if (bt=NULL) return; BiTNode *p=bt;北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.3 二叉樹遍歷的非遞歸算法 while( !(p=NULL & Empty_SeqStack(s) while(p!=NULL) coutdata; /*訪問結(jié)點(diǎn)的數(shù)據(jù)域訪問結(jié)點(diǎn)的數(shù)據(jù)域*/ Push_SeqStack(s,p); p=p-lchild； /*往左深入往左深入*/ /*返回返回*/ if (!Empty_SeqStack(s) Pop_SeqStack(s,p); p=p-rchild; /*訪問右子樹訪問右子樹*/ 北華航天工業(yè)

30、學(xué)院計(jì)算機(jī)系 制作 對(duì)于圖所示的二叉樹，用該算法進(jìn)行遍歷過程中，棧和當(dāng)前對(duì)于圖所示的二叉樹，用該算法進(jìn)行遍歷過程中，棧和當(dāng)前指針指針p p的變化情況以及樹中各結(jié)點(diǎn)的訪問次序如下表所示。的變化情況以及樹中各結(jié)點(diǎn)的訪問次序如下表所示。6.3.3 二叉樹遍歷的非遞歸實(shí)現(xiàn)二叉樹遍歷的非遞歸實(shí)現(xiàn)北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法中序遍歷的非遞歸算法：中序遍歷的非遞歸算法： 與先序遍歷過程比較，中序的區(qū)別就是與先序遍歷過程比較，中序的區(qū)別就是每次每次返回時(shí)訪問結(jié)點(diǎn)返回時(shí)訪問結(jié)點(diǎn)。后序遍歷的非遞歸算法：后序遍歷的非遞歸算法： 與先序遍歷過程比較，與先序遍歷

31、過程比較，結(jié)點(diǎn)在第二次出結(jié)點(diǎn)在第二次出棧時(shí)訪問棧時(shí)訪問。結(jié)點(diǎn)第一次出棧只表示訪問完該。結(jié)點(diǎn)第一次出棧只表示訪問完該結(jié)點(diǎn)的左子樹，還需再次入棧，第二次出棧結(jié)點(diǎn)的左子樹，還需再次入棧，第二次出棧才表示該結(jié)點(diǎn)的右子樹也訪問完畢，該遍歷才表示該結(jié)點(diǎn)的右子樹也訪問完畢，該遍歷該結(jié)點(diǎn)。該結(jié)點(diǎn)。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法中序遍歷和后序遍歷的非遞歸算法中序遍歷和后序遍歷的非遞歸算法自己編寫。自己編寫。不用棧實(shí)現(xiàn)非遞歸算法的方法不用棧實(shí)現(xiàn)非遞歸算法的方法 三叉鏈表；三叉鏈表； 利用線索二叉樹利用線索二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3 二叉樹的遍

32、歷二叉樹的遍歷 6.3.1 6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式 6.3.2 6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法 6.3.3 6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 6.3.4 6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法 6.3.5 6.3.5 線索二叉樹線索二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法層次遍歷實(shí)現(xiàn)算法層次遍歷實(shí)現(xiàn)算法 分析層次遍歷過程分析層次遍歷過程 在進(jìn)行層次遍歷時(shí)，對(duì)一層結(jié)點(diǎn)訪問完在進(jìn)行層次遍歷時(shí)，對(duì)一層結(jié)點(diǎn)訪問完后，再按照它們的訪問次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左后，再按照它們的訪問次序

33、對(duì)各個(gè)結(jié)點(diǎn)的左孩子和右孩子順序訪問，這樣一層一層進(jìn)行，孩子和右孩子順序訪問，這樣一層一層進(jìn)行，先遇到的結(jié)點(diǎn)先訪問。先遇到的結(jié)點(diǎn)先訪問。 符合隊(duì)列特征符合隊(duì)列特征北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法層次遍歷實(shí)現(xiàn)算法層次遍歷實(shí)現(xiàn)算法 設(shè)一個(gè)隊(duì)列，遍歷從二叉樹的根結(jié)點(diǎn)開始，設(shè)一個(gè)隊(duì)列，遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)入隊(duì)，執(zhí)行下面兩個(gè)操作：首先將根結(jié)點(diǎn)入隊(duì)，執(zhí)行下面兩個(gè)操作： 出隊(duì)一個(gè)結(jié)點(diǎn)，訪問該結(jié)點(diǎn)；出隊(duì)一個(gè)結(jié)點(diǎn)，訪問該結(jié)點(diǎn)； 若該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，若該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將其左孩子和右孩子結(jié)點(diǎn)順序入隊(duì)。則將其左孩子和右孩子結(jié)點(diǎn)順

34、序入隊(duì)。 直到隊(duì)列為空時(shí)，層次遍歷結(jié)束。直到隊(duì)列為空時(shí)，層次遍歷結(jié)束。北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法層次遍歷實(shí)現(xiàn)算法層次遍歷實(shí)現(xiàn)算法 定義隊(duì)列定義隊(duì)列LinkQueue *Q，二叉樹以二叉二叉樹以二叉鏈表形式存放。鏈表形式存放。 void LevelOrder（BiTree bt） LinkQueue *Q; Q=Init_Queue ( ); if (bt=NULL) return; In_Queue(Q,bt);北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法 BitNode *p; while( !Em

35、pty_Queue(Q) Out_Queue(Q,p); coutdata; if (p-lchild!=NULL) In_Queue(Q,p-lchild); if (p-rchild!=NULL) In_Queue(Q,p-rchild); 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3 二叉樹的遍歷二叉樹的遍歷 6.3.1 6.3.1 二叉樹的遍歷方式二叉樹的遍歷方式 6.3.2 6.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法 6.3.3 6.3.3 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 6.3.4 6.3.4 二叉樹的層次遍歷算法二叉樹的層次遍歷算法 6.3.5 6.3.5 線索二

36、叉樹線索二叉樹北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作6.3.5 6.3.5 線索二叉樹線索二叉樹1 1線索二叉樹的定義線索二叉樹的定義為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息。繼的位置信息。利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的空指針域來保利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的空指針域來保存該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)，該指針被存該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)，該指針被稱為稱為線索線索（threadthread），加了線索的二叉樹稱為），加了線索的二叉樹稱為線索二線索二叉樹叉樹。注意：注意： 北華航天工業(yè)學(xué)院計(jì)算機(jī)系 制作2 2畫線索二叉樹畫線索二叉樹l 線索樹有先序線索二叉樹、中序線索二叉樹和線索樹有先序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。后序線索二叉樹三種。l 通常用實(shí)線表示二叉樹中的指向左、右孩子結(jié)通常用實(shí)線表示二叉樹中的指向左、右孩子結(jié)點(diǎn)的指針，用虛線表示線索