數(shù)據(jù)結(jié)構(gòu) 第六章 樹和二叉樹

數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹第一頁，共六十二頁，2022年，8月28日第一節(jié)樹的類型定義A為“根”T1、T2和T3都是一棵樹，稱為A的子樹。稱根和子樹根之間的連線為“分支”結(jié)點(diǎn)分支的個(gè)數(shù)定義為“結(jié)點(diǎn)的度”，如結(jié)點(diǎn)B的度為2，D的度為3。樹中所有結(jié)點(diǎn)度的最大值定義為“樹的度”。稱度為零的結(jié)點(diǎn)為“葉子” 或“終端結(jié)點(diǎn)”所有度不為零的結(jié)點(diǎn) 被稱作"分支結(jié)點(diǎn)"第二頁，共六十二頁，2022年，8月28日基本定義森林為m(m≥0)棵互不相交的樹的集合。樹的深度定義為樹中葉子結(jié)點(diǎn)所在最大層次數(shù)。稱根結(jié)點(diǎn)為子樹根的"雙親"。稱子樹根為根結(jié)點(diǎn)的"孩子“根的所有子樹根互為“兄弟”。有序樹、無序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。第三頁，共六十二頁，2022年，8月28日樹的抽象數(shù)據(jù)類型：ADTTree{

數(shù)據(jù)對(duì)象：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系：

若D為空集，則稱為空樹；

若D中僅含一個(gè)數(shù)據(jù)元素，則關(guān)系R為空集；

否則R={H}，

(1)

在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)

當(dāng)n>1時(shí)，其余數(shù)據(jù)元素可分為m(m>0)個(gè)互不相交的(非空)有限集T1,T2,…,Tm,其中每一個(gè)子集本身又是一棵符合本定義的樹，稱為根root的子樹，每一棵子樹的根xi都是根root的后繼，即<root,xi>H,i=1,2,…,m。第四頁，共六十二頁，2022年，8月28日基本操作：

{結(jié)構(gòu)初始化}

InitTree(&T);

操作結(jié)果：構(gòu)造空樹T。

CreateTree(&T,definition);

初始條件：definition給出樹T的定義。

操作結(jié)果：按definition構(gòu)造樹T。

{銷毀結(jié)構(gòu)}

DestroyTree(&T);

初始條件：樹T存在。

操作結(jié)果：銷毀樹T。第五頁，共六十二頁，2022年，8月28日{(diào)引用型操作}

TreeEmpty(T);

初始條件：樹T存在。

操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE。

TreeDepth(T);

初始條件：樹T存在。

操作結(jié)果：返回T的深度。

Root(T);

初始條件：樹T存在。

操作結(jié)果：返回T的根。

Value(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回cur_e的值。第六頁，共六十二頁，2022年，8月28日Parent(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回"空"。

LeftChild(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回"空"。

RightSibling(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則返回"空"。

TraverseTree(T,visit());

初始條件：樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。

第七頁，共六十二頁，2022年，8月28日{(diào)加工型操作}

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。

ClearTree(&T);

初始條件：樹T存在。

操作結(jié)果：將樹T清為空樹。

InsertChild(&T,&p,i,c);

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所指結(jié)點(diǎn)的度＋1，非空樹c與T不相交。

操作結(jié)果：插入c為T中p所指結(jié)點(diǎn)的第i棵子樹。

DeleteChild(&T,&p,i);

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度。

操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹。

}ADTTree

第八頁，共六十二頁，2022年，8月28日樹和線性結(jié)構(gòu)對(duì)照：第九頁，共六十二頁，2022年，8月28日第二節(jié)二叉樹類型定義：二叉樹是另一種樹形結(jié)構(gòu)。它與樹形結(jié)構(gòu)的區(qū)別是：（1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹；（2）子樹有左右之分。二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱為空二叉樹；當(dāng)n>0時(shí)，有且僅有一個(gè)結(jié)點(diǎn)為二叉樹的根，其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集，一個(gè)作為左子集，另一個(gè)作為右子集，每個(gè)子集又是一個(gè)二叉樹。第十頁，共六十二頁，2022年，8月28日二叉樹的5種形態(tài)：?(a)(b)(c)(d)(e)第十一頁，共六十二頁，2022年，8月28日6.2.1二叉樹的類型定義ADTBinaryTree{

數(shù)據(jù)對(duì)象：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系：

若D為空集，稱BinaryTree為空二叉樹；

否則關(guān)系R={H}：

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)D中其余元素必可分為兩個(gè)互不相交的子集

L和R，每一個(gè)子集都是一棵符合本定義的二叉樹，并分別為root的左子樹和右子樹。如果左子樹L不空，則必存在一個(gè)根結(jié)點(diǎn)，它是root的"左后繼"(<root,>∈H)，如果右子樹R不空，則必存在一個(gè)根結(jié)點(diǎn)為root的"右后繼"(<root,>∈H)。第十二頁，共六十二頁，2022年，8月28日第十三頁，共六十二頁，2022年，8月28日基本操作P：

{結(jié)構(gòu)初始化}

InitBiTree(&T);

操作結(jié)果：構(gòu)造空二叉樹T。

CreateBiTree(&T,definition);

初始條件：definition給出二叉樹T的定義。

操作結(jié)果：按definition構(gòu)造二叉樹T。

{銷毀結(jié)構(gòu)}

DestroyBiTree(&T);

初始條件：二叉樹T存在。

操作結(jié)果：銷毀二叉樹T。第十四頁，共六十二頁，2022年，8月28日{(diào)引用型操作}

BiTreeEmpty(T);

初始條件：二叉樹T存在。

操作結(jié)果：若T為空二叉樹，則返回TRUE，否則返回FALSE。

BiTreeDepth(T);

初始條件：二叉樹T存在。

操作結(jié)果：返回T的深度。

Root(T);

初始條件：二叉樹T存在。

操作結(jié)果：返回T的根。

Value(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的值。第十五頁，共六十二頁，2022年，8月28日Parent(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回"空"。

LeftChild(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的左孩子。若e無左孩子，則返回"空"。

RightChild(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的右孩子。若e無右孩子，則返回"空"。

LeftSibling(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的左兄弟。若e是其雙親的左孩子或無左兄弟，則返回"空"。第十六頁，共六十二頁，2022年，8月28日RightSibling(T,e);

初始條件：二叉樹T存在，e是T的結(jié)點(diǎn)。

操作結(jié)果：返回e的右兄弟。若e是其雙親的右孩子或無右兄弟，則返回"空"。

PreOrderTraverse(T,visit());

初始條件：二叉樹T存在,visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：先序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

InOrderTraverse(T,vsit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：中序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。

PostOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：后序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。第十七頁，共六十二頁，2022年，8月28日

LevelOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：層序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

{加工型操作}

ClearBiTree(&T);

初始條件：二叉樹T存在。

操作結(jié)果：將二叉樹T清為空樹。

Assign(&T,&e,value);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)e賦值為value。第十八頁，共六十二頁，2022年，8月28日InsertChild(&T,p,LR,c);

初始條件：二叉樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，LR為0或1，非空二叉樹c與T不相交且右子樹為空。

操作結(jié)果：根據(jù)LR為0或1，插入c為T中p所指結(jié)點(diǎn)的左或右子樹。p所指結(jié)點(diǎn)原有左或右子樹成為c的右子樹。

DeleteChild(&T,p,LR);

初始條件：二叉樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，LR為0或1。

操作結(jié)果：根據(jù)LR為0或1，刪除T中p所指結(jié)點(diǎn)的左或右子樹。

}ADTBinaryTree

第十九頁，共六十二頁，2022年，8月28日6.2.2二叉樹的幾個(gè)特性一、在二叉樹的第i層上至多有2i-1

個(gè)結(jié)點(diǎn)(i≥1)。二、深度為k的二叉樹中至多含有2k-1

個(gè)結(jié)點(diǎn)，(k≥1)。三、對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

第二十頁，共六十二頁，2022年，8月28日若二叉樹中所有的分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。假如一棵包含n個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)都可以和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一、一對(duì)應(yīng)，則稱這類二叉樹為完全二叉樹。第二十一頁，共六十二頁，2022年，8月28日第二十二頁，共六十二頁，2022年，8月28日第三節(jié)二叉樹的存儲(chǔ)表示6.3.1順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)的定義如下：constMAXSIZE=100;//暫定二叉樹中結(jié)點(diǎn)數(shù)的最大值為100

typedefstruct{

ElemType*data;

//存儲(chǔ)空間基址(初始化時(shí)分配空間)

intnodeNum;

//二叉樹中結(jié)點(diǎn)數(shù)

}SqBiTree;

//二叉樹的順序存儲(chǔ)結(jié)構(gòu)

第二十三頁，共六十二頁，2022年，8月28日6.3.2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的二叉鏈表存儲(chǔ)表示typedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

}*BiTree;第二十四頁，共六十二頁，2022年，8月28日二叉樹的三叉鏈表存儲(chǔ)表示typedefstructTriTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

structBiTNode*parent;

//雙親指針

}*TriTree;第二十五頁，共六十二頁，2022年，8月28日二叉樹的雙親鏈表存儲(chǔ)表示typedefstructBPTNode{

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

ElemTypedata;

int*parent;

//指向雙親的指針

charLRTag;

//左、右孩子標(biāo)志域

}BPTNode第二十六頁，共六十二頁，2022年，8月28日第四節(jié)二叉樹的遍歷“遍歷”的含義是對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都訪問一次且僅僅訪問一次。由于二叉樹中每個(gè)結(jié)點(diǎn)都有兩個(gè)后繼，則可以有三條搜索路徑：

1)先左(子樹)后右(子樹)；

2)先右(子樹)后左(子樹)；

3)按層次從上到下。第二十七頁，共六十二頁，2022年，8月28日6.4.1先左后右的遍歷6-4-1遍歷.swf第二十八頁，共六十二頁，2022年，8月28日GHDEFBCA先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA 第二十九頁，共六十二頁，2022年，8月28日先序遍歷遞歸算法voidPreOrder(BTreeBT){if(BT){Visit(BT);PreOrder(BT->Lchild);PreOrder(BT->Rchild);}}6-4-2-1.swf第三十頁，共六十二頁，2022年，8月28日中序遍歷遞歸算法voidInOrder(BTreeBT){if(BT){InOrder(BT->Lchild);Visit(BT);InOrder(BT->Rchild);}}6-4-2-2.swf第三十一頁，共六十二頁，2022年，8月28日后序遍歷遞歸算法voidPostOrder(BTreeBT){if(BT){PostOrder(BT->Lchild);PostOrder(BT->Rchild);Visit(BT);}}6-4-2-3.swf第三十二頁，共六十二頁，2022年，8月28日按層次遍歷二叉樹按層次遍歷該二叉樹的序列為：

ABCDEFGHGHDEFBCA第三十三頁，共六十二頁，2022年，8月28日二叉樹用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示時(shí)，按層遍歷的算法實(shí)現(xiàn)（1）訪問根結(jié)點(diǎn)，并將根結(jié)點(diǎn)入隊(duì)；（2）當(dāng)隊(duì)列不空時(shí)，重復(fù)下列操作：從隊(duì)列退出一個(gè)結(jié)點(diǎn)；若其有左孩子，則訪問左孩子，并將其左孩子入隊(duì)；若其有右孩子，則訪問右孩子，并將其右孩子入隊(duì)；GHDEFBCA第三十四頁，共六十二頁，2022年，8月28日voidLevelOrder(BTree*BT){if(!BT)exit;InitQueue(Q);p=BT;//初始化

Visite(p);EnQueue(&Q,p);

//訪問根結(jié)點(diǎn)，并將根結(jié)點(diǎn)入隊(duì)

while(!QueueEmpty(Q)){//當(dāng)隊(duì)非空時(shí)重復(fù)執(zhí)行下列操作

DeQueue(&Q,&p);//出隊(duì)

if(!p->Lchild){Visite(p->Lchild);EnQueue(&Q,p->Lchild);}//處理左孩子

if(!p->Rchild){Visite(p->Rchild);EnQueue(&Q,p->Rchild);}//處理右孩子

}}第三十五頁，共六十二頁，2022年，8月28日建立二叉樹voidCreateBiTree(BiTree&T)

{

//

在先序遍歷二叉樹的過程中輸入二叉樹的"先序字符串"，

//

建立根指針為T的二叉鏈表存儲(chǔ)結(jié)構(gòu)。在先序字符串中，

//

字符'#'表示空樹，其它字母字符為結(jié)點(diǎn)的數(shù)據(jù)元素

cin>>ch；

if(ch=='#')T=NULL;

//

建空樹

else{

T=newBiTNode;//"訪問"操作為生成根結(jié)點(diǎn)

T->data=ch;

CreateBiTree(T->Lchild);

//

遞歸建(遍歷)左子樹

CreateBiTree(T->Rchild);

//

遞歸建(遍歷)右子樹

}

}6-4-6.swf第三十六頁，共六十二頁，2022年，8月28日統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)voidCountLeaf(BiTreeT,int&count)

{

//先序遍歷二叉樹，以count返回二叉樹中葉子結(jié)點(diǎn)的數(shù)目

if(T){

if((!T->Lchild)&&(!T->Rchild))

count++;

//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->Lchild,count);

CountLeaf(T->Rchild,count);

}//if

}第三十七頁，共六十二頁，2022年，8月28日求二叉樹的深度voidBiTreeDepth(BiTreeT,intlevel,int&depth)

{//T指向二叉樹的根，level為T所指結(jié)點(diǎn)所在層次，其初值為1，depth為當(dāng)前求得的最大層次,其初值為0

if(T){

if(level>depth)depth=level;

BiTreeDepth(T->Lchild,level+1,depth);

BiTreeDepth(T->Rchild,level+1,depth);

}

}6-4-3求二叉樹的深度.swf第三十八頁，共六十二頁，2022年，8月28日復(fù)制二叉樹生成一個(gè)二叉樹的結(jié)點(diǎn)的算法：BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)

{//生成一個(gè)其元素值為item，左指針為lptr，右指針為rptr的結(jié)點(diǎn)

T=newBiTNode;T->data=item;

T->Lchild=lptr;T->Rchild=rptr;

returnT;

}

第三十九頁，共六十二頁，2022年，8月28日后序遍歷復(fù)制二叉樹的操作為:BiTNode*CopyTree(BiTNode*T)

{

//已知二叉樹的根指針為T，本算法返回它的復(fù)制品的根指針

if(!T)

returnNULL;

//復(fù)制一棵空樹

if(T->Lchild)

newlptr=CopyTree(T->Lchild);

//復(fù)制(遍歷)左子樹

elsenewlptr=NULL;

if(T->Rchild)

newrptr=CopyTree(T->Rchild);//復(fù)制(遍歷)右子樹

elsenewrptr=NULL;

newnode=GetTreeNode(T->data,newlptr,newrptr);//生成根結(jié)點(diǎn)

returnnewnode;

}6-4-5后序遍歷復(fù)制.swf第四十頁，共六十二頁，2022年，8月28日在二叉樹上查詢某個(gè)結(jié)點(diǎn)voidlocate(BiTreeT,ElemTypex,BiTree&p)

{

//

若二叉樹T中存在和x相同的元素，則p指向該結(jié)點(diǎn)，否則p的值不變，p的初值為NULL

if(T)

{if(T->data==x)p=T;

locate(T->lchild,x,p);

locate(T->rchild,x,p);

}

}第四十一頁，共六十二頁，2022年，8月28日中序遍歷（非遞歸）InitStack(S); Push(S,T); //根入棧

while(!StackEmpty(S)) { while(GetTop(S,p)&&p) Push(S,p->lchild); //向左到盡頭

Pop(S,p); //空指針出棧

if(!StackEmpty(S)) //訪問，向右

{ Pop(S,p); if(!Visit(p->data))returnERROR; Push(S,p->rchild); } } returnOK;第四十二頁，共六十二頁，2022年，8月28日表達(dá)式的二叉樹第四十三頁，共六十二頁，2022年，8月28日二叉樹的線索鏈表將在二叉樹中每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)外）的直接前驅(qū)和直接后繼保存起來。這種信息是在遍歷的動(dòng)態(tài)過程中產(chǎn)生的，如果將這些信息在第一次遍歷時(shí)就保存起來，則在以后再次需要對(duì)二叉樹進(jìn)行“遍歷”時(shí)就可以將二叉樹視作線性結(jié)構(gòu)進(jìn)行訪問操作了。typedefenumPointerType{Link=0,Thread=1};

//定義指針類型，以Link表示指針，Thread表示線索

typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*Lchild,*Rchild;//左右指針

PointerTypeLTag,RTag;//左右指針類型標(biāo)志

}*BiThrTree;第四十四頁，共六十二頁，2022年，8月28日在線索鏈表中添加了一個(gè)"頭結(jié)點(diǎn)"，頭結(jié)點(diǎn)的左指針指向二叉樹的根結(jié)點(diǎn)，其右線索指向中序序列中的最后一個(gè)結(jié)點(diǎn)第四十五頁，共六十二頁，2022年，8月28日以中序線索鏈表為存儲(chǔ)結(jié)構(gòu)的中序遍歷voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(ElemTypee))

{//T指向中序線索鏈表中的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左指針Lchild指向二叉樹的根結(jié)點(diǎn)，頭結(jié)點(diǎn)的右線索Rchild指向中序遍歷訪問的最后一個(gè)結(jié)點(diǎn)。本算法對(duì)此二叉樹進(jìn)行中序遍歷，對(duì)樹中每個(gè)元素調(diào)用函數(shù)Visit進(jìn)行訪問操作

p=T->Lchild;

//p指向二叉樹的根結(jié)點(diǎn)

while(p!=T) {

//空樹或遍歷結(jié)束時(shí)，p==Thead

while(p->LTag==Link)p=p->Lchild;

Visit(p->data);

//訪問其左子樹為空的結(jié)點(diǎn)

while(p->RTag==Thread&&p->Rchild!=T) {

p=p->rchild;Visit(p->data);//訪問“右線索”所指后繼結(jié)點(diǎn)

}

p=p->Rchild;

//p進(jìn)至其右子樹根

}

}第四十六頁，共六十二頁，2022年，8月28日p=T->Lchild;

//p指向二叉樹的根結(jié)點(diǎn)

while(p!=T){

//空樹或遍歷結(jié)束時(shí)，p==Thead

while(p->LTag==Link)p=p->Lchild;

Visit(p->data);

//訪問其左子樹為空的結(jié)點(diǎn)

while(p->RTag==Thread&&p->Rchild!=T){

p=p->rchild;Visit(p->data);//訪問“右線索”所指后繼結(jié)點(diǎn)

}

p=p->Rchild;

//p進(jìn)至其右子樹根

}6-5-1.swf第四十七頁，共六十二頁，2022年，8月28日線索鏈表的生成voidInThreading(BiThrTreep，BiThrTree&pre)

{

//對(duì)p指向根結(jié)點(diǎn)的二叉樹進(jìn)行中序遍歷，遍歷過程中進(jìn)行“中序線索化”。若p所指結(jié)點(diǎn)的左指針為空，則將它改為“左線索”，若pre所指結(jié)點(diǎn)的右指針為空，則將它改為“右線索”。指針pre在遍歷過程中緊隨其后，即始終指向p所指結(jié)點(diǎn)在中序序列中的前驅(qū)。

if(p){

InThreading(p->Lchild,pre);

//對(duì)左子樹進(jìn)行線索化

if(!p->Lchild)

{p->LTag=Thread;p->Lchild=pre;}//建前驅(qū)線索

if(!pre->Rchild)

{pre->RTag=Thread;pre->Rchild=p;}//建后繼線索

pre=p;

//保持pre指向p的前驅(qū)

InThreading(p->Rchild,pre);

//對(duì)右子樹進(jìn)行線索化

}

}第四十八頁，共六十二頁，2022年，8月28日voidInOrderThreading(BiThrTree&Th,BiThrTreeBT)

{

//BT為指向二叉樹根結(jié)點(diǎn)的指針，由此二叉鏈表建立二叉樹的中序線索鏈表，Thead指向線索鏈表中的頭結(jié)點(diǎn)。

BiThrTreepre;

if(!(Th=newBiThrNode))exit(1);//存儲(chǔ)分配失敗

Th->LTag=Link;Th->RTag=Thread;

//建頭結(jié)點(diǎn)

Th->Rchild=Th;

//右指針回指

if(!BT)Th->Lchild=Th;

//若二叉樹空，則左指針回指

else{

Th->Lchild=BT;pre=Thead;

InThreading(BT,pre);

//中序遍歷進(jìn)行中序線索化

pre->Rchild=Th;pre->RTag=Thead;//對(duì)中序序列中最后一個(gè)結(jié)點(diǎn)進(jìn)行線索化

Th->Rchild=pre;

//建非空樹的頭結(jié)點(diǎn)的"右線索"

}

}6-5-2.swf第四十九頁，共六十二頁，2022年，8月28日樹和森林的存儲(chǔ)表示

1樹的雙親表示法

constMAX_TREE_SIZE=100;

typedefstruct{//結(jié)點(diǎn)結(jié)構(gòu)

ElemTypedata;

intparent;//雙親位置域

}PTNode;

typedefstruct{//樹結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根的位置和結(jié)點(diǎn)數(shù)

}PTree;

第五十頁，共六十二頁，2022年，8月28日第五十一頁，共六十二頁，2022年，8月28日2樹的孩子表示法樹的孩子鏈表存儲(chǔ)表示

typedefstructCTNode{

//孩子結(jié)點(diǎn)

intchild;

structCTNode*next;

}*ChildPtr;

typedefstruct{

ElemTypedata;/