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

ADTTree{

數據對象：D是具有相同特性的數據元素的集合。

數據關系：

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

若D中僅含一個數據元素，則關系R為空集；

否則R={H}，

(1)在D中存在唯一的稱為根的數據元素root，它在關系H下無前驅；

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

基本操作：

{結構初始化}

InitTree(&T);

操作結果：構造空樹T。

CreateTree(&T,definition);

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

操作結果：按definition構造樹T。

{銷毀結構}

DestroyTree(&T);

初始條件：樹T存在。

操作結果：銷毀樹T。{引用型操作}

TreeEmpty(T);

初始條件：樹T存在。

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

TreeDepth(T);

初始條件：樹T存在。

操作結果：返回T的深度。

Root(T);

初始條件：樹T存在。

操作結果：返回T的根。

Value(T,cur_e);

初始條件：樹T存在，cur_e

是T中某個結點。

操作結果：返回cur_e

的值。

Parent(T,cur_e);

初始條件：樹T存在，cur_e

是T中某個結點。

操作結果：若cur_e

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

初始條件：樹T存在，cur_e

是T中某個結點。

操作結果：若cur_e

是T的非葉子結點，則返回它的最左孩子，否則返回"空"。

RightSibling(T,cur_e);

初始條件：樹T存在，cur_e

是T中某個結點。

操作結果：若cur_e

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

TraverseTree(T,visit());

初始條件：樹T存在，visit是對結點操作的應用函數。

操作結果：按某種次序對T的每個結點調用函數

visit()一次且至多一次。

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

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e

是T中某個結點。

操作結果：結點cur_e

賦值為value。

ClearTree(&T);

初始條件：樹T存在。

操作結果：將樹T清為空樹。

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

初始條件：樹T存在，p指向T中某個結點，

1≤i≤p所指結點的度＋1，空樹c與T不相交。

操作結果：插入c為T中p所指結點的第i棵子樹。

DeleteChild(&T,&p,i);

初始條件：樹T存在，p指向T中某個結點，

1≤i≤p指結點的度。操作結果：刪除T中p所指結點的第i棵子樹。

}ADTTree

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

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

則可定義樹是一個二元組

Tree=(root,F)

其中，root

是數據元素，稱作樹的根，

F

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

其中Ti=(ri,Fi)

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

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

樹和線性結構作如下對照：線性結構樹結構存在唯一的沒有前驅

的"首元素"存在唯一的沒有前驅的

"根結點"

存在唯一的沒有后繼

的"尾元素"

存在多個沒有后繼的

"葉子"

其余元素均存在唯一

的"前驅元素"和唯一

的"后繼元素"

其余結點均存在唯一的

"前驅(雙親)結點"和多

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

二叉樹的抽象數據類型定義如下:ADTBinaryTree{

數據對象：D是具有相同特性的數據元素的集合。

數據關系：

若D為空集，稱BinaryTree

為空二叉樹；

否則關系R={H}：

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

root，它在關系H下無前驅；

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

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

基本操作：

{結構初始化}

InitBiTree(&T);

操作結果：構造空二叉樹T。

CreateBiTree(&T,definition);

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

操作結果：按definition構造二叉樹T。

{銷毀結構}

DestroyBiTree(&T);

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

操作結果：銷毀二叉樹T。

{引用型操作}

BiTreeEmpty(T);

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

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

BiTreeDepth(T);

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

操作結果：返回T的深度。

Root(T);

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

操作結果：返回T的根。

Value(T,e);

初始條件：二叉樹T存在，e是T中某個結點。

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

初始條件：二叉樹T存在，e是T中某個結點。

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

初始條件：二叉樹T存在，e是T中某個結點。

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

初始條件：二叉樹T存在，e是T中某個結點。

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

初始條件：二叉樹T存在，e是T中某個結點。

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

初始條件：二叉樹T存在，e是T的結點。

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

PreOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：先序遍歷T，對每個結點調用函數visit一次且僅一次。一旦visit()失敗，則操作失敗。InOrderTraverse(T,vsit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：中序遍歷T，對每個結點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。

PostOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：后序遍歷T，對每個結點調用函數visit一次且僅一次。一旦visit()失敗，則操作失敗。LevelOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對結點操作的應用函數。

操作結果：層序遍歷T，對每個結點調用函數visit一次且僅一次。一旦visit()失敗，則操作失敗。

{加工型操作}

ClearBiTree(&T);

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

操作結果：將二叉樹T清為空樹。

Assign(&T,&e,value);

初始條件：二叉樹T存在，e是T中某個結點。

操作結果：結點e賦值為value。

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

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

操作結果：根據LR為0或1，插入c為T中p所指結點的左或右子樹。p所指結點原有左或右子樹成為c的右子樹。

DeleteChild(&T,p,LR);

初始條件：二叉樹T存在，p指向T中某個結點，LR為0或1。

操作結果：根據LR為0或1，刪除T中p所指結點的左或右子樹。

}ADTBinaryTree

6.2.2二叉樹的幾個特性

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

個結點(i≥1)。

利用歸納法容易證得此結論。證明：

歸納基：i=1

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

個結點。歸納證明：由歸納假設“第i-1層上至多有

2i-2個結點”，又二叉樹的每個結點的度至多為2，則第

i層上的最大結點數為第

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

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

n0

=n2

+1證明：

由于二叉樹中只有三種結點，假設n1為二叉樹T中度為1的結點數，則二叉樹中結點總數為

n=n0+n1+n2

①

再看二叉樹中的分支數目。除了根結點外，其余結點都有一個分支進入，假設B為分支數，則

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

即n=n1+2n2+1

②

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

n0=n2+1

有兩種特殊形態的二叉樹滿二叉樹:若二叉樹中所有的分支結點的度數都為2，且葉子結點都在同一層次上，則稱這類二叉樹為滿二叉樹。

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

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

四、具有n個結點的完全二叉樹的深度為log2n+1。

假設該完全二叉樹的深度為k，則根據特性二和完全二叉樹的定義

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

或2k-1≤n<2k

對后者取對數便得k-1≤log2n<k

因為k是整數，所以k=[log2n]+1

。

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

(1)

如果i=1，則編號為i的結點是二叉樹的根，無雙親；如果

i>1，則其雙親結點parent(i)

的編號是

i/2

。

(2)

如果

2i>n，則編號為i

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

的編號是2i

。

(3)

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

的結點無右孩子；否則其右孩子結點rChild(i)

的編號是結點

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

用一組地址連續的存儲單元存儲二叉樹中的數據元素。二叉樹的順序存儲結構的定義如下：

constMAXSIZE=100;//定二叉樹中結點數的max為100

typedef

struct

{

ElemType

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

int

nodeNum;

//二叉樹中結點數

}SqBiTree;

//二叉樹的順序存儲結構6.3.1順序存儲結構

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

0123456789abcdefghij根據二叉樹的特性五，可推出順序存儲結構中“雙親”和“孩子”的關系：

假設bt.data[i]

是完全二叉樹上的一個結點，若

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

是它的左孩子，否則它的左子樹為空樹；若2i+2<bt.nodeNum，則bt.data[2i+2]是它的右孩子，否則它的右子樹為空樹。對于一般二叉樹，應將其每個結點與完全二叉樹上的結點相對照，存在一維數組的相應分量中，不存在的結點用0表示01234567891011121314ABC0E0F00G000006.3.2鏈式存儲結構

一、二叉鏈表二叉鏈表的結點結構：lchilddatarchild二叉樹的二叉鏈表存儲表示

typedef

struct

BiTNode

{

ElemTypedata;

struct

BiTNode*Lchild,*Rchild;

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

ab二、三叉鏈表的結點結構：parentlchilddatachild二叉樹的三叉鏈表存儲表示

typedef

struct

TriTNode

{

ElemTypedata;

struct

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

struct

BiTNode*parent;

//雙親指針

}*TriTree;

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

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

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

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

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

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

否則

(1)訪問根結點；

(2)先序遍歷左子樹；

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

否則

(1)中序遍歷左子樹；

(2)訪問根結點；

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

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

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

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

{

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

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

visit(T);

//通過函數指針*visit訪問根結點

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

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

}//if

}//Preorder根據遍歷遞歸算法遞歸工作棧的狀態變化狀況可以直接寫出相應的非遞歸算法算法6.2

void

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

{

//采用二叉鏈表存儲結構，visit是對數據元素操作的//應用函數。中序遍歷二叉樹T的非遞歸算法，對每一//個數據元素調用

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廣度優先遍歷二叉樹（按層次遍歷二叉樹）過程：先訪問第1層，然后從左到右依次訪問第2層兩個節點，依此類推，當第i層訪問完以后，在從左到右訪問第i+1層的各個節點。這里需要使用一個隊列作為輔助的存儲結構

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

6.5.1二叉樹的線索鏈表

先序序列為：

ABDEGHCFIJ

中序序列為：

DBGEHACIJF

后序序列為：

DGHEBJIFCA

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

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

typedef

enum

PointerType{Link=0,Thread=1};

//

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

typedef

struct

BiThrNode{

ElemTypedata;

struct

BiThrNode

*Lchild,*Rchild;

//

左右指針

PointerType

LTag,RTag;

//

左右指針類型標志

}

*BiThrTree;

若結點的左指針類型標志為“Link”，則Lchild

指向它的左子樹根結點，否則指向它的“前驅”；

若結點的右指針類型標志為“Link”，則Rchild

指向它的右子樹根結點，否則指向它的"后繼"。

圖二叉樹的中序線索鏈表如下所示（圖中所有實線表示指針，虛線表示線索）

從圖中可見，在線索鏈表中添加了一個"頭結點"，頭結點的左指針指向二叉樹的根結點，其右線索指向中序序列中的最后一個結點，中序序列中的第一個結點的左線索和中序序列中的最后一個結點的右線索均指向頭結點。這就好比將二叉樹中所有結點置于一個雙向循環鏈表之中，即可以從頭結點出發，依照中序遍歷的規則對二叉樹中的結點依次進行"順序"（和中序序列相同的次序）訪問，或"逆序"（和中序序列相反的次序）訪問。

6.5.2以中序線索鏈表為存儲結構的中序遍歷如何在中序線索鏈表上進行遍歷，關鍵問題有二：一是如何找到訪問的第一個結點？

二是如何找到每個結點在中序序列中的后繼？

由于線索鏈表上保存的是“遍歷”過程中得到的前驅和后繼的信息，顯然，線索鏈表應該在遍歷過程中建立，即在遍歷過程中改變二叉鏈表中結點的“空指針”以及相應的“指針類型標志”。

6.5.2以中序線索鏈表為存儲結構的中序遍歷若結點沒有左子樹，

則令其左指針指向它的“前驅”并將左指針類型標志改為“Thread”，若結點沒有右子樹，

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

由此建立線索鏈表的過程即為將遍歷過程中對結點進行下列“訪問”操作(指針p指向當前訪問的結點，pre

指向在它之前“剛剛”訪問過的結點)：

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指向根結點的二叉樹進行中序遍歷，遍歷過程中進行//“中序線索

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

過程中始終指向p所指結點在中序序列中的前趨

if(p){

InThreading(p->Lchild,pre);

//對左子樹進行線索化

if(!p->Lchild)

{p->LTag=Thread;p->Lchild=pre;}

//建前驅線索

if(!pre->Rchild)

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

pre=p;

//保持pre指向p的前驅

InThreading(p->Rchild,pre);

//對右子樹進行線索化

}//if

}//InThreading算法6.11

void

InOrderThreading(BiThrTree

&Thead,BiThrTreeBT)

{//BT為指向二叉樹根結點的指針，由此二叉鏈表建立二叉樹

//的中序線索鏈表，Thead

指向線索鏈表中的頭結點。

BiThrTreepre;

if(!(Thead=new

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

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

//建頭結點

Thead->Rchild=Thead;

//右指針回指

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

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

else

{

Thead->Lchild=BT;pre=Thead;

InThreading(BT,pre);

//中序遍歷進行中序線索化

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

//對中序序列中最后一個結點進行線索化

Thead->Rchild=pre;

//建非空樹的頭結點的"右線索"

}//else

}//InOrderThreading

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

6.6.1樹的雙親表示法

結點中只設一個指向雙親的指針，并對無序樹不需要設子樹位置的標志。所有結點存儲在一個地址連續的存儲空間中。

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

constMAX_TREE_SIZE=100;

typedef

struct{

//結點結構

ElemTypedata;

intparent;

//雙親位置域

}

PTNode;

typedef

struct{

//樹結構

PTNode

nodes[MAX_TREE_SIZE];

intr,n;

//根的位置和結點數

}

PTree;

6.6.2樹的孩子表示法

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

樹的孩子鏈表存儲表示

typedef

struct

CTNode

{

//孩子結點

intchild;

struct

CTNode*next;

}*ChildPtr;typedef

struct{

ElemTypedata;

//結點的數據元素

ChildPtr

firstchild;

//孩子鏈表頭指針

}

CTBox;

typedef

struct{

CTBox

nodes[MAX_TREE_SIZE];

intn,r;

//結點數和根結點的位置

}

CTree;

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

樹中每個結點都設有兩個指針，

firstchild

指向該結點的“第一個”子樹根結點，nextsibling

指向它的“下一個”兄弟結點。

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

6.6.4森林和二叉樹的轉換假設森林

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

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

,T12

,…,T1m

}構成?？砂慈缦乱巹t轉換成一棵二叉樹

B=(LBT,Node(root),

RBT

)：

若森林F為空集，則二叉樹B為空樹；否則，由森林中第一棵樹的根結點

ROOT(T1

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

{T11

,T12

,…,T1m

}轉換得到二叉樹中的左子樹LBT，由森林中刪去第一棵樹之后由其余樹構成的森林

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

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

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

可按如下規則轉換得到由n棵樹構成的森林

F={T1,T2,…,Tn}

若二叉樹B為空樹,則與其對應的森林F為空集；否則，由二叉樹的根結點Node(root)

復制得森林中第一棵樹的根結點ROOT()，由二叉樹中的左子樹LBT

轉換構造森林中第一棵樹的子樹森林{T11

,T12

,…,T1m

}，由二叉樹中的右子樹RBT轉換構造森林中其余樹構成的森林{T2,T3,…,Tn}

。

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

6.7樹和森林的遍歷

6.7.1樹的遍歷對樹進行遍歷可有兩條搜索路徑：

1.是從左到右

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

一、先根(次序)遍歷樹

若樹不空，則先訪問根結點，然后依次從左到右先根遍歷根的各棵子樹；

二、后根(次序)遍歷樹

若樹不空，則先依次從左到右后根遍歷根的各棵子樹，然后訪問根結點；

樹進行從左到右遍歷的搜索路徑如下圖所示。進行先根遍歷所得結點的訪問序列為：ABEHIJCDFGK進行后根遍歷所得結點的訪問序列為：HIJEBCFKGDA

如圖