第六章樹和二叉樹第六章樹和二叉樹基本內容

二叉樹的概念、性質和存儲結構；二叉樹的遍歷和線索化算法；樹的定義、存儲結構、樹與二叉樹的轉換、樹的遍歷；哈夫曼樹的構造；學習要點

1．

掌握二叉樹的結構特性，

2．

熟悉二叉樹的各種存儲結構的特點及適用范圍；

3．

遍歷二叉樹是二叉樹各種操作的基礎。掌握各種遍歷策略的遞歸算法，能靈活運用遍歷算法實現二叉樹的其他操作；

4．

理解二叉樹線索化的實質是建立結點與其在相應序列中的前驅或后繼之間的直接聯系，掌握二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。

5．

熟悉樹的各種存儲結構及其特點，掌握樹和與二叉樹的轉換方法，掌握樹的遍歷方法；

6．

了解哈夫曼樹的特性，掌握構造哈夫曼樹和哈夫曼編碼的方法；第六章樹和二叉樹第六章樹和二叉樹6.1樹的有關概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應用6.5線索二叉樹6.6樹和森林6.7哈夫曼樹及應用第六章樹和二叉樹6.1

樹的有關概念1.樹的概念2.樹的應用3.樹的表示樹的有關術語5樹的基本操作6.1

樹的有關概念1．樹的概念樹結構（除了一個稱為根的結點外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。樹是n個結點的有限集合，在任一棵非空樹中：

（1）有且僅有一個稱為根的結點。

（2）其余結點可分為個互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。樹是遞歸結構，在樹的定義中又用到了樹的概念JIACBDHGFE6.1

樹的有關概念例：下面的圖是一棵樹T={A,B,C,D,E,F,G,H,I,J}A是根，其余結點可以劃分為3個互不相交的集合：

T1={B,E,F},T2={C,D},T3={D,H,I,J}這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。

例如對于T11，B是根，其余結點可以劃分為2個互不相交的集合：T11={E}，T12={F}，T11,T12是B的子樹。JIACBDHGFE6.1

樹的有關概念從邏輯結構看：

1）樹中只有根結點沒有前趨；

2）除根外，其余結點都有且僅一個前趨；3）樹的結點，可以有零個或多個后繼；

4）除根外的其他結點，都存在唯一條從根到該結點的路徑；5）樹是一種分枝結構JIACBDHGFE6.1

樹的有關概念2．樹的應用

1）樹可表示具有分枝結構關系的對象

例1．家族族譜設某家庭有10個成員A、B、C、D、E、F、G、H、I、J，他們之間的關系可下圖所示的樹表示：例2．單位行政機構的組織關系JIACBDHGFE6.1

樹的有關概念2）樹是常用的數據組織形式

有些應用中數據元素之間并不存在間分支結構關系，但是為了便于管理和使用數據，將它們用樹的形式來組織。

例3計算機的文件系統

不論是DOS文件系統還是window文件系統，所有的文件是用樹的形式來組織的。文件夾1文件夾n文件1文件2文件夾11文件夾12文件11文件12C6.1

樹的有關概念3）一些應用問題的求解過程可用樹結構的來描述

一些應用問題的求解過程可用樹結構的來描述，以幫助程序員寫出求解問題的程序或算法。

例4求集合的冪集

例如求集合A={1，2，3}的冪集顯然集合A中所有即為該樹的所有葉子，求集合A所有子集即為求該樹的所有葉子。{1}{}{1,2}{1}{2}{}{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}{}集合中每個元素對于子集來說，要么屬于該子集，要么不屬于該子集例如1不屬于{2，3}，左面的樹從空集開始，構造集合的子集考慮元素1考慮元素2考慮元素36.1

樹的有關概念3樹的表示

1）圖示表示

2）二元組表示

3）文氏圖表示

4）凹人表示法（類似書的目錄）

5）廣義表表示

6.1

樹的有關概念樹的基本術語樹的結點：包含一個數據元素及若干指向子樹的分支；

孩子結點：結點的子樹的根稱為該結點的孩子；

雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親；

兄弟結點：同一雙親的孩子結點；

堂兄結點：同一層上結點；

結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；

樹的高度：樹中最大的結點層

結點的度：結點子樹的個數

樹的度：樹中最大的結點度。

葉子結點：也叫終端結點，是度為0的結點；

分枝結點：度不為0的結點；

森林；互不相交的樹集合；

有序樹：子樹有序的樹，如：家族樹；

無序樹：不考慮子樹的順序；6.1

樹的有關概念5樹的基本操作樹的應用很廣，應用不同基本操作也不同。下面列舉了樹的一些基本操作：

（以DOS文元件系統為例解釋樹的基本操作）1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Paret(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());6．2二叉樹

樹是一種分枝結構的對象，在樹的概念中，對每一個結點孩子的個數沒有限制，因此樹的形態多種多樣，本章我們主要討論一種最簡單的樹——二叉樹。第六章樹和二叉樹6.2二叉樹一二叉樹的概念二二叉樹的性質三二叉樹的存儲結構6.2二叉樹一二叉樹的概念1二叉樹的定義二叉樹：或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹。說明1）二叉樹中每個結點最多有兩顆子樹；二叉樹每個結點度小于等于2;2）左、右子樹不能顛例——有序樹;3）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念;

A

F

G

E

D

C

B6.2二叉樹

A

F

G

E

D

C

B

(a)、(b)是不同的二叉樹，(a)的左子樹有四個結點，(b)的左子樹有兩個結點，(a)

A

G

E

D

B

C

F(b)6.2二叉樹

2．二叉樹的基本形態

φ6.2二叉樹3．應用舉例例1可以用二叉樹表示表達式

a+b*(c-d)-e/f

e

d

c

b

f

a

+

*

/

-

-6.2二叉樹例2雙人比賽的所有可能的結局

甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙開始開局連贏兩局或五局三勝6.2二叉樹例3樹能用二叉樹表示6.2二叉樹二二叉樹性質性質1在二叉樹的第i層上最多有2i-1個結點性質2深度為k的二叉樹最多有2k-1個結點性質3設二叉樹葉子結點數為n0，度為2的結點n2設，則n0=

n2+1

A

F

G

E

D

C

B6.2二叉樹兩種特殊的二叉樹滿二叉樹：如果深度為k的二叉樹，有2k-1個結點則稱為滿二叉樹；

A

G

F

E

D

C

B

A

C

BK=3的滿二叉樹K=2的滿二叉樹6.2二叉樹完全二叉樹：如果一顆二叉樹只有最下一層結點數可能未達到最大，并且最下層結點都集中在該層的最左端，則稱為完全二叉樹；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉樹(c)不是完全二叉樹

A

G

F

E

D

C

B6.2二叉樹下面是兩個關于完全二叉樹的性質性質4具有n個結點的完全二叉樹的深度為：log2n+1對完全二叉樹的結點編號：從上到下，每一層從左到右

A

F

E

D

C

B123456性質5：在完全二叉樹中編號為i的結點，1）若有左孩子，則左孩編號為2i；2）若有右孩子，則有孩子結點編號為2i+1；3）若有雙親，則雙親結點編號為i/2；6.2二叉樹三．二叉樹存貯結構

1二叉樹的順序結構完全二叉樹的順序結構用一組連續的內存單元，按編號順序依次存儲完全二叉樹的元素

順序結構圖示

1234567m-1

ABCDEF

A

F

E

D

C

B1234566.2二叉樹二叉樹的順序結構假想，我們補齊二叉樹所缺少的那些結點，對二叉樹結點編號。用這種方式對二叉樹結點編號，則在二叉樹中編號為i的結點，1）若有左孩子，則左孩編號為2i；2）若有右孩子，則有孩子結點編號為2i+1；3）若有雙親，則雙親結點編號為i/2；

A

F

G

E

D

C

B167245389

A

F

G

E

D

C

B6.2二叉樹167245389

A

F

G

E

D

C

B123456789m-1

AB

C

DE

F

G二叉樹的順序結構圖示將二叉樹原有的結點按編號存儲到內存單元“相應”的位置上6.2二叉樹2二叉鏈表二叉鏈表中每個結點至少包含三個域：數據域、左指針域、右指針域∧

D

A

B

∧C

∧∧

E

∧∧

F

∧

A

F

E

D

C

B3三叉鏈表三叉鏈表中每個結點至少包含四個域：數據域、雙親指針域、左指針域、右指針域二叉鏈表圖示6.2二叉樹4

靜態鏈表上面們二叉鏈表或三叉鏈表是用指針實現，是一種動態的鏈式存儲結構，鏈式存儲結構也可用一維數組來實現，用一維數組表示的二叉鏈表或三叉鏈表，稱為靜態鏈表

A

F

E

D

C

B孩子結點在數組中的位置0表示無左或右孩子靜態二叉鏈表A13C05B00E00F00D4

0123456Lchilddatarchild第六章樹和二叉樹6.3二叉樹的遍歷一.二叉樹的遍歷方法二.遍歷的遞歸算法6.3二叉樹的遍歷遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一次。訪問：含義很廣，可以是對結點的各種處理，如修改結點數據、輸出結點數據。遍歷是各種數據結構最基本的操作，許多其他的操作可以在遍歷基礎上實現。

對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事

二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？

6.3二叉樹的遍歷二叉樹的遍歷方法二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

D：訪問根結點

R：遍歷右子樹

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

約定先左后右,有三種遍歷方法：DLR、LDR、LRD

，分別稱為

先序遍歷、中序遍歷、后序遍歷

A

F

G

E

D

C

B6.3二叉樹的遍歷先序遍歷（DLR）

若二叉樹非空

（1）訪問根結點；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；

先序遍歷序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍歷右圖所示的二叉樹（1）訪問根結點A（2）先序遍歷左子樹：即按DLR的順序遍歷左子樹（3）先序遍歷右子樹：即按DLR的順序遍歷右子樹6.3二叉樹的遍歷中序遍歷（LDR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結點（3）中序遍歷右子樹

中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍歷右圖所示的二叉樹

（1）中序遍歷左子樹：即按LDR的順序遍歷左子樹

（2）訪問根結點A

（3）中序遍歷右子樹：即按LDR的順序遍歷右子樹6.3二叉樹的遍歷后序遍歷（LRD）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結點

后序遍歷序列：D,G,E,B,F,C,A例：后序遍歷右圖所示的二叉樹

（1）后序遍歷左子樹：即按LRD的順序遍歷左子樹

（2）后序遍歷右子樹：即按LRD的順序遍歷右子樹（3）訪問根結點A

A

F

G

E

D

C

B6.3二叉樹的遍歷

e

d

c

b

f

a

+

*

/

-

-

后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-

中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f

先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f例：先中序遍歷序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹6.3二叉樹的遍歷這實際上是先序遍歷的遞歸定義，我們知道遞歸定義包括兩個部分：1）基本項（也叫終止項）；2）遞歸項若二叉樹非空（1）訪問根結點；（2）先序遍歷左子樹（3）先序遍歷右子樹；先序遍歷遞歸定義遞歸項二.遍歷的遞歸算法

上面介紹了三種遍歷方法，顯然是用遞歸的方式給出的三種遍歷方法，以先序為例：先序遍歷（DLR）的定義：該定義隱含著若二叉樹為空，結束6.3二叉樹的遍歷上面先序遍歷的定義等價于：若二叉樹為空，結束——基本項（也叫終止項）若二叉樹非空——遞歸項（1）訪問根結點；（2）先序遍歷左子樹（3）先序遍歷右子樹；下面給出先序、中序、后序遍歷遞歸算法，為了增加算法的可讀性，這里對書上算法作了簡化，沒有考慮訪問結點出錯的情況（即我們假設調用函數visit()訪問結點總是成功的。6.3二叉樹的遍歷先序遍歷遞歸算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結點的函數。本算法先序//遍歷以為根結點指針的二叉樹，對每個數據元素調用函數Visit()

if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，訪問根結點；遍歷左子樹，遍歷右子樹

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse最簡單的Visit函數是：

StatusPrintElement(TElemTypee){//輸出元素e的值

printf(e);

returnOK;}

∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T6.3二叉樹的遍歷2中序遍歷遞歸算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結點的函數。本算法中序//遍歷以為根結點指針的二叉樹，對每個數據元素調用函數Visit()

if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，遍歷左子樹，訪問根結點，遍歷右子樹

InOrderTraverse(T->lchild,Visit);Visit(T->data)；

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse

你能寫出后序遍歷遞歸算法了吧6.3二叉樹的遍歷3后序遍歷遞歸算法

void

PostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結點的函數。本算法中序//遍歷以為根結點指針的二叉樹，對每個數據元素調用函數Visit()

if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問根結點

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);Visit(T->data)；

}//PostOrderTraverse

第六章樹和二叉樹6.4遍歷的應用

1.求二叉樹的葉子結點個數2.建立二叉鏈表

6.4遍歷的應用遍歷是二叉樹的基本操作：二叉樹許多操作可在遍歷過程中完成，如二叉樹線索化，就是在對二叉樹進行中序遍歷時加上線索的。本節再例子舉幾個二叉樹遍歷應用實例。6.4遍歷的應用例1編寫

求二叉樹的葉子結點個數的算法

輸入：二叉樹的二叉鏈表

結果：二叉樹的葉子結點個數基本思想：遍歷操作訪問二叉樹的每個結點，而且每個結點僅被訪問一次。所以可在二叉樹遍歷的過程中，統計葉子結點的個數?！?/p>

D

A

B

∧C

∧∧

E

∧∧

F

∧Tvoidleaf(BiTreeT){//采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結點//的個數。本算法在先序遍歷二叉樹的過程中，統計葉子結點的個數//第一次被調用時，n=0if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，在先序遍歷二叉樹的過程中，統計葉子結點的個數if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leafvoidleaf(BiTreeT){//采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結點,的個數。//本算法在先序遍歷二叉樹的過程中，統計葉子結點的個數第一次被調用時，n=0if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，在先序遍歷二叉樹的過程中，統計葉子結點的個數if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leaf6.4遍歷的應用

viodPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結點的函數。本算法先序//遍歷以為根結點指針的二叉樹，對每個數據元素調用函數Visit()

if(T){//若二叉樹為空，返回

//若二叉樹不為空，訪問根結點；遍歷左子樹，遍歷右子樹

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse比較先序遍歷算法和計算葉子結點算法，有什么相同和不同？結構類似函數名不同訪問結點時調用visit()訪問結點時統計葉子結點的個數6.4遍歷的應用例2為二叉樹建立二叉鏈表

輸入：二叉樹的先序序列

結果：二叉樹的二叉鏈表

遍歷操作訪問二叉樹的每個結點，而且每個結點僅被訪問一次。是否可在利用遍歷，建立二叉鏈表的所有結點并完成相應結點的鏈接？基本思想：輸入（在空子樹處添加*的二叉樹的）先序序列（設每個元素是一個字符//）按先序編歷的順序，建立二叉鏈表的所有結點并完成相應結點的鏈接6.4遍歷的應用∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T先序序列：ABDFCE（在空子樹處添加*的二叉樹的）先序序列：ABD*F**CE***

A

F

E

D

C

B*******

A

F

E

D

C

B6.4遍歷的應用StatusCreateBiTree(BiTree&T){//輸入（在空子樹處添加*的二叉樹的）先序序列（設每個元素是一個字//符）按先序編歷的順序，建立二叉鏈表，并將該二叉鏈表根結點指針//賦給T

scanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’則T=NULL返回else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）結點

CreateBiTree(T->lchild);//構造左子樹鏈表，并將左子樹根結點指針//賦給（根）結點的左孩子域CreateBiTree(T->rchild);//構造右子樹鏈表，并將右子樹根結點指針//賦給（根）結點的右孩子域}

returnOK;}//CreateBiTree小結

小結1二叉樹：或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹；2二叉樹即可以用順序結構存儲，也可用鏈式結構存儲；3遍歷：按某種搜索路徑訪問二叉樹的每個結點，每個結點僅被訪問一次。二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹，本課程介紹了三種遍歷算法：先序遍歷、中序遍歷、后序遍歷；習題十1P386.12對P396.15給出的二叉樹求出以下的遍歷序列：（1）先序序列（2）中序序列（3）后序序列3編寫

求二叉樹的分枝結點個數的算法（用二叉鏈表存貯二叉樹習題取自數據結構題集C語言版嚴尉敏等編清華大學出版社第六章習題第六章樹和二叉樹6.4線索二叉樹1.線索二叉樹的概念2線索鏈表3.線索二叉樹的遍歷6.5線索二叉樹1線索二叉樹

遍歷是二叉樹最基本最常用的操作。

1）對二叉樹所有結點做某種處理可在遍歷過程中實現；

2）檢索（查找）二叉樹某個結點，可通過遍歷實現；

與線性表相比，對二叉樹的遍歷存在如下問題：1）遍歷算法要復雜的多，費時的多；2）為檢索或查找二叉樹中某結點在某種遍歷下的后繼，必須從根開始遍歷，直到找到該結點及后繼；

如果能將二叉樹線性化，就可以減化遍歷算法，提高遍歷速度。如何將二叉樹線性化？

以中序遍歷為例，我們看到通過遍歷可以得到二叉樹結點的中序序列。若能將中序序列中每個結點前趨、后繼信息保存起來，以后再遍歷二叉樹時就可以根據所保存的結點前趨、后繼信息對二叉樹進行遍歷。

加上結點前趨后繼信息（結索）的二叉樹稱為線索二叉樹6.5線索二叉樹中序遍歷序列：D,B,H,E,A,F,C,G在中序序列中，D的后繼是B，H的前趨是B，后繼是E…

A

G

H

E

D

C

B

F加上結點前趨后繼信息（結索）的二叉樹稱為線索二叉樹線索二叉樹孩子指針前趨指針后繼指針6.5線索二叉樹2．線索鏈表

線索二叉樹的存貯方法：

1）

為每個結點增加二個指針域。

缺點：要點用較多的內存空間。每個n個結點的二叉鏈表，有n+1個空指針域，故可利用這些的空指針域存放結點的前趨和后繼指針，以這種結點的構成二叉鏈表稱為線索鏈表T∧

D

A

B

C

∧

F

∧∧

H∧

E

∧∧

G

∧6.5線索二叉樹

線索鏈表的類型說明typedefenum{link,thread}PointerTag;//link=0,thread=1typedefstructBiThrNode{

TElemTypedata;

StructBiThrNode*lchild,*rchild;//左右指針域

PointerTagLtag,Rtag;//左右標志域，標志域為0時，表示左右指針//域存儲的是左右孩子的指針，標志域為1時，表示左右指針域存儲的是//前趨后繼結點的指針}BiThrNode，*BiThrTreeLchildlTagdataRTagrchildF11E01G10D01A00B00H11C006.5線索二叉樹線索鏈表圖示線索二叉樹

A

G

H

E

D

C

B

F孩子指針前趨指針后繼指針

6.5線索二叉樹為簡化線索鏈表的遍歷算法，仿照線性鏈表，為線索鏈表加上一頭結點

約定：

頭結點的lchild域：存放線索鏈表的根結點指針；

頭結點的rchild域:中序序列最后一個結點的指針；

中序序列第一結點lchild域指向頭結點;

中序序列最后一個結點的rchild域指向頭結點;F11E01G11D11A00B00H11C0001頭結點6.5線索二叉樹如圖標出的中序二叉樹結點的順序，可看出1）中序序列的第一結點，是二叉樹的最左下結點；2）若p所指結點的右孩子域為線索，則p的右孩子結點即為后繼結點；3）若p所指結點的右孩子域為孩子指針，則p的后繼結點為其右子樹的最左下結點；F11E01G11D11A00B00H11C0001頭結點①②③

中序遍歷序列：D,B,H,E,A,F,C,G6.5線索二叉樹3．線索二叉樹的遍歷

在二叉樹上加上結點前趨、后繼線索后，可利用線索對二叉樹進行遍歷。

下面是線索鏈表的遍歷算法。

基本步驟：1）p=T->lchild;p指向線索鏈表的根結點；2）若線索鏈表非空，循環：（a）循環，順著p左孩子指針找到最左下結點；訪問之；（b）若p所指結點的右孩子域為線索，p的右孩子結點即為后繼結點循環：p=p->rchild；并訪問p所指結點；（在此循環中，順著后繼線索訪問二叉樹中的結點）（c）一旦線索“中斷”，p所指結點的右孩子域為右孩子指針，p=p->rchild，使p指向右孩子結點；3）返回OK；結束6.5線索二叉樹線索鏈表的遍歷算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){//T指向頭結點，頭結點的左鏈lchild指向根結點，//中序遍歷二叉線索樹T算法，對每個數據元素調用函數Visit。P=T->lchild;//p指向根結點While(p!=T){//空樹或遍歷結束時，p==TWhile(p->Ltag==Link)p=p->lchild;//找到最左下結點；訪問之Visit(p->data))while(p->Rtag==Thread&&p->rchild!=T){//若p所指結點的右孩子域為線索//且不是最后一個結點p=p->rchild;Visit(p->data);//訪問后繼結點}p=p->rchild;}returnOK;}//InOrderTraverse_Thr為了增加算法的可讀性，這里對書上算法作了簡化，沒有考慮訪問結點出錯的情況（即我們假設調用函數visit()訪問結點總是成功的。第六章樹和二叉樹6.6樹和森林一.樹的存儲結構二.樹和二叉樹的轉換三.

樹的遍歷四.森林

6.6樹和森林

一．樹的存貯結構在樹中，每個結點即可能有孩子也可能有雙親，所以既可以通過保存每個結點的孩子結點位置來表示結點之間的結構關系，也雙親表示法通過通過保存每個結點的雙親結點位置來表示結點之間的結構關系。

1雙親表示法雙親表示法：通過保存每個結點的雙親結點的位置，表示樹中結點之間的結構關系。用一組連續的內存單元存儲數的結點，每個結點包含兩個域：一個數據域，一個“指針域”，用于指示其雙親結點在數組中的位置6.6樹和森林雙親表示類型定義

#defineMAX_TREEE_SIZE100typedefstructPTNode{

TelemTypedata;

intparent;//雙親位置域}PTNode;typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

Intn;//結點數}Ptree;IACBDHGFE雙親表示圖示A-1B0C0D0E1F1G2H3I3012345678.dataparent9T.nodesT.n結點數雙親結點在數組中的位置-1表示無雙親

6.6樹和森林2、孩子表示法孩子表示法：通過保存每個結點的孩子結點的位置，表示樹中結點之間的結構關系。

與雙親表示法相反，孩子表示法適合實現涉及孩子的操作。還可以將雙親表示與孩子表示法結合：帶雙親的孩子鏈表。

方法1：多重鏈表（類似二叉鏈表）

兩種方式：定長結點不定長結點定長結點

優點結點結構一致，便于實現樹的操作。缺點是浪費一些內存。

不定長結點

優點：節省內存

缺點：不定長會使一些操作實現復雜一些6.6樹和森林方式II：孩子鏈表（可以不看）孩子鏈表：對樹的每個結點用線性鏈表存貯它的孩子結點樹的孩子鏈表類型定義typedefstructCTNode{//孩子結點

intchild;

str