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

第六章樹和二叉樹6.1樹的類型定義樹（Tree）是n（n≥0）個結(jié)點(diǎn)的有限集。在任意一棵非空樹當(dāng)中：（1）有且僅有一個特定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（Root）（2）當(dāng)n〉1時，其余結(jié)點(diǎn)可分為m（m〉0）個互不相交的有限集T1T2…Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（subtree）樹結(jié)構(gòu)中的基本術(shù)語：結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的個數(shù)。終端結(jié)點(diǎn)（葉子）：度為0的結(jié)點(diǎn)非終端結(jié)點(diǎn)（分支）：度不為0的結(jié)點(diǎn)樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。孩子：結(jié)點(diǎn)子樹的根結(jié)點(diǎn)。雙親：結(jié)點(diǎn)本身成為其孩子的雙親（父）結(jié)點(diǎn)。兄弟：同一個雙親結(jié)點(diǎn)的孩子之間互稱為兄弟。祖先：是從根到該節(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。子孫：以某結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)。結(jié)點(diǎn)的層次：從根開始定義為第1層，根的孩子為第二層……堂兄弟：其雙親在同一層的結(jié)點(diǎn)。樹的深度（高度）：樹中結(jié)點(diǎn)的最大層數(shù)。有序樹：樹中結(jié)點(diǎn)的子樹看成從左到右有序的（不能互換），則稱概樹為有序樹，否則稱為無序樹。森林（forest）：是m（m≥0）棵互不相交的樹的集合。樹的抽象數(shù)據(jù)類型的定義如下：

ADTTree{

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

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

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

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

否則R={H}，

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

(2)當(dāng)n>1時，其余數(shù)據(jù)元素可分為m(m>0)個互不相交的(非空)有限集T1,T2,…,Tm,其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹，每一棵子樹的根xi都是根root的后繼，即<root,xi>H,i=1,2,…,m。

基本操作：

{結(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。{引用型操作}

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中某個結(jié)點(diǎn)。

操作結(jié)果：返回cur_e

的值。

Parent(T,cur_e);

初始條件：樹T存在，cur_e

是T中某個結(jié)點(diǎn)。

操作結(jié)果：若cur_e

是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。LeftChild(T,cur_e);

初始條件：樹T存在，cur_e

是T中某個結(jié)點(diǎn)。

操作結(jié)果：若cur_e

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

RightSibling(T,cur_e);

初始條件：樹T存在，cur_e

是T中某個結(jié)點(diǎn)。

操作結(jié)果：若cur_e

有右兄弟，則返回它的右兄弟，否則返回“空”。

TraverseTree(T,visit());

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

操作結(jié)果：按某種次序?qū)的每個結(jié)點(diǎn)調(diào)用函數(shù)

visit()一次且至多一次。

一旦visit()失敗，則操作失敗。{加工型操作}

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e

是T中某個結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)cur_e

賦值為value。

ClearTree(&T);

初始條件：樹T存在。

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

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

初始條件：樹T存在，p指向T中某個結(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中某個結(jié)點(diǎn)，

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

}ADTTree

可從另一個角度來定義樹。

定義森林為m(m≥0)棵互不相交的樹的集合。

則可定義樹是一個二元組

Tree=(root,F)

其中，root

是數(shù)據(jù)元素，稱作樹的根，

F

是子樹森林，記作F=(T1,T2,…,Tm),

其中Ti=(ri,Fi)

為根root的第i棵(符合本定義的)子樹，當(dāng)m≠0是，在樹根和其子樹森林之間存在下列關(guān)系：

RF={<root,ri>|i=1,2,…,m,m>0}

樹和線性結(jié)構(gòu)作如下對照：線性結(jié)構(gòu)樹結(jié)構(gòu)存在唯一的沒有前驅(qū)

的"首元素"存在唯一的沒有前驅(qū)的

"根結(jié)點(diǎn)"

存在唯一的沒有后繼

的"尾元素"

存在多個沒有后繼的

"葉子"

其余元素均存在唯一

的"前驅(qū)元素"和唯一

的"后繼元素"

其余結(jié)點(diǎn)均存在唯一的

"前驅(qū)(雙親)結(jié)點(diǎn)"和多

個"后繼(孩子)結(jié)點(diǎn)"6.2二叉樹類型6.2.1二叉樹的類型定義

二叉樹的抽象數(shù)據(jù)類型定義如下:ADTBinaryTree{

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

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

若D為空集，稱BinaryTree

為空二叉樹；

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

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素

root，它在關(guān)系H下無前驅(qū)；

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

L和R，每一個子集都是一棵符合本定義的二叉樹，并分別為root的左子樹和右子樹。如果左子樹L不空，則必存在一個根結(jié)點(diǎn)XL，它是root的“左后繼”(<root,XL>∈H)如果右子樹R不空，則必存在一個根結(jié)點(diǎn)XR，為root的"右后繼"(<root,XR>∈H)。

基本操作：

{結(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。

{引用型操作}

BiTreeEmpty(T);

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

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

BiTreeDepth(T);

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

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

Root(T);

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

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

Value(T,e);

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

操作結(jié)果：返回e的值。Parent(T,e);

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

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

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

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

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

操作結(jié)果：返回e的右孩子。若e無右孩子，則返回“空”。LeftSibling(T,e);

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

操作結(jié)果：返回e的左兄弟。若e是其雙親的左孩子或無左兄弟，則返回“空”。RightSibling(T,e);

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

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

PreOrderTraverse(T,visit());

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

操作結(jié)果：先序遍歷T，對每個結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。InOrderTraverse(T,vsit());

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

操作結(jié)果：中序遍歷T，對每個結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。

PostOrderTraverse(T,visit());

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

操作結(jié)果：后序遍歷T，對每個結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。LevelOrderTraverse(T,visit());

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

操作結(jié)果：層序遍歷T，對每個結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

{加工型操作}

ClearBiTree(&T);

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

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

Assign(&T,&e,value);

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

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

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

初始條件：二叉樹T存在，p指向T中某個結(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中某個結(jié)點(diǎn)，LR為0或1。

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

}ADTBinaryTree

6.2.2二叉樹的幾個特性

一、在二叉樹的第i層上至多有2i-1

個結(jié)點(diǎn)(i≥1)。

利用歸納法容易證得此結(jié)論。證明：

歸納基：i=1

時，只有一個根結(jié)點(diǎn)。顯然2i-1=20=1是對的。歸納假設(shè)：設(shè)對所有的j(1≤j<i)，命題成立，即第j層上至多有2j-1

個結(jié)點(diǎn)。歸納證明：由歸納假設(shè)“第i-1層上至多有

2i-2個結(jié)點(diǎn)”，又二叉樹的每個結(jié)點(diǎn)的度至多為2，則第

i層上的最大結(jié)點(diǎn)數(shù)為第

i-1層上最大結(jié)點(diǎn)數(shù)的2倍，即2×2i-2=2i-1。證畢。二、深度為k的二叉樹中至多含有2k-1個結(jié)點(diǎn)，(k≥1)。證明：

由特性一可推出，深度為k的二叉樹上最大結(jié)點(diǎn)數(shù)為三、對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則

n0

=n2

+1證明：

由于二叉樹中只有三種結(jié)點(diǎn)，假設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)，則二叉樹中結(jié)點(diǎn)總數(shù)為

n=n0+n1+n2

①

再看二叉樹中的分支數(shù)目。除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個分支進(jìn)入，假設(shè)B為分支數(shù)，則

n=B+1。從另一角度看，這些分支是由度為1或2的結(jié)點(diǎn)射出的，所以又有B=n1+2n2

即n=n1+2n2+1

②

綜合以上①和②兩個等式便可得到

n0=n2+1

有兩種特殊形態(tài)的二叉樹滿二叉樹:若二叉樹中所有的分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。

對滿二叉樹從上到下從左到右進(jìn)行從1開始的編號（如圖所示），則任意一棵二叉樹都可以和同深度的滿二叉樹相對比。完全二叉樹

:假如一棵包含n個結(jié)點(diǎn)的二叉樹中每個結(jié)點(diǎn)都可以和滿二叉樹中編號為1至n的結(jié)點(diǎn)一、一對應(yīng)，則稱這類二叉樹為完全二叉樹。顯然一棵深度為h的完全二叉樹中，前h-1層中的結(jié)點(diǎn)都是"滿"的，且第h層的結(jié)點(diǎn)都集中在左邊。顯然，滿二叉樹本身也是完全二叉樹。

四、具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。

假設(shè)該完全二叉樹的深度為k，則根據(jù)特性二和完全二叉樹的定義

2k-1-1<n≤2k-1

或2k-1≤n<2k

對后者取對數(shù)便得k-1≤log2n<k

因為k是整數(shù)，所以k=[log2n]+1

。

五、如果對一棵有n個結(jié)點(diǎn)的完全二叉樹（其深度為log2n+1）的結(jié)點(diǎn)按層序（從第1層到第log2n+1層，每層從左到右）從1起開始編號，則對任一編號為i的結(jié)點(diǎn)(1≤i≤n)，有

(1)

如果i=1，則編號為i的結(jié)點(diǎn)是二叉樹的根，無雙親；如果

i>1，則其雙親結(jié)點(diǎn)parent(i)

的編號是

i/2

。

(2)

如果

2i>n，則編號為i

的結(jié)點(diǎn)無左孩子（編號為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)

的編號是2i

。

(3)

如果2i+1>n，則編號為i

的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn)rChild(i)

的編號是結(jié)點(diǎn)

2i+1。6.3二叉樹的存儲表示

用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素。二叉樹的順序存儲結(jié)構(gòu)的定義如下：

constMAXSIZE=100;//定二叉樹中結(jié)點(diǎn)數(shù)的max為100

typedef

struct

{

ElemType

data[MAXSIZE];//存儲空間基址(初始化時分配空間)

int

nodeNum;

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

}SqBiTree;

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

對于完全二叉樹，只要從根起按層序存儲即可。

0123456789abcdefghij根據(jù)二叉樹的特性五，可推出順序存儲結(jié)構(gòu)中“雙親”和“孩子”的關(guān)系：

假設(shè)bt.data[i]

是完全二叉樹上的一個結(jié)點(diǎn)，若

2i+1<bt.nodeNum，則bt.data[2i+1]

是它的左孩子，否則它的左子樹為空樹；若2i+2<bt.nodeNum，則bt.data[2i+2]是它的右孩子，否則它的右子樹為空樹。對于一般二叉樹，應(yīng)將其每個結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對照，存在一維數(shù)組的相應(yīng)分量中，不存在的結(jié)點(diǎn)用0表示01234567891011121314ABC0E0F00G000006.3.2鏈?zhǔn)酱鎯Y(jié)構(gòu)

一、二叉鏈表二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)：lchilddatarchild二叉樹的二叉鏈表存儲表示

typedef

struct

BiTNode

{

ElemTypedata;

struct

BiTNode*Lchild,*Rchild;

}*BiTree;a圖二叉樹的二叉鏈表如下b圖所示。

ab二、三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)：parentlchilddatachild二叉樹的三叉鏈表存儲表示

typedef

struct

TriTNode

{

ElemTypedata;

struct

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

struct

BiTNode*parent;

//雙親指針

}*TriTree;

和上頁相同的二叉樹的三叉鏈表如下圖所示。

6.4二叉樹的遍歷遍歷二叉樹有兩種方法：

1)深度優(yōu)先遍歷二叉樹（三部分，根、左子樹、右子樹）

2)廣度優(yōu)先遍歷二叉樹（按層次遍歷）6.4.1深度優(yōu)先遍歷

深度優(yōu)先遍歷由左到右TLR,LTR,LRT由右到左TRL,RTL,RLT三個深度優(yōu)先遍歷二叉樹的算法：

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。請參看flash6-4-2-1、flash6-4-2-2、flash6-4-2-3由于遍歷算法的定義很容易寫出對應(yīng)的遞歸算法算法6.1

voidPreorder(BiTreeT，void(*visit)(BiTree))

{

//先序遍歷以T為根指針的二叉樹

if(T){//T=NULL時，二叉樹為空樹，不做任何操作

visit(T);

//通過函數(shù)指針*visit訪問根結(jié)點(diǎn)

Preorder(T->Lchild,visit);//先序遍歷左子樹

Preorder(T->Rchild,visit);//先序遍歷右子樹

}//if

}//Preorder根據(jù)遍歷遞歸算法遞歸工作棧的狀態(tài)變化狀況可以直接寫出相應(yīng)的非遞歸算法算法6.2

void

InorderTraverse(BiTreeT，void(*visit)(BiTree))

{

//采用二叉鏈表存儲結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的//應(yīng)用函數(shù)。中序遍歷二叉樹T的非遞歸算法，對每一//個數(shù)據(jù)元素調(diào)用

visit

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->lchild))ReturnERROR;

Push(S,P->rchild);

}//if

}//while

Returnok;

}//InorderTraverse層次遍歷右圖的遍歷序列為：ABCDTFGHIJ6.4.2廣度優(yōu)先遍歷二叉樹（按層次遍歷二叉樹）過程：先訪問第1層，然后從左到右依次訪問第2層兩個節(jié)點(diǎn)，依此類推，當(dāng)?shù)趇層訪問完以后，在從左到右訪問第i+1層的各個節(jié)點(diǎn)。這里需要使用一個隊列作為輔助的存儲結(jié)構(gòu)

在遍歷開始時，首先把根節(jié)點(diǎn)放入隊列；然后每次從隊列中取出隊頭元素進(jìn)行處理，每處理一個結(jié)點(diǎn)時，按從左到右的順序把它的所有子結(jié)點(diǎn)放入隊列。這樣，上層結(jié)點(diǎn)總是排在下一層結(jié)點(diǎn)的前面，從而實(shí)現(xiàn)了二叉樹的廣度優(yōu)先遍歷。二叉樹的廣度優(yōu)先遍歷算法，同學(xué)們自己練習(xí)寫下6.5線索二叉樹

6.5.1二叉樹的線索鏈表

先序序列為：

ABDEGHCFIJ

中序序列為：

DBGEHACIJF

后序序列為：

DGHEBJIFCA

如何保存在遍歷過程中得到的前驅(qū)和后繼信息？方法一：最簡單的辦法是在結(jié)點(diǎn)中增加兩個指針域分別指向該結(jié)點(diǎn)的前驅(qū)和后繼，但如此做將使存儲結(jié)構(gòu)的存儲密度大大降低。方法二：一個含n個結(jié)點(diǎn)的二叉鏈表中有n+1個鏈域的值為"NULL"，可以利用這些空的指針域存放指向前驅(qū)和后繼的信息，由此得到的二叉樹的存儲結(jié)構(gòu)稱作"線索鏈表"，其中指向前驅(qū)或后繼的指針稱作"線索"。線索鏈表的結(jié)構(gòu)定義如下：

二叉樹的二叉線索鏈表存儲表示

typedef

enum

PointerType{Link=0,Thread=1};

//

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

typedef

struct

BiThrNode{

ElemTypedata;

struct

BiThrNode

*Lchild,*Rchild;

//

左右指針

PointerType

LTag,RTag;

//

左右指針類型標(biāo)志

}

*BiThrTree;

若結(jié)點(diǎn)的左指針類型標(biāo)志為“Link”，則Lchild

指向它的左子樹根結(jié)點(diǎn)，否則指向它的“前驅(qū)”；

若結(jié)點(diǎn)的右指針類型標(biāo)志為“Link”，則Rchild

指向它的右子樹根結(jié)點(diǎn)，否則指向它的"后繼"。

圖二叉樹的中序線索鏈表如下所示（圖中所有實(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)置于一個雙向循環(huán)鏈表之中，即可以從頭結(jié)點(diǎn)出發(fā)，依照中序遍歷的規(guī)則對二叉樹中的結(jié)點(diǎn)依次進(jìn)行"順序"（和中序序列相同的次序）訪問，或"逆序"（和中序序列相反的次序）訪問。

6.5.2以中序線索鏈表為存儲結(jié)構(gòu)的中序遍歷如何在中序線索鏈表上進(jìn)行遍歷，關(guān)鍵問題有二：一是如何找到訪問的第一個結(jié)點(diǎn)？

二是如何找到每個結(jié)點(diǎn)在中序序列中的后繼？

由于線索鏈表上保存的是“遍歷”過程中得到的前驅(qū)和后繼的信息，顯然，線索鏈表應(yīng)該在遍歷過程中建立，即在遍歷過程中改變二叉鏈表中結(jié)點(diǎn)的“空指針”以及相應(yīng)的“指針類型標(biāo)志”。

6.5.2以中序線索鏈表為存儲結(jié)構(gòu)的中序遍歷若結(jié)點(diǎn)沒有左子樹，

則令其左指針指向它的“前驅(qū)”并將左指針類型標(biāo)志改為“Thread”，若結(jié)點(diǎn)沒有右子樹，

則令它右指針指向它的“后繼”并將右指針類型標(biāo)志改為“Thread”。為了獲取"前驅(qū)"的信息，需要在遍歷過程中添加一個指向其前驅(qū)的指針pre。

由此建立線索鏈表的過程即為將遍歷過程中對結(jié)點(diǎn)進(jìn)行下列“訪問”操作(指針p指向當(dāng)前訪問的結(jié)點(diǎn)，pre

指向在它之前“剛剛”訪問過的結(jié)點(diǎn))：

if(!pre->Rchild){

pre->RTag=Thread;

pre->Rchild=p;

}

if(!p->Lchild){

p->LTag=Thread;

p->Lchild=pre;

}

pre=p;

6.5.3線索鏈表的生成

算法6.10

void

InThreading(BiThrTreep，BiThrTree&pre)

{//對p指向根結(jié)點(diǎn)的二叉樹進(jìn)行中序遍歷，遍歷過程中進(jìn)行//“中序線索

化”。若p所指結(jié)點(diǎn)的左指針為空，則將它改為“左線//索”，若pre所指結(jié)點(diǎn)的右指針為空，則將它改為“右線索”。指//針pre在遍歷

過程中始終指向p所指結(jié)點(diǎn)在中序序列中的前趨

if(p){

InThreading(p->Lchild,pre);

//對左子樹進(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);

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

}//if

}//InThreading算法6.11

void

InOrderThreading(BiThrTree

&Thead,BiThrTreeBT)

{//BT為指向二叉樹根結(jié)點(diǎn)的指針，由此二叉鏈表建立二叉樹

//的中序線索鏈表，Thead

指向線索鏈表中的頭結(jié)點(diǎn)。

BiThrTreepre;

if(!(Thead=new

BiThrNode))exit(1);//存儲分配失敗

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

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

Thead->Rchild=Thead;

//右指針回指

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

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

else

{

Thead->Lchild=BT;pre=Thead;

InThreading(BT,pre);

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

pre->Rchild=Thead;pre->RTag=Thead;

//對中序序列中最后一個結(jié)點(diǎn)進(jìn)行線索化

Thead->Rchild=pre;

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

}//else

}//InOrderThreading

參看flash6-5-26.6樹和森林的存儲表示

6.6.1樹的雙親表示法

結(jié)點(diǎn)中只設(shè)一個指向雙親的指針，并對無序樹不需要設(shè)子樹位置的標(biāo)志。所有結(jié)點(diǎn)存儲在一個地址連續(xù)的存儲空間中。

例如，下圖所示樹的雙親鏈表如下所示r=0n=110A-16C01B07D02E18F73H29G74I210K95J2樹的雙親鏈表存儲表示

constMAX_TREE_SIZE=100;

typedef

struct{

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

ElemTypedata;

intparent;

//雙親位置域

}

PTNode;

typedef

struct{

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

PTNode

nodes[MAX_TREE_SIZE];

intr,n;

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

}

PTree;

6.6.2樹的孩子表示法

讓每個結(jié)點(diǎn)的"子樹根"構(gòu)成一個線性表，以鏈表作它的存儲結(jié)構(gòu)，令其頭指針和結(jié)點(diǎn)的數(shù)據(jù)元素構(gòu)成一個結(jié)點(diǎn)，并將所有這樣的結(jié)點(diǎn)存放在一個地址連續(xù)的存儲空間里，所構(gòu)成的樹的存儲結(jié)構(gòu)稱為樹的孩子鏈表。如：下列圖示樹的孩子鏈表如下圖所示

樹的孩子鏈表存儲表示

typedef

struct

CTNode

{

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

intchild;

struct

CTNode*next;

}*ChildPtr;typedef

struct{

ElemTypedata;

//結(jié)點(diǎn)的數(shù)據(jù)元素

ChildPtr

firstchild;

//孩子鏈表頭指針

}

CTBox;

typedef

struct{

CTBox

nodes[MAX_TREE_SIZE];

intn,r;

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

}

CTree;

6.6.3樹和森林的孩子兄弟表示法

樹中每個結(jié)點(diǎn)都設(shè)有兩個指針，

firstchild

指向該結(jié)點(diǎn)的“第一個”子樹根結(jié)點(diǎn)，nextsibling

指向它的“下一個”兄弟結(jié)點(diǎn)。

森林可認(rèn)為各棵樹的根結(jié)點(diǎn)之間是一個“兄弟”關(guān)系因此無論樹和森林都可以用這樣的“二叉鏈表”表示。由于結(jié)點(diǎn)中的兩個指針指示的分別為"孩子"和"兄弟"的關(guān)系，故稱為"孩子-兄弟鏈表"。

6.6.4森林和二叉樹的轉(zhuǎn)換假設(shè)森林

F={T1,T2,…,Tn}，

其中第一棵樹T1由根結(jié)點(diǎn)ROOT(T1)和子樹森林{T11

,T12

,…,T1m

}構(gòu)成?？砂慈缦乱?guī)則轉(zhuǎn)換成一棵二叉樹

B=(LBT,Node(root),

RBT

)：

若森林F為空集，則二叉樹B為空樹；否則，由森林中第一棵樹的根結(jié)點(diǎn)

ROOT(T1

)復(fù)制得二叉樹的根Node(root)，由森林中第一棵樹的子樹森林

{T11

,T12

,…,T1m

}轉(zhuǎn)換得到二叉樹中的左子樹LBT，由森林中刪去第一棵樹之后由其余樹構(gòu)成的森林

{T2,T3,…,Tn}轉(zhuǎn)換得到二叉樹中的右子樹RBT。

反之，對于任意一棵二叉樹

B=(LBT,Node(root),RBT)，

可按如下規(guī)則轉(zhuǎn)換得到由n棵樹構(gòu)成的森林

F={T1,T2,…,Tn}

若二叉樹B為空樹,則與其對應(yīng)的森林F為空集；否則，由二叉樹的根結(jié)點(diǎn)Node(root)

復(fù)制得森林中第一棵樹的根結(jié)點(diǎn)ROOT()，由二叉樹中的左子樹LBT

轉(zhuǎn)換構(gòu)造森林中第一棵樹的子樹森林{T11

,T12

,…,T1m

}，由二叉樹中的右子樹RBT轉(zhuǎn)換構(gòu)造森林中其余樹構(gòu)成的森林{T2,T3,…,Tn}

。

由此，對樹和森林進(jìn)行的各種操作均可通過對"二叉樹"進(jìn)行相應(yīng)的操作來完成，但同時也必須注意，此時的"二叉樹"，其左、右子樹和根結(jié)點(diǎn)之間的關(guān)系不再是它的"左、右孩子"，而是左子樹是根的"孩子們"，右子樹是根的"兄弟們"。

6.7樹和森林的遍歷

6.7.1樹的遍歷對樹進(jìn)行遍歷可有兩條搜索路徑：

1.是從左到右

2.是按層次從上到下。樹的按層次遍歷類似于二叉樹的按層次遍歷，例如下圖樹按層次遍歷所得訪問的次序的為：ABCDEFGHIJK。類似于二叉樹，在這條搜索路徑上途徑根結(jié)點(diǎn)兩次，由對根的訪問時機(jī)不同可得下列兩個算法：

一、先根(次序)遍歷樹

若樹不空，則先訪問根結(jié)點(diǎn)，然后依次從左到右先根遍歷根的各棵子樹；

二、后根(次序)遍歷樹

若樹不空，則先依次從左到右后根遍歷根的各棵子樹，然后訪問根結(jié)點(diǎn)；

樹進(jìn)行從左到右遍歷的搜索路徑如下圖所示。進(jìn)行先根遍歷所得結(jié)點(diǎn)的訪問序列為：ABEHIJCDFGK進(jìn)行后根遍歷所得結(jié)點(diǎn)的訪問序列為：HIJEBCFKGDA

如圖