i/2結點i的左孩子為2i結點i的右孩子為2i＋1

6.2二叉樹的邏輯結構性質5表明，在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系。完全二叉樹的基本性質

6.在滿二叉樹中，葉結點的個數比分支結點個數多1。

7.在擴充二叉樹中，外部結點的個數比內部結點的個數多1。8.對擴充二叉樹,外部路徑長度E和內部路徑長度I的關系：E=I+2n,n是內部結點個數6.2二叉樹的邏輯結構完全二叉樹的基本性質

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

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

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

判斷二叉樹t是否為空。

6.2二叉樹的邏輯結構由于二叉樹的概念是遞歸定義的，二叉樹中的每個結點也可標識以這個結點為根的二叉樹，所以二叉樹類型和二叉樹中結點類型在具體實現時常?？闯墒峭环N類型。

BinTreeNoderoot(BinTreet)

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

返回結點p的父結點。當指定的結點為根時，返回一個特殊值。BinTreeleftChild(BinTreet,BinTreeNodep)

返回p結點的左子樹，當指定結點沒有左子樹時，返回一個特殊值。BinTreerightChild(BinTreet,BinTreeNodep)

返回p結點的右子樹，當指定結點沒有右子樹時，返回一個特殊值。endADTBinTree

二叉樹的抽象數據類型定義6.2二叉樹的邏輯結構順序存儲結構二叉樹的順序存儲結構就是用一維數組存儲二叉樹中的結點，并且結點的存儲位置（下標）應能體現結點之間的邏輯關系——父子關系。

如何利用數組下標來反映結點之間的邏輯關系?完全二叉樹中結點的序號可以唯一地反映出結點之間的邏輯關系。6.2.3二叉樹的存儲結構及實現

A

B

C

D

E

F

G

H

I

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

結點結構：

LChildData

RChild其中，Data：數據域，存放該結點的數據信息；LChild：左指針域，存放指向左孩子的指針；RChild：右指針域，存放指向右孩子的指針。

6.2.3二叉樹的存儲結構及實現typedefstructNode{DataTypedata;strctNode*LChild;structNode*RChild;}BiTNode,*BiTree;6.2.3二叉樹的存儲結構及實現LChild

DataRChild左孩子結點右孩子結點二叉鏈表GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表6.2.3二叉樹的存儲結構及實現具有n個結點的二叉鏈表中，有多少個空指針？GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表6.2.3二叉樹的存儲結構及實現具有n個結點的二叉鏈表中，有n+1個空指針。三叉鏈表6.2.3二叉樹的存儲結構及實現GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉鏈表中，如何求某結點的雙親？三叉鏈表

LChildDataParentRChild在二叉鏈表的基礎上增加了一個指向雙親的指針域。結點結構其中：data、lchild和rchild三個域的含義同二叉鏈表的結點結構；parent域為指向該結點的雙親結點的指針。

6.2.3二叉樹的存儲結構及實現ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧三叉鏈表6.2.3二叉樹的存儲結構及實現二叉樹的遍歷操作

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

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

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結點。

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

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

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

二叉樹的遍歷操作

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

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

6.3二叉樹的周游

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

6.3二叉樹的周游層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。

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

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

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

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

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

二叉樹的遍歷操作

6.3二叉樹的周游前序：ABCDEFG

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

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

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

二叉樹的遍歷操作

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

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

為什么如此處理?如何由一種遍歷序列生成該二叉樹？遍歷是二叉樹各種操作的基礎，可以在遍歷的過程中進行各種操作，例如建立一棵二叉樹。6.3二叉樹的周游擴展二叉樹的前序遍歷序列:AB.D..C..DBAC.DBAC....建立二叉樹6.3二叉樹的周游設二叉樹中的結點均為一個字符。假設擴展二叉樹的前序遍歷序列由鍵盤輸入，root為指向根結點的指針，二叉鏈表的建立過程是：首先輸入根結點，若輸入的是一個“.”字符，則表明該二叉樹為空樹，即root=NULL；否則輸入的字符應該賦給root->data,，之后依次遞歸建立它的左子樹和右子樹。建立二叉樹6.3二叉樹的周游建立二叉鏈表方式存儲的二叉樹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));}}二叉樹算法設計練習遍歷二叉樹是二叉樹各種操作的基礎，遍歷算法中對每個結點的訪問操作可以是多種形式及多個操作，根據遍歷算法的框架，適當修改訪問操作的內容，可以派生出很多關于二叉樹的應用算法。voidInOrder(BiTreeroot){if(root==NULL)return;else{InOrder(root->lchild);

printf(“%c”,root->data);InOrder(root->rchild);}}二叉樹算法設計練習設計算法求二叉樹的結點個數。voidCount(BiTreeroot)//count為全局量并已初始化為0{if(root==NULL)return;else{Count(root->lchild);count++;Count(root->rchild);}}二叉樹算法設計練習設計算法按前序次序打印二叉樹中的葉子結點。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遍歷算法應用1.輸出二叉樹中的結點【算法描述】voidPreOrder(BiTreeroot){ if(root!=NULL){ printf(root->data);/*輸出根結點*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/}}2.輸出二叉樹中的葉子結點voidPreOrder(BiTreeroot){ if(root!=NULL){

if(root->LChild==NULL&&root->RChild==NULL)printf(root->data);/*輸出葉子結點*/PreOrder(root->LChild);/*先序遍歷左子樹*/PreOrder(root->RChild);/*先序遍歷右子樹*/}}3.統(tǒng)計葉子結點數目/*LeafCount為保存葉子結點數目的全局變量,調用之前初始化值為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/*葉子數為左右子樹的葉子數目之和*/

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

若bt為空，則高度為0

若bt非空，其高度應為其左右子樹高度的最大值加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*/}二叉樹前序遍歷的非遞歸算法的關鍵：在前序遍歷過某結點的整個左子樹后，如何找到該結點的右子樹的根指針。解決辦法：在訪問完該結點后，將該結點的指針保存在棧中，以便以后能通過它找到該結點的右子樹。

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

A

B前序遍歷的非遞歸實現

ADBC6.3二叉樹遍歷的非遞歸算法訪問結點序列:A棧S內容:BD

A前序遍歷的非遞歸實現

ADBC

D6.3二叉樹遍歷的非遞歸算法訪問結點序列:A棧S內容:BD

C前序遍歷的非遞歸實現

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

2.1當root不空時循環(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準備遍歷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二叉樹遍歷的非遞歸算法中序遍歷——非遞歸算法在二叉樹的中序遍歷中，訪問結點的操作發(fā)生在該結點的左子樹遍歷完畢并準備遍歷右子樹時，所以，在遍歷過程中遇到某結點時并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語句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二叉樹遍歷的非遞歸算法層序遍歷隊列Q初始化；2.如果二叉樹非空，將根指針入隊；3.循環(huán)直到隊列Q為空3.1p=隊列Q的隊頭元素出隊；3.2訪問結點p的數據域；3.3若結點p存在左孩子，則將左孩子指針入隊；3.4若結點p存在右孩子，則將右孩子指針入隊；6.3二叉樹遍歷的非遞歸算法層序遍歷voidLeverOrder(BiTreeroot){InitQueue(&Q);//采用順序隊列if(root==NULL)return;//二叉樹為空，算法結束p=root;EnterQueue(&Q,p);//指針入隊while(!isEmptyQueue(Q))//當隊列非空時{DelQueue(&Q,&p);//出隊printf(“%c”,p->data);if(p->lchild!=NULL)EnterQueue(&Q,p->lchild);if(p->rchild!=NULL)EnterQueue(&Q,p->rchild);}}6.3二叉樹遍歷的非遞歸算法線索鏈表線索：將二叉鏈表中的空指針域指向前驅結點和后繼結點的指針被稱為線索；線索化：使二叉鏈表中結點的空鏈域存放其前驅或后繼信息的過程稱為線索化；線索鏈表：加上線索的二叉鏈表稱為線索鏈表。6.3二叉樹的線索化如何保存二叉樹的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅結點和后繼結點

LtagLChild

dataRChildRtag0:Lchild指向該結點的左孩子1:Lchild指向該結點的前驅結點0:Rchild指向該結點的右孩子1:Rchild指向該結點的后繼結點Ltag=Rtag=結點結構線索鏈表6.3二叉樹的線索化typedefstructThrNode{DataTypedata;PThrNodelchild,rchild;intltag,rtag;}*PThrNode;線索鏈表結點結構

LtagLChild

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

2.3.1若root沒有左孩子，則為root加上前驅線索;2.3.2若結點pre右標志為1，則為pre加上后繼線索；2.3.3令pre指向剛剛訪問的結點root；2.4對root的右子樹建立線索。中序線索鏈表的建立

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

6.3二叉樹的線索化中序線索鏈表查找后繼FABDCEG⑴如果結點p的右標志為1，則表明該結點的右指針是線索；⑵如果結點p的右標志為0，則表明該結點有右孩子。根據中序遍歷的操作定義，它的后繼結點應該是遍歷其右子樹時第一個訪問的結點，即右子樹中的最左下結點。6.3二叉樹的線索化

PThrNodeNext(PThrNodep){if(p->ltag==1)q=p->lchild;//右標志為1，可直接得到后繼結點

else{q=p->lchild;//工作指針q指向結點p的右孩子

while(q->rtag==0)//查找最左下結點

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

PThrNodeNext(PThrNodep){if(p->rtag==1)q=p->rchild;//右標志為1，可直接得到后繼結點

else{q=p->rchild;//工作指針q指向結點p的右孩子

while(q->ltag==0)//查找最左下結點

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

6.4樹的存儲結構

data

parentdata：存儲樹中結點的數據信息parent：存儲該結點的雙親在數組中的下標structParTreeNode{

DataTypedata;//數據域intparent;//指針域，雙親在數組中的下標};

data

parent6.4樹的存儲結構樹的雙親表示法實質上是一個靜態(tài)鏈表。雙親表示法下標

dataparent012345678

A-1B0C0D1E1F1G2H2I

46.4樹的存儲結構如何查找雙親結點？時間性能？雙親表示法ACBHFEDGI6.4樹的存儲結構雙親表示法ACBHFEDGI如何查找孩子結點？時間性能？下標

dataparentfirstchild136-18-1-1-1-1012345678

A-1B0C0D1E1F1G2H2I

4下標

dataparentrightsib-12-145-17-1-16.4樹的存儲結構雙親表示法012345678

A-1B0C0D1E1F1G2H2I

4ACBHFEDGI如何查找兄弟結點？時間性能？鏈表中的每個結點包括一個數據域和多個指針域，每個指針域指向該結點的一個孩子結點。如何表示孩子？6.4樹的存儲結構孩子鏈表表示法（子表）方案一：指針域的個數等于樹的度datachild1child2……childd其中：data：數據域，存放該結點的數據信息；

child1~childd：指針域，指向該結點的孩子。

6.4樹的存儲結構∧缺點：浪費空間ACBHFEDGIA∧B∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧鏈表中的每個結點包括一個數據域和多個指針域，每個指針域指向該結點的一個孩子結點。如何表示孩子？6.4樹的存儲結構孩子鏈表表示法方案二：

指針域的個數等于該結點的度data

degree

child1

child2

……

childd其中：data：數據域，存放該結點的數據信息；

degree：度域，存放該結點的度；

child1~childd：指針域，指向該結點的孩子。

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

6.4樹的存儲結構如何表示孩子？將結點的所有孩子放在一起，構成線性表。childnext孩子結點structCTNode{

intchild;CTNode*next;};6.4樹的存儲結構structCBNode{DataTypedata;CTNode*firstchild;};孩子鏈表表示法datafirstchild表頭結點ACBHFEDGI012345678下標

datafirstchild

ABCDEFG

H

I

∧∧∧∧6.4樹的存儲結構如何查找孩子結點？時間性能？∧12∧345∧7∧68∧ACBHFEDGI012345678下標

datafirstchild

ABCDEFG

H

I

∧∧∧∧∧6.4樹的存儲結構12∧345∧7∧68∧如何查找雙親結點？時間性能？雙親孩子表示法6.4樹的存儲結構012345678

A-1B0C0D1

∧

E1F1

∧

G

2

∧H

2

∧I

4

∧dataparentfirstchild12∧345∧7∧68∧ACBHFEDGI孩子兄弟表示法(長子兄弟)6.4樹的存儲結構ACBHFEDGI某結點的第一個孩子是惟一的某結點的右兄弟是惟一的設置兩個分別指向該結點的第一個孩子和右兄弟的指針

structTNode{DataTypedata;StructTNode*firstchild,*nextsib;};6.4樹的存儲結構結點結構firstchild

data

nextsibdata：數據域，存儲該結點的數據信息；firstchild：指針域，指向該結點第一個孩子；rightsib：指針域，指向該結點的右兄弟結點。

孩子兄弟表示法6.4樹的存儲結構孩子兄弟表示法ACBHFEDGI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找兄弟結點？時間性能？6.4樹的存儲結構孩子兄弟表示法ACBHFEDGI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找孩子結點？時間性能？6.4樹、森林與二叉樹的轉換是哪些樹結構的存儲結構?樹和二叉樹之間具有對應關系AEBCFDGA∧BC∧E∧D∧F∧∧G∧∧ABCDEFG6.4樹、森林與二叉樹的轉換樹和二叉樹之間的對應關系

樹：兄弟關系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG6.4樹、森林與二叉樹的轉換1.兄弟加線.樹和二叉樹之間的對應關系ABCDEFG6.4樹、森林與二叉樹的轉換2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG樹和二叉樹之間的對應關系1.兄弟加線.3.順時針轉動,使之層次分明.6.4樹、森林與二叉樹的轉換樹和二叉樹之間的對應關系2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG3.順時針轉動,使之層次分明.6.4樹、森林與二叉樹的轉換樹和二叉樹之間的對應關系2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF樹轉換為二叉樹

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

⑵去線——對樹中的每個結點，只保留它與第一個孩子結點之間的連線，刪去它與其它孩子結點之間的連線。

⑶層次調整——以根結點為軸心，將樹順時針轉動一定的角度，使之層次分明。

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

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

⑴加線——若某結點x是其雙親y的左孩子，則把結點x的右孩子、右孩子的右孩子、……，都與結點y用線連起來；⑵去線——刪去原二叉樹中所有的雙親結點與右孩子結點的連線；⑶

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

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

6.4樹、森林與二叉樹的轉換樹的遍歷操作

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

如何理解訪問?抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數據。如何理解次序?樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式。樹結構（非線性結構）→線性結構。遍歷的實質?6.4樹、森林與二叉樹的轉換前序遍歷

樹的前序遍歷操作定義為：若樹為空，則空操作返回；否則⑴訪問根結點；⑵

按照從左到右的順序前序遍歷根結點的每一棵子樹。

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

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