第6章樹和二叉樹

i/2結(jié)點(diǎn)i的左孩子為2i結(jié)點(diǎn)i的右孩子為2i＋1

6.2二叉樹的邏輯結(jié)構(gòu)性質(zhì)5表明，在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹的基本性質(zhì)

6.在滿二叉樹中，葉結(jié)點(diǎn)的個(gè)數(shù)比分支結(jié)點(diǎn)個(gè)數(shù)多1。

7.在擴(kuò)充二叉樹中，外部結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)多1。8.對(duì)擴(kuò)充二叉樹,外部路徑長度E和內(nèi)部路徑長度I的關(guān)系：E=I+2n,n是內(nèi)部結(jié)點(diǎn)個(gè)數(shù)6.2二叉樹的邏輯結(jié)構(gòu)完全二叉樹的基本性質(zhì)

1.具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（）個(gè)度為2的結(jié)點(diǎn)，【北京航空航天大學(xué)2000一、5（2分)】A．8B．9C．10D．ll2．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）【西安交通大學(xué)1996三、2(3分)】A．250B．500C．254D．505E．以上答案都不對(duì)3.有關(guān)二叉樹下列說法正確的是（）【南京理工大學(xué)2000一、11（1.5分）】A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為24.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）【南京理工大學(xué)1999一、19（2分）】A．11B．10C．11至1025之間D．10至1024之間6.2二叉樹的邏輯結(jié)構(gòu)二叉樹的抽象數(shù)據(jù)類型定義ADTBinTreeisoperationsBinTreecreateEmptyBinTree(void)

創(chuàng)建一棵空的二叉樹。BinTreeconsBinTree(BinTreeNoderoot,BinTreeleft,BinTreeright)

返回一棵二叉樹，其根結(jié)點(diǎn)是root，左右二叉樹分別為left和right。intisNull(BinTreet)

判斷二叉樹t是否為空。

6.2二叉樹的邏輯結(jié)構(gòu)由于二叉樹的概念是遞歸定義的，二叉樹中的每個(gè)結(jié)點(diǎn)也可標(biāo)識(shí)以這個(gè)結(jié)點(diǎn)為根的二叉樹，所以二叉樹類型和二叉樹中結(jié)點(diǎn)類型在具體實(shí)現(xiàn)時(shí)常?？闯墒峭环N類型。

BinTreeNoderoot(BinTreet)

返回二叉樹t的根結(jié)點(diǎn)。若為空二叉樹，則返回一特殊值。BinTreeNodeparent(BinTreet,BinTreeNodep)

返回結(jié)點(diǎn)p的父結(jié)點(diǎn)。當(dāng)指定的結(jié)點(diǎn)為根時(shí)，返回一個(gè)特殊值。BinTreeleftChild(BinTreet,BinTreeNodep)

返回p結(jié)點(diǎn)的左子樹，當(dāng)指定結(jié)點(diǎn)沒有左子樹時(shí)，返回一個(gè)特殊值。BinTreerightChild(BinTreet,BinTreeNodep)

返回p結(jié)點(diǎn)的右子樹，當(dāng)指定結(jié)點(diǎn)沒有右子樹時(shí)，返回一個(gè)特殊值。endADTBinTree

二叉樹的抽象數(shù)據(jù)類型定義6.2二叉樹的邏輯結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系——父子關(guān)系。

如何利用數(shù)組下標(biāo)來反映結(jié)點(diǎn)之間的邏輯關(guān)系?完全二叉樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系。6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

A

B

C

D

E

F

G

H

I

J數(shù)組下標(biāo)12345678910完全二叉樹的順序存儲(chǔ)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)CDEFGHIJ以編號(hào)為下標(biāo)二叉樹的順序存儲(chǔ)ABC∧DE∧∧∧F∧∧G數(shù)組下標(biāo)123456789101112136.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEGF以編號(hào)為下標(biāo)ABCDEGF123561013按照完全二叉樹編號(hào)一棵斜樹的順序存儲(chǔ)會(huì)怎樣呢？深度為k的右斜樹，k個(gè)結(jié)點(diǎn)需分配2k－1個(gè)存儲(chǔ)單元一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結(jié)點(diǎn)，造成存儲(chǔ)空間的浪費(fèi)。6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹ABC137D15二叉鏈表基本思想：令二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)除了存放與二叉樹結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。

結(jié)點(diǎn)結(jié)構(gòu)：

LChildData

RChild其中，Data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；LChild：左指針域，存放指向左孩子的指針；RChild：右指針域，存放指向右孩子的指針。

6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)typedefstructNode{DataTypedata;strctNode*LChild;structNode*RChild;}BiTNode,*BiTree;6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)LChild

DataRChild左孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)二叉鏈表GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針。三叉鏈表6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉鏈表中，如何求某結(jié)點(diǎn)的雙親？三叉鏈表

LChildDataParentRChild在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域。結(jié)點(diǎn)結(jié)構(gòu)其中：data、lchild和rchild三個(gè)域的含義同二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針。

6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧三叉鏈表6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的遍歷操作

二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化6.3二叉樹的周游抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。

考慮二叉樹的組成：根結(jié)點(diǎn)D左子樹L右子樹R二叉樹6.3二叉樹的周游前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結(jié)點(diǎn)；②前序遍歷根結(jié)點(diǎn)的左子樹；③前序遍歷根結(jié)點(diǎn)的右子樹。二叉樹的遍歷操作

6.3二叉樹的周游ADBCDLRADLRDLR>B>>D>>CDLR前序遍歷序列：ABDC前序遍歷:6.3二叉樹的周游前序遍歷序列：ABDGCEFABCDEFG二叉樹的遍歷操作

6.3二叉樹的周游中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結(jié)點(diǎn)的左子樹；②訪問根結(jié)點(diǎn)；③中序遍歷根結(jié)點(diǎn)的右子樹。

二叉樹的遍歷操作

6.3二叉樹的周游LDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBC6.3二叉樹的周游中序遍歷序列：DGBAECFABCDEFG二叉樹的遍歷操作

6.3二叉樹的周游后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結(jié)點(diǎn)的左子樹；②后序遍歷根結(jié)點(diǎn)的右子樹。③訪問根結(jié)點(diǎn)；二叉樹的遍歷操作

6.3二叉樹的周游

LRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:BADBC6.3二叉樹的周游后序遍歷序列：GDBEFCAABCDEFG二叉樹的遍歷操作

6.3二叉樹的周游層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。

層序遍歷序列：ABCDEFGABCDEFG二叉樹的遍歷操作

6.3二叉樹的周游--/+*abcdef二叉樹遍歷操作練習(xí)前序遍歷結(jié)果：-+a*b-cd/ef中序遍歷結(jié)果：a+b*c-d-e/f后序遍歷結(jié)果：abcd-*+ef/-6.3二叉樹的周游若已知一棵二叉樹的前序（或中序，或后序，或?qū)有颍┬蛄?，能否唯一確定這棵二叉樹呢？ABC例：已知前序序列為ABC，則可能的二叉樹有5種。ABC二叉樹的遍歷操作

6.3二叉樹的周游例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹都滿足條件。ABCABC若已知一棵二叉樹的前序序列和后序序列，能否唯一確定這棵二叉樹呢？二叉樹的遍歷操作

6.3二叉樹的周游若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？

例如：已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構(gòu)造該二叉樹呢?

二叉樹的遍歷操作

6.3二叉樹的周游前序：ABCDEFG

HI中序：BCAEDGHFI前序：BC中序：BC

BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI6.3二叉樹的周游前序：FG

HI中序：GHFI前序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH6.3二叉樹的周游1.根據(jù)前序序列的第一個(gè)元素建立根結(jié)點(diǎn)；2.在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；3.在前序序列中確定左右子樹的前序序列；4.由左子樹的前序序列和中序序列建立左子樹；5.由右子樹的前序序列和中序序列建立右子樹。已知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下：

二叉樹的遍歷操作

6.3二叉樹的周游以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，討論二叉樹的遍歷算法1)先序遍歷voidPreOrder(BiTreeroot)/*先序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/{ if(root!=NULL) {Visit(root->data);/*訪問根結(jié)點(diǎn)*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}2)中序遍歷voidInOrder(BiTreeroot)/*中序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/{ if(root!=NULL) { InOrder(root->LChild);/*中序遍歷左子樹*/ Visit(root->data);/*訪問根結(jié)點(diǎn)*/ InOrder(root->RChild);/*中序遍歷右子樹*/ }}3)后序遍歷voidPostOrder(BiTreeroot)/*后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/{ if(root!=NULL) { PostOrder(root->LChild);/*后序遍歷左子樹*/ PostOrder(root->RChild);/*后序遍歷右子樹*

Visit(root->data);/*訪問根結(jié)點(diǎn)*/ }}建立二叉樹為了建立一棵二叉樹，將二叉樹中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一特定值如“.”，以標(biāo)識(shí)其為空，把這樣處理后的二叉樹稱為原二叉樹的擴(kuò)展二叉樹。

為什么如此處理?如何由一種遍歷序列生成該二叉樹？遍歷是二叉樹各種操作的基礎(chǔ)，可以在遍歷的過程中進(jìn)行各種操作，例如建立一棵二叉樹。6.3二叉樹的周游擴(kuò)展二叉樹的前序遍歷序列:AB.D..C..DBAC.DBAC....建立二叉樹6.3二叉樹的周游設(shè)二叉樹中的結(jié)點(diǎn)均為一個(gè)字符。假設(shè)擴(kuò)展二叉樹的前序遍歷序列由鍵盤輸入，root為指向根結(jié)點(diǎn)的指針，二叉鏈表的建立過程是：首先輸入根結(jié)點(diǎn)，若輸入的是一個(gè)“.”字符，則表明該二叉樹為空樹，即root=NULL；否則輸入的字符應(yīng)該賦給root->data,，之后依次遞歸建立它的左子樹和右子樹。建立二叉樹6.3二叉樹的周游建立二叉鏈表方式存儲(chǔ)的二叉樹voidCreateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreateBiTree(&((*bt)->LChild));CreateBiTree(&((*bt)->RChild));}}二叉樹算法設(shè)計(jì)練習(xí)遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法中對(duì)每個(gè)結(jié)點(diǎn)的訪問操作可以是多種形式及多個(gè)操作，根據(jù)遍歷算法的框架，適當(dāng)修改訪問操作的內(nèi)容，可以派生出很多關(guān)于二叉樹的應(yīng)用算法。voidInOrder(BiTreeroot){if(root==NULL)return;else{InOrder(root->lchild);

printf(“%c”,root->data);InOrder(root->rchild);}}二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。voidCount(BiTreeroot)//count為全局量并已初始化為0{if(root==NULL)return;else{Count(root->lchild);count++;Count(root->rchild);}}二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)。voidPreOrder(BiTreeroot){if(root==NULL)return;else{if(!root->lchild&&!root->rchild)printf(“%c”,root->data);PreOrder(root->lchild);PreOrder(root->rchild);}}6.3.2遍歷算法應(yīng)用1.輸出二叉樹中的結(jié)點(diǎn)【算法描述】voidPreOrder(BiTreeroot){ if(root!=NULL){ printf(root->data);/*輸出根結(jié)點(diǎn)*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/}}2.輸出二叉樹中的葉子結(jié)點(diǎn)voidPreOrder(BiTreeroot){ if(root!=NULL){

if(root->LChild==NULL&&root->RChild==NULL)printf(root->data);/*輸出葉子結(jié)點(diǎn)*/PreOrder(root->LChild);/*先序遍歷左子樹*/PreOrder(root->RChild);/*先序遍歷右子樹*/}}3.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目/*LeafCount為保存葉子結(jié)點(diǎn)數(shù)目的全局變量,調(diào)用之前初始化值為0*/voidleaf(BiTreeroot){if(root!=NULL){leaf(root->LChild);leaf(root->RChild);if(root->LChild==NULL&&root->RChild==NULL)LeafCount++;}}

方法一：intleaf(BiTreeroot){intLeafCount;if(root==NULL) LeafCount=0;elseif((root->LChild==NULL)&&(root->RChild==NULL))LeafCount=1; else/*葉子數(shù)為左右子樹的葉子數(shù)目之和*/

LeafCount=leaf(root->LChild)+leaf(root->RChild); returnLeafCount;}方法二：3.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目5.求二叉樹的高度設(shè)函數(shù)表示二叉樹bt的高度，則遞歸定義如下:

若bt為空，則高度為0

若bt非空，其高度應(yīng)為其左右子樹高度的最大值加1

左子樹右子樹bthlhrHigh=max(hl+hr)+1intPostTreeDepth(BiTreebt){inthl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild);/*求左子樹的深度*/hr=PostTreeDepth(bt->RChild);/*求右子樹的深度*/max=hl>hr?hl:hr;/*得到左、右子樹深度較大者*/return(max+1);/*返回樹的深度*/}elsereturn(0);/*如果是空樹，則返回0*/}二叉樹前序遍歷的非遞歸算法的關(guān)鍵：在前序遍歷過某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的右子樹的根指針。解決辦法：在訪問完該結(jié)點(diǎn)后，將該結(jié)點(diǎn)的指針保存在棧中，以便以后能通過它找到該結(jié)點(diǎn)的右子樹。

在前序遍歷中，設(shè)要遍歷二叉樹的根指針為root，則有兩種可能：⑴若root!=NULL，則表明？如何處理？⑵若root=NULL，則表明？如何處理？前序遍歷——非遞歸算法6.3二叉樹遍歷的非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD

A

B前序遍歷的非遞歸實(shí)現(xiàn)

ADBC6.3二叉樹遍歷的非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD

A前序遍歷的非遞歸實(shí)現(xiàn)

ADBC

D6.3二叉樹遍歷的非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD

C前序遍歷的非遞歸實(shí)現(xiàn)

ADBCC6.3二叉樹遍歷的非遞歸算法1.棧s初始化；2.循環(huán)直到root為空或棧s為空

2.1當(dāng)root不空時(shí)循環(huán)

2.1.1輸出root->data;2.1.2將指針root的值保存到棧中；

2.1.3繼續(xù)遍歷root的左子樹

2.2如果棧s不空，則

2.2.1將棧頂元素彈出至root；

2.2.2準(zhǔn)備遍歷root的右子樹；前序遍歷——非遞歸算法（偽代碼）6.3二叉樹遍歷的非遞歸算法前序遍歷——非遞歸算法

voidPreOrder(BiTreeroot){InitStack(&S);//采用順序棧p=root;

while(p!=NULL||!isEmpty(S))

{if(p!=NULL){printf(“%c”,p->data);push(&S,p);p=p->lchild;}else{pop(&S,&p);p=p->rchild;}}}6.3二叉樹遍歷的非遞歸算法中序遍歷——非遞歸算法在二叉樹的中序遍歷中，訪問結(jié)點(diǎn)的操作發(fā)生在該結(jié)點(diǎn)的左子樹遍歷完畢并準(zhǔn)備遍歷右子樹時(shí)，所以，在遍歷過程中遇到某結(jié)點(diǎn)時(shí)并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語句printf(“%c”,p->data)移到pop(&S,&p)之后即可。6.3二叉樹遍歷的非遞歸算法中序遍歷——非遞歸算法

voidPreOrder(BinTreeroot){InitStack(&S);//采用順序棧p=root;

while(p!=NULL||!isEmpty(S)){if(p!=NULL){push(&S,p);p=p->lchild;}else{pop(&S,&p);printf(“%c”,p->data);p=p->rchild;}}}6.3二叉樹遍歷的非遞歸算法后序遍歷——非遞歸算法voidPostOrder(BiTreeroot){BiTNode*p,*q;StackS;q=NULL;p=root;InitStack(&S);while(p!=NULL||!isEmpty(S)){while(p!=NULL){push(&S,p);p=p->lchild;}if(!isEmpty(S)){GetTop(&S,&p);if(p->rchild==NULL)||(p->rchild==q){printf(“%c”,p->data);q=p;pop(&s,&p);p=NULL;}elsep=p->rchild;}}}6.3二叉樹遍歷的非遞歸算法層序遍歷ABCDEFG遍歷序列：AABCBDCEFGDEFG6.3二叉樹遍歷的非遞歸算法層序遍歷隊(duì)列Q初始化；2.如果二叉樹非空，將根指針入隊(duì)；3.循環(huán)直到隊(duì)列Q為空3.1p=隊(duì)列Q的隊(duì)頭元素出隊(duì)；3.2訪問結(jié)點(diǎn)p的數(shù)據(jù)域；3.3若結(jié)點(diǎn)p存在左孩子，則將左孩子指針入隊(duì)；3.4若結(jié)點(diǎn)p存在右孩子，則將右孩子指針入隊(duì)；6.3二叉樹遍歷的非遞歸算法層序遍歷voidLeverOrder(BiTreeroot){InitQueue(&Q);//采用順序隊(duì)列if(root==NULL)return;//二叉樹為空，算法結(jié)束p=root;EnterQueue(&Q,p);//指針入隊(duì)while(!isEmptyQueue(Q))//當(dāng)隊(duì)列非空時(shí){DelQueue(&Q,&p);//出隊(duì)printf(“%c”,p->data);if(p->lchild!=NULL)EnterQueue(&Q,p->lchild);if(p->rchild!=NULL)EnterQueue(&Q,p->rchild);}}6.3二叉樹遍歷的非遞歸算法線索鏈表線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化；線索鏈表：加上線索的二叉鏈表稱為線索鏈表。6.3二叉樹的線索化如何保存二叉樹的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)

LtagLChild

dataRChildRtag0:Lchild指向該結(jié)點(diǎn)的左孩子1:Lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0:Rchild指向該結(jié)點(diǎn)的右孩子1:Rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)Ltag=Rtag=結(jié)點(diǎn)結(jié)構(gòu)線索鏈表6.3二叉樹的線索化typedefstructThrNode{DataTypedata;PThrNodelchild,rchild;intltag,rtag;}*PThrNode;線索鏈表結(jié)點(diǎn)結(jié)構(gòu)

LtagLChild

dataRChildRtag6.3二叉樹的線索化二叉樹的遍歷方式有4種，故有4種意義下的前驅(qū)和后繼，相應(yīng)的有4種線索二叉樹：⑴前序線索二叉樹⑵中序線索二叉樹⑶后序線索二叉樹⑷層序線索二叉樹線索二叉樹6.3二叉樹的線索化FABDCEG中序線索二叉樹線索二叉樹中序序列：DGBAECF6.3二叉樹的線索化分析：建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹時(shí)才能得到。建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立6.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程已經(jīng)建立起二叉鏈表6.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)p16.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre1p16.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p16.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧∧∧00000000000000中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p116.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧∧00000000000000中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p1116.3二叉樹的線索化A頭指針BCDEFG∧∧∧∧00000000000000中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p11116.3二叉樹的線索化A頭指針BCDEFG∧∧∧00000000000000中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p111116.3二叉樹的線索化A頭指針BCDEFG∧∧00000000000000中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre111111116.3二叉樹的線索化在遍歷過程中，訪問當(dāng)前結(jié)點(diǎn)root的操作為：⑴如果root的左、右指針域?yàn)榭?，則將相應(yīng)標(biāo)志置1；⑵若root的左指針域?yàn)榭眨瑒t令其指向它的前驅(qū)，這需要設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，顯然pre的初值為NULL；若pre的右指針域?yàn)榭?，則令其指向它的后繼，即當(dāng)前訪問的結(jié)點(diǎn)root;⑶令pre指向剛剛訪問過的結(jié)點(diǎn)root；中序線索鏈表的建立6.3二叉樹的線索化1.建立二叉鏈表，將每個(gè)結(jié)點(diǎn)的左右標(biāo)志置為0；2.遍歷二叉鏈表，建立線索；2.1如果二叉鏈表root為空，則空操作返回；2.2對(duì)root的左子樹建立線索；2.3對(duì)根結(jié)點(diǎn)root建立線索；

2.3.1若root沒有左孩子，則為root加上前驅(qū)線索;2.3.2若結(jié)點(diǎn)pre右標(biāo)志為1，則為pre加上后繼線索；2.3.3令pre指向剛剛訪問的結(jié)點(diǎn)root；2.4對(duì)root的右子樹建立線索。中序線索鏈表的建立

6.3二叉樹的線索化voidThread(PThrNoderoot){if(root==NULL)return;Thread(root->lchild);if(root->lchild==NULL){//對(duì)root的左指針進(jìn)行處理root->ltag=1;root->lchild=pre;//設(shè)置pre的前驅(qū)線索}if(pre!=NULL&&pre->rtag==1){pre->rchild=root;pre->rtag=1;}//設(shè)置pre的后繼線索pre=root;Thread(root->rchild);}中序線索鏈表的建立

6.3二叉樹的線索化中序線索鏈表查找后繼FABDCEG⑴如果結(jié)點(diǎn)p的右標(biāo)志為1，則表明該結(jié)點(diǎn)的右指針是線索；⑵如果結(jié)點(diǎn)p的右標(biāo)志為0，則表明該結(jié)點(diǎn)有右孩子。根據(jù)中序遍歷的操作定義，它的后繼結(jié)點(diǎn)應(yīng)該是遍歷其右子樹時(shí)第一個(gè)訪問的結(jié)點(diǎn)，即右子樹中的最左下結(jié)點(diǎn)。6.3二叉樹的線索化

PThrNodeNext(PThrNodep){if(p->ltag==1)q=p->lchild;//右標(biāo)志為1，可直接得到后繼結(jié)點(diǎn)

else{q=p->lchild;//工作指針q指向結(jié)點(diǎn)p的右孩子

while(q->rtag==0)//查找最左下結(jié)點(diǎn)

q=q->rchild;}returnq;}中序線索鏈表查找前驅(qū)6.3二叉樹的線索化

PThrNodeNext(PThrNodep){if(p->rtag==1)q=p->rchild;//右標(biāo)志為1，可直接得到后繼結(jié)點(diǎn)

else{q=p->rchild;//工作指針q指向結(jié)點(diǎn)p的右孩子

while(q->ltag==0)//查找最左下結(jié)點(diǎn)

q=q->lchild;}returnq;}中序線索鏈表查找后繼6.3二叉樹的線索化6.4樹的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)樹的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么?什么是存儲(chǔ)結(jié)構(gòu)?樹中結(jié)點(diǎn)之間的邏輯關(guān)系是什么?思考問題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子如何表示樹中結(jié)點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲(chǔ)器中的表示。雙親表示法(父指針表示法)基本思想：用一維數(shù)組來存儲(chǔ)樹的各個(gè)結(jié)點(diǎn)（一般按層序存儲(chǔ)），數(shù)組中的一個(gè)元素對(duì)應(yīng)樹中的一個(gè)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。

6.4樹的存儲(chǔ)結(jié)構(gòu)

data

parentdata：存儲(chǔ)樹中結(jié)點(diǎn)的數(shù)據(jù)信息parent：存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)structParTreeNode{

DataTypedata;//數(shù)據(jù)域intparent;//指針域，雙親在數(shù)組中的下標(biāo)};

data

parent6.4樹的存儲(chǔ)結(jié)構(gòu)樹的雙親表示法實(shí)質(zhì)上是一個(gè)靜態(tài)鏈表。雙親表示法下標(biāo)

dataparent012345678

A-1B0C0D1E1F1G2H2I

46.4樹的存儲(chǔ)結(jié)構(gòu)如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親表示法ACBHFEDGI6.4樹的存儲(chǔ)結(jié)構(gòu)雙親表示法ACBHFEDGI如何查找孩子結(jié)點(diǎn)？時(shí)間性能？下標(biāo)

dataparentfirstchild136-18-1-1-1-1012345678

A-1B0C0D1E1F1G2H2I

4下標(biāo)

dataparentrightsib-12-145-17-1-16.4樹的存儲(chǔ)結(jié)構(gòu)雙親表示法012345678

A-1B0C0D1E1F1G2H2I

4ACBHFEDGI如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。如何表示孩子？6.4樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法（子表）方案一：指針域的個(gè)數(shù)等于樹的度datachild1child2……childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；

child1~childd：指針域，指向該結(jié)點(diǎn)的孩子。

6.4樹的存儲(chǔ)結(jié)構(gòu)∧缺點(diǎn)：浪費(fèi)空間ACBHFEDGIA∧B∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。如何表示孩子？6.4樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法方案二：

指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度data

degree

child1

child2

……

childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；

degree：度域，存放該結(jié)點(diǎn)的度；

child1~childd：指針域，指向該結(jié)點(diǎn)的孩子。

6.4樹的存儲(chǔ)結(jié)構(gòu)缺點(diǎn)：結(jié)點(diǎn)結(jié)構(gòu)不一致ACBHFEDGIA2B3C2E1I0G0H0F0D0孩子鏈表表示法孩子鏈表的基本思想：把每個(gè)結(jié)點(diǎn)的孩子排列起來，看成是一個(gè)線性表，且以單鏈表存儲(chǔ)，則n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表。這n個(gè)單鏈表共有n個(gè)頭指針，這n個(gè)頭指針又組成了一個(gè)線性表，為了便于進(jìn)行查找采用順序存儲(chǔ)。最后，將存放n個(gè)頭指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來，構(gòu)成孩子鏈表的表頭數(shù)組。

6.4樹的存儲(chǔ)結(jié)構(gòu)如何表示孩子？將結(jié)點(diǎn)的所有孩子放在一起，構(gòu)成線性表。childnext孩子結(jié)點(diǎn)structCTNode{

intchild;CTNode*next;};6.4樹的存儲(chǔ)結(jié)構(gòu)structCBNode{DataTypedata;CTNode*firstchild;};孩子鏈表表示法datafirstchild表頭結(jié)點(diǎn)ACBHFEDGI012345678下標(biāo)

datafirstchild

ABCDEFG

H

I

∧∧∧∧6.4樹的存儲(chǔ)結(jié)構(gòu)如何查找孩子結(jié)點(diǎn)？時(shí)間性能？∧12∧345∧7∧68∧ACBHFEDGI012345678下標(biāo)

datafirstchild

ABCDEFG

H

I

∧∧∧∧∧6.4樹的存儲(chǔ)結(jié)構(gòu)12∧345∧7∧68∧如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親孩子表示法6.4樹的存儲(chǔ)結(jié)構(gòu)012345678

A-1B0C0D1

∧

E1F1

∧

G

2

∧H

2

∧I

4

∧dataparentfirstchild12∧345∧7∧68∧ACBHFEDGI孩子兄弟表示法(長子兄弟)6.4樹的存儲(chǔ)結(jié)構(gòu)ACBHFEDGI某結(jié)點(diǎn)的第一個(gè)孩子是惟一的某結(jié)點(diǎn)的右兄弟是惟一的設(shè)置兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針

structTNode{DataTypedata;StructTNode*firstchild,*nextsib;};6.4樹的存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)firstchild

data

nextsibdata：數(shù)據(jù)域，存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)信息；firstchild：指針域，指向該結(jié)點(diǎn)第一個(gè)孩子；rightsib：指針域，指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)。

孩子兄弟表示法6.4樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？6.4樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找孩子結(jié)點(diǎn)？時(shí)間性能？6.4樹、森林與二叉樹的轉(zhuǎn)換是哪些樹結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)?樹和二叉樹之間具有對(duì)應(yīng)關(guān)系A(chǔ)EBCFDGA∧BC∧E∧D∧F∧∧G∧∧ABCDEFG6.4樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對(duì)應(yīng)關(guān)系

樹：兄弟關(guān)系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG6.4樹、森林與二叉樹的轉(zhuǎn)換1.兄弟加線.樹和二叉樹之間的對(duì)應(yīng)關(guān)系A(chǔ)BCDEFG6.4樹、森林與二叉樹的轉(zhuǎn)換2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG樹和二叉樹之間的對(duì)應(yīng)關(guān)系1.兄弟加線.3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.6.4樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對(duì)應(yīng)關(guān)系2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.6.4樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對(duì)應(yīng)關(guān)系2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF樹轉(zhuǎn)換為二叉樹

⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。

⑶層次調(diào)整——以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。

6.4樹、森林與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換成的二叉樹其右子樹一定為空CBEDFGAABEFCDG前序遍歷AEBCFDGABEFCDG前序遍歷樹的前序遍歷等價(jià)于二叉樹的前序遍歷！6.4樹、森林與二叉樹的轉(zhuǎn)換EFBCGDA后序遍歷EFBCGDA中序遍歷樹的后序遍歷等價(jià)于二叉樹的中序遍歷！6.4樹、森林與二叉樹的轉(zhuǎn)換CBEDFGAAEBCFDG森林轉(zhuǎn)換為二叉樹

⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。6.4樹、森林與二叉樹的轉(zhuǎn)換FEDCBAGHIJBAFEDCGHIKKIFEHABCGD6.4樹、森林與二叉樹的轉(zhuǎn)換二叉樹轉(zhuǎn)換為樹或森林

⑴加線——若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn)y用線連起來；⑵去線——?jiǎng)h去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

6.4樹、森林與二叉樹的轉(zhuǎn)換FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調(diào)整IHGBCDAFE6.4樹、森林與二叉樹的轉(zhuǎn)換森林的遍歷森林有兩種遍歷方法：⑴前序（根）遍歷：前序遍歷森林即為前序遍歷森林中的每一棵樹。⑵后序（根）遍歷：后序遍歷森林即為后序遍歷森林中的每一棵樹。

6.4樹、森林與二叉樹的轉(zhuǎn)換樹的遍歷操作

樹的遍歷：從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。

如何理解訪問?抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。如何理解次序?樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式。樹結(jié)構(gòu)（非線性結(jié)構(gòu)）→線性結(jié)構(gòu)。遍歷的實(shí)質(zhì)?6.4樹、森林與二叉樹的轉(zhuǎn)換前序遍歷

樹的前序遍歷操作定義為：若樹為空，則空操作返回；否則⑴訪問根結(jié)點(diǎn)；⑵

按照從左到右的順序前序遍歷根結(jié)點(diǎn)的每一棵子樹。

前序遍歷序列：ABDEHIFCGACBGFEDHI6.4樹、森林與二叉樹的轉(zhuǎn)換后序遍歷

樹的后序遍歷操作定義為：若樹為空