第六樹和二叉樹

會計學(xué)1第六樹和二叉樹思考

你見過家族譜系圖嗎？試以圖形表示從你的祖父起的家族成員關(guān)系。侄兒伯父父親叔父堂兄堂姐自己堂弟祖父用關(guān)系表示的家族譜系圖<祖父，伯父>，<祖父，父親>，

<祖父，叔父>，<伯父，堂兄>，

<伯父，堂姐>，<父親，自己>，

<叔父，堂弟>，<堂兄，侄兒>第1頁/共110頁

樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。第2頁/共110頁IndexRootChildernnode1中國河南2中國北京3中國廣東IndexRootChildernnode1北京通州2河南鄭州3河南開封4廣東深圳5廣東廣州IndexRootChildernnode1深圳寶安區(qū)2深圳沙田區(qū)3鄭州金水區(qū)4鄭州二七區(qū)中國河南北京廣東開封鄭州深圳廣州金水二七寶安沙田第3頁/共110頁樹的抽象數(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第4頁/共110頁在這13個數(shù)據(jù)元素之間存在下列關(guān)系：R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,

<D,H>,<D,I>,<D,J>,<F,K>,<F,L>,<J,M>}第5頁/共110頁樹結(jié)構(gòu)的表現(xiàn)形式嵌套集合表示法凹入表表示法：類似于目錄形式廣義表表示法：（A,(B,(C),(D),(E)),(F,(G),(H))）圖形表示法：ACDEFBGH第6頁/共110頁基本術(shù)語

分支：根和子樹根之間的連線

結(jié)點：一個數(shù)據(jù)元素及若干指向其子樹的分支

結(jié)點的度：結(jié)點擁有的子樹個數(shù)

葉子(終端結(jié)點)：度為0的結(jié)點

非終端結(jié)點(分支結(jié)點)：度不為0的結(jié)點

樹的度：樹內(nèi)各結(jié)點度的最大值

孩子：指結(jié)點的子樹的根,相應(yīng)的,該結(jié)點稱為孩子的雙親

兄弟：同一雙親的孩子之間互稱兄弟

祖先：一個結(jié)點的祖先指從根到該結(jié)點所經(jīng)分支上的所有結(jié)點

AIDBEHCFGKJ第7頁/共110頁子孫：以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫結(jié)點的層次：令根為第一層，根的孩子為第二層。若某結(jié)點 處在第l層，其子樹的根就在l+1層。堂兄弟：雙親在同一層的結(jié)點互稱堂兄弟樹的深度：指樹中結(jié)點的最大層次有序樹：樹中結(jié)點的各子樹從左至右有序（即不能互換）， 否則稱為無序樹森林：指m(m≥0)棵互不相交的樹的集合AIDBEHCFGKJ第8頁/共110頁ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先第9頁/共110頁基本操作：

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

InitTree(&T); //構(gòu)造空樹T

CreateTree(&T,definition); //按definition構(gòu)造樹T

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

DestroyTree(&T); //銷毀樹T

第10頁/共110頁{引用型操作}TreeEmpty(T); //若T為空樹，則返回TRUE，否則返回FALSE

TreeDepth(T);//返回T的深度

Root(T);//返回T的根

Value(T,cur_e);//返回cur_e的值

Parent(T,cur_e);//若cur_e是T的非根結(jié)點，則返回它的雙親，否則返回"空"。

LeftChild(T,cur_e);//若cur_e是T的非葉子結(jié)點，則返回它的最左孩子，否則返回"空"

RightSibling(T,cur_e);//若cur_e有右兄弟，則返回它的右兄弟，否則返回"空"

TraverseTree(T,visit());//按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit()一次且至多一次。一旦

//visit()失敗，則操作失敗。 第11頁/共110頁{加工型操作}

Assign(T,cur_e,value); //結(jié)點cur_e賦值為value ClearTree(&T);

//將樹T清為空樹

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

//插入c為T中p所指結(jié)點的第i棵子樹

DeleteChild(&T,&p,i); //刪除T中p所指結(jié)點的第i棵子樹}ADTTree

第12頁/共110頁線性結(jié)構(gòu)樹結(jié)構(gòu)存在唯一的沒有前驅(qū)的"首元素"存在唯一的沒有前驅(qū)的"根結(jié)點"存在唯一的沒有后繼的"尾元素"存在多個沒有后繼的"葉子"其余元素均存在唯一的"前驅(qū)元素"和唯一的"后繼元素"其余結(jié)點均存在唯一的"前驅(qū)(雙親)結(jié)點"和多個"后繼(孩子)結(jié)點"線性結(jié)構(gòu)和樹結(jié)構(gòu)中數(shù)據(jù)元素之間關(guān)系對比表第13頁/共110頁二叉樹的類型定義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é)點xl,它是root的”左后繼”,如果右子樹R

不空,則必存在一個根結(jié)點xr,它是root的”右后繼”第14頁/共110頁第15頁/共110頁基本操作P：{結(jié)構(gòu)初始化} InitBiTree(&T);//構(gòu)造空二叉樹T CreateBiTree(&T,definition); //按definition構(gòu)造二叉樹T{銷毀結(jié)構(gòu)} DestroyBiTree(&T);//銷毀二叉樹T

第16頁/共110頁{引用型操作} BiTreeEmpty(T); BiTreeDepth(T); Root(T); Value(T,e); Parent(T,e); LeftChild(T,e);

RightChild(T,e); LeftSibling(T,e); RightSibling(T,e); PreOrderTraverse(T,visit()); //先序遍歷T，對每個結(jié)點調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗

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

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

LevelOrderTraverse(T,visit()); //層序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗第17頁/共110頁{加工型操作} ClearBiTree(&T);

//將二叉樹T清為空樹

Assign(&T,&e,value);

//結(jié)點e賦值為value InsertChild(&T,p,LR,c);

//根據(jù)LR為0或1，插入c為T中p所指結(jié)點的左或右

//子樹。p所指結(jié)點原有左或右子樹成為c的右子樹

DeleteChild(&T,p,LR); //根據(jù)LR為0或1，刪除T中p所指結(jié)點的左或右子樹}ADTBinaryTree第18頁/共110頁二叉樹和樹是兩種不同的樹型結(jié)構(gòu)，二叉樹不等同于度為2的有序樹。

Why?第19頁/共110頁具有三個結(jié)點的樹的棵數(shù)：ACBCBA具有三個結(jié)點的二叉樹的棵數(shù)：ACBCBACBACBACBA第20頁/共110頁二叉樹的五種形態(tài)空樹，結(jié)點數(shù)為0單節(jié)點二叉樹，只有一個結(jié)點左子樹為空，右子樹不空右子樹為空，左子樹不空左右子樹均不空第21頁/共110頁二叉樹的幾個特性一、在二叉樹的第i層上至多有2i-1

個結(jié)點(i≥1)二、深度為k的二叉樹中至多含有2k-1個結(jié)點，

(k≥1)。三、對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為

n0，度為2的結(jié)點數(shù)為n2，則：

n0=n2+1

第22頁/共110頁證明：

由于二叉樹中只有三種結(jié)點，假設(shè)n1為二叉樹T

中度為1的結(jié)點數(shù)，則二叉樹中結(jié)點總數(shù)為

n=n0+n1+n2

①

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

n=B+1。從另一角度看，這些分支是由度為1或2

的結(jié)點射出的，所以又有

B=n1+2n2

即n=n1+2n2+1②

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

n0=n2+1第23頁/共110頁思考：若一棵樹的度為4，其中，度為1的結(jié)點有4個，度為2的結(jié)點有2個，度為3的結(jié)點有1個，度為4的結(jié)點有1個，則該樹中葉子有多少個？第24頁/共110頁兩種特殊形式的二叉樹若二叉樹中所有的分支結(jié)點的度數(shù)都為2，且葉子結(jié)點都在同一層次上，則稱這類二叉樹為滿二叉樹。

對滿二叉樹從上到下從左到右進行從1開始的編號，則任意一棵二叉樹都可以和同深度的滿二叉樹對比

第25頁/共110頁假如一棵包含n個結(jié)點的二叉樹中每個結(jié)點都可以和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)，則稱這類二叉樹為完全二叉樹。在滿二叉樹的最下層從右到左連續(xù)地刪除若干個結(jié)點所得到的二叉樹。顯然一棵深度為h的完全二叉樹中，前h-1層中的結(jié)點都是“滿”的。滿二叉樹本身也是完全二叉樹。第26頁/共110頁1231145891213671014151231145891267101234567123456第27頁/共110頁二叉樹的幾個特性四、具有n個結(jié)點的完全二叉樹的深度為五、如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序從1

開始編號，則對任一編號為i的結(jié)點(1≤i≤n)，有：

(1)如果i=1，則編號為i的結(jié)點是二叉樹的根；如果

i>1，則其雙親結(jié)點parent(i)的編號是

(2)如果2i>n，則編號為i的結(jié)點無左孩子（編號為i的結(jié)點為葉子結(jié)點）；否則其左孩子結(jié)點lChild(i)的編號是2i。

(3)如果2i+1>n，則編號為i的結(jié)點無右孩子；否則其右孩子結(jié)點rChild(i)的編號是結(jié)點2i+1。第28頁/共110頁二叉樹的存儲結(jié)構(gòu)----順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素

二叉樹的順序存儲結(jié)構(gòu)的定義如下：

constMAXSIZE=100;

//定義二叉樹中結(jié)點數(shù)的最大值為100

typedefstruct

{

ElemType*data;

//存儲空間基址(初始化時分配空間)

intnodeNum;

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

}SqBiTree;

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

SqBiTreebt;第29頁/共110頁為了能在存儲結(jié)構(gòu)中反映出結(jié)點之間的邏輯關(guān)系，必須將二叉樹中結(jié)點依照一定規(guī)律安排在這組存儲單元中。對于完全二叉樹，只要從根起按層序存儲即可。將完全二叉樹上編號為i的結(jié)點元素存儲在一維數(shù)組中下標(biāo)為i-1的分量中

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

假設(shè)bt.data[i]是完全二叉樹上的一個結(jié)點若2i+1<bt.nodeNum，則bt.data[2i+1]是它的左孩子，否則它的左子樹為空樹；若2i+2<bt.nodeNum，則bt.data[2i+2]是它的右孩子，否則它的右子樹為空樹。0123456789abcdefghij第31頁/共110頁對于一般的二叉樹，可對照完全二叉樹的編號進行相應(yīng)的存儲，但在沒有結(jié)點的分量中需填充空白字符。為此，需要依據(jù)實際結(jié)點數(shù)來分配存儲空間，即采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。abcdefgabcde0000fg012345678910第32頁/共110頁二叉鏈表二叉鏈表的結(jié)點結(jié)構(gòu)：

LchilddataRchild二叉樹的二叉鏈表存儲表示

typedefstructBiTNode{

ElemTypedata;

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

}BiTNode,*BiTree;

第33頁/共110頁整個二叉樹可用一個指向根結(jié)點的指針表示。第34頁/共110頁BiTreecreate_tree(){ BiTreeq[100]; BiTNode*s,*root=NULL; charch; intrear=0,front=1; ch=getchar(); while(ch!='#') { if(ch!=',') { s=(BiTNode*)malloc(sizeof(BiTNode)); s->data=ch; s->lchild=NULL; s->rchild=NULL; }elses=NULL; q[++rear]=s; if(rear==1) root=s;

else { if(rear%2==0)q[front]->lchild=s;else{q[front]->rchild=s;front++; } }ch=getchar(); }//whilereturnroot;}

第35頁/共110頁三叉鏈表三叉鏈表的結(jié)點結(jié)構(gòu)：

parentLchilddataRchild二叉樹的三叉鏈表存儲表示

typedefstructTriTNode{

ElemTypedata;

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

structBiTNode*parent;

//雙親指針

}TriTNode,*TriTree;

第36頁/共110頁第37頁/共110頁雙親鏈表雙親鏈表的結(jié)點結(jié)構(gòu)：

dataparentLRTag二叉樹的雙親鏈表存儲表示typedefstructBPTNode{

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

ElemTypedata;

int*parent;

//指向雙親的指針

charLRTag;

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

}BPTNode

typedefstructBPTree{

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

BPTNode*nodes;

//初始化時分配存儲空間

intnodeNum;

//結(jié)點數(shù)目

introot;

//根結(jié)點的位置

}BPTree

第38頁/共110頁二叉樹的雙親鏈表建表過程constMAXSIZE=100;

//暫定二叉樹中結(jié)點數(shù)的最大值為100cin>>BT.nodeNum;

//輸入結(jié)點數(shù)目

BT.root=0;

cin>>BT.nodes[0].data;

//輸入根

BT.nodes[0].parent=-1;

//根的雙親為空

BT.nodes[0].LRTag=‘L’;

for(i=1;i<BT.nodeNum;i++)

{

cin>>BT.nodes[i].data>>F>>BT.nodes[i].LRtag;

k=i-1;

while(k>=0&&BT.nodes[k].data!=F)k--;//查詢雙親

if(k<0)returnFALSE;

//沒有找到雙親

BT.nodes[i].parent=k;

returnTRUE;

}第39頁/共110頁二叉樹的輸入數(shù)據(jù)為：

6,A,(B,A,L),(C,B,R),(D,A,R),(E,D,R),(F,E,L)

建立的雙親鏈表如下所示：第40頁/共110頁二叉樹的遍歷

“遍歷”的含義是對結(jié)構(gòu)中的每個數(shù)據(jù)元素都訪問一次且僅僅訪問一次。因此進行遍歷應(yīng)該確定一條搜索路徑，使得結(jié)構(gòu)中的每個數(shù)據(jù)元素都出現(xiàn)在這條搜索路徑上，才能確保每個數(shù)據(jù)元素都被訪問到。

二叉樹中每個結(jié)點都有兩個后繼，可以有三條搜索路徑：

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

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

3)按層次從上到下。

第41頁/共110頁先左后右的遍歷第一次走到根結(jié)點即“訪問”為“先序遍歷”，從左子樹回來再“訪問”為“中序遍歷”，從右子樹回來再"訪問"為"后序遍歷"第42頁/共110頁根據(jù)對二叉樹進行遍歷的先左后右的搜索路徑，可得以下三個遍歷二叉樹的算法先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點

(2)先序遍歷左子樹

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

否則

(1)中序遍歷左子樹

(2)訪問根結(jié)點

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

否則

(1)后序遍歷左子樹

(2)后序遍歷右子樹

(3)訪問根結(jié)點按照遍歷過程中先后訪問的次序?qū)⒍鏄渲械慕Y(jié)點排列起來可分別得到二叉樹的先序序列、中序序列和后序序列。第43頁/共110頁voidPreOrder(BiTreeT，void(*visit)(BiTree))

{

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

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

visit(T);

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

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

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

}//if

}第44頁/共110頁voidInOrder(BiTreeT，void(*visit)(BiTree))

{

//中序遍歷以T為根的二叉樹

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

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

visit(T);

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

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

}//if

}第45頁/共110頁voidPostOrder(BiTreeT，void(*visit)(BiTree))

{

//后序遍歷以T為根的二叉樹

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

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

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

visit(T);

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

}//if

}第46頁/共110頁遍歷算法例題1假設(shè)訪問二叉樹T的結(jié)點的操作是打印結(jié)點的值，請分別寫出下圖所示的二叉樹的先序、中序和后序序列ACBDFGHEJIAABF

ABCDEFGHIJ

ALARFLBLBRFRFBALARBLBRFLFRALAR第47頁/共110頁-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef用二叉樹可以表示數(shù)學(xué)表達式，例如：

a+b*(c-d)-e/f表達式的前綴表示表達式的中綴表示表達式的后綴表示第48頁/共110頁遍歷算法例題2已知二叉樹的先序和中序序列如下，試構(gòu)造出相應(yīng)的二叉樹。先序：ABCDEFGHIJ

中序：CDBFEAIHGJ原理：先序序列的第一個節(jié)點是根節(jié)點中序序列根結(jié)點處于左右子樹的中序序列之間注意：二叉樹的先序和后序序列不能唯一確定一棵二叉樹，但由先序和中序或后序和中序序列能唯一確定一棵二叉樹。先序：ABCDEFGHIJ中序：CDBFEAIHGJBCDEFCDBFEGHIJIHGJACDCDEFFEHIIHJJAGBAJECBFDGHI第49頁/共110頁非遞歸算法——中序遍歷BoolInOrder(BiTreeT,bool(*visit)(ElemTypee)){//采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹T的非遞歸算法

InitStack(S);Push(S,T);//根指針進棧

while(!StackEmpty(S)){while(Gettop(S,p)&&p)Push(S,p->lchild);//找最左下結(jié)點

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

if(!StackEmpty(S)){Pop(S,p);visit(p->data);//訪問結(jié)點

Push(S,p->rchild);//訪問右子樹

}//if}//whilereturnOK;}//InOrder第50頁/共110頁非遞歸算法——先序遍歷BoolPreOrder(BiTreeT,bool(*visit)(ElemTypee)){//采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹T的非遞歸算法

InitStack(S);Push(S,T);//根指針進棧

while(!StackEmpty(S)){Gettop(S,p)if(p){visit(p->data);//訪問結(jié)點

Push(S,p->lchild);}else{Pop(S,p);//空指針退棧

if(!StackEmpty(S)){Pop(S,p);Push(S,p->rchild);//訪問右子樹

}}//else}//whilereturnOK;}//InOrder第51頁/共110頁二叉樹算法舉例建立二叉樹的存儲結(jié)構(gòu)--二叉鏈表設(shè)二叉樹中結(jié)點的元素均為一個單字符，并以“#”表示空樹。假設(shè)二叉樹以由“根”、“左子樹串”和“右子樹串“聯(lián)接而成的字符串表示，則建立二叉鏈表的算法應(yīng)該是一個“先序遍歷”的過程，并且遍歷過程中“訪問”的操作應(yīng)是識別輸入的字符并作相應(yīng)操作

第52頁/共110頁例如，空樹以“#”表示，只有一個根結(jié)點A的二叉樹以"A##"表示，下列二叉樹則以"AB#CD###E#F##“表示。

第53頁/共110頁在輸入數(shù)據(jù)正確的前提下，由此建立二叉鏈表的算法為：

若輸入的字符是'#'，則建立空樹；

否則

建立根結(jié)點；

遞歸建立左子樹的二叉鏈表；

遞歸建立右子樹的二叉鏈表。

第54頁/共110頁voidCreateBiTree(BiTree&T)

{

//在先序遍歷二叉樹的過程中輸入二叉樹的“先序字符

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

//字符串中，字符‘#’表示空樹，其它字母字符為結(jié)點

//的數(shù)據(jù)元素

cin>>ch；

if(ch==‘#’)T=NULL;

//建空樹

else{

T=newBiTNode;

//“訪問”操作為生成根結(jié)點

T->data=ch;

CreateBiTree(T->Lchild);

//遞歸建(遍歷)左子樹

CreateBiTree(T->Rchild);//遞歸建(遍歷)右子樹

}//else

}//CreateBiTree第55頁/共110頁

先序序列為：ABDEGHCFIJ

中序序列為：DBGEHACIJF

后序序列為：DGHEBJIFCA

第56頁/共110頁二叉樹的線索鏈表如果將在第一次遍歷過程中得到的前驅(qū)和后繼信息保存起來，那么在以后需要再次對二叉樹進行“遍歷”時就可以將二叉樹視作線性結(jié)構(gòu)進行訪問操作第57頁/共110頁如何保存在遍歷過程中得到的前驅(qū)和后繼信息？最簡單的辦法是在結(jié)點中增加兩個指針域分別指向該結(jié)點的前驅(qū)和后繼。一個含n個結(jié)點的二叉鏈表中有n+1個鏈域的值為“NULL”，可以利用這些空的指針域存放指向前驅(qū)和后繼的信息，由此得到的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”，其中指向前驅(qū)或后繼的指針稱作"線索"。

第58頁/共110頁二叉樹的二叉線索鏈表存儲表示

typedefenumPointerType{Link=0,Thread=1};

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

typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*Lchild,*Rchild;

//左右指針

PointerTypeLTag,RTag;

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

}*BiThrTree;

第59頁/共110頁若結(jié)點的左指針類型標(biāo)志為“Link”，則Lchild指向它的左子樹根結(jié)點，否則指向它的“前驅(qū)”；若結(jié)點的右指針類型標(biāo)志為“Link”，則Rchild指向它的右子樹根結(jié)點，否則指向它的"后繼"。

第60頁/共110頁中序線索鏈表第61頁/共110頁在線索鏈表中添加了一個“頭結(jié)點”，頭結(jié)點的左指針指向二叉樹的根結(jié)點，其右線索指向中序序列中的最后一個結(jié)點，中序序列中的第一個結(jié)點的左線索和中序序列中的最后一個結(jié)點的右線索均指向頭結(jié)點。第62頁/共110頁以中序線索鏈表為存儲結(jié)構(gòu)的中序遍歷如何在中序線索鏈表上進行遍歷，關(guān)鍵問題有二：

一是如何找到訪問的第一個結(jié)點？

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

第63頁/共110頁如何找到訪問的第一個結(jié)點？中序遍歷訪問的第一個結(jié)點必定是"其左子樹為空“的結(jié)點。若根結(jié)點沒有左子樹，則根結(jié)點即為中序遍歷訪問的第一個結(jié)點，若根結(jié)點的左子樹不空，則訪問的第一個結(jié)點應(yīng)該是其左子樹中“最左下的結(jié)點“，即從根結(jié)點出發(fā)，順指針Lchild找到其左子樹直至某個結(jié)點的指針Lchild為“線索”止，該結(jié)點必為中序序列中的第一個結(jié)點。第64頁/共110頁如何找到每個結(jié)點在中序序列中的后繼？

若結(jié)點沒有右子樹，即結(jié)點的右指針類型標(biāo)志Rtag為“Thread”，則指針Rchild所指即為它的后繼若結(jié)點有右子樹，則它的后繼應(yīng)該是其右子樹中訪問的第一個結(jié)點。和前面所述找二叉樹的第一個結(jié)點一樣，就應(yīng)該從它的右子樹根出發(fā)，順指針Lchild直至沒有左子樹的結(jié)點為止，該結(jié)點即為它的后繼。

第65頁/共110頁例如：找結(jié)點B的后繼。結(jié)點B的RTag=Link，則順指針Rchild找到它的右子樹根E，因為結(jié)點E的LTag=Link，則順指針Lchild找到它的左子樹根G，因為結(jié)點G的Ltag=Thread，說明G是結(jié)點B的右子樹中“最左下”的結(jié)點，所以結(jié)點G是結(jié)點B的后繼。第66頁/共110頁voidInOrderTraverse_Thr(BiThrTreeThead,void(*Visit)(ElemTypee))

{

//Thead指向中序線索鏈表中的頭結(jié)點，頭結(jié)點的左指針Lchild

//指向二叉樹的根結(jié)點，頭結(jié)點的右線索Rchild指向中序遍歷

//訪問的最后一個結(jié)點。本算法對此二叉樹進行中序遍歷，對

//樹中每個數(shù)據(jù)元素調(diào)用函數(shù)Visit進行訪問操作

p=Thead->Lchild;

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

while(p!=Thead){

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

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

Visit(p->data);

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

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

p=p->rchild;Visit(p->data);

//訪問"右線索"所指后繼結(jié)點

}//while

p=p->Rchild;

//p進至其右子樹根

}//while

}//InOrderTraverse_Thr第67頁/共110頁線索鏈表的生成由于線索鏈表上保存的是“遍歷”過程中得到的前驅(qū)和后繼的信息，顯然，線索鏈表應(yīng)該在遍歷過程中建立，即在遍歷過程中改變二叉鏈表中結(jié)點的“空指針“以及相應(yīng)的”指針類型標(biāo)志“。若結(jié)點沒有左子樹，則令其左指針指向它的“前驅(qū)“并將左指針類型標(biāo)志改為“Thread”，若結(jié)點沒有右子樹，則令它的右指針指向它的“后繼”并將右指針類型標(biāo)志改為“Thread”。為了獲取“前驅(qū)”的信息，需要在遍歷過程中添加一個指向其前驅(qū)的指針pre。

第68頁/共110頁建立線索鏈表的過程即為將遍歷過程中對結(jié)點進行下列"訪問"操作(指針p指向當(dāng)前訪問的結(jié)點，pre指向在它之前“剛剛”訪問過的結(jié)點)：

if(!pre->Rchild){

pre->RTag=Thread;

pre->Rchild=p;

}

if(!p->Lchild){

p->LTag=Thread;

p->Lchild=pre;

}

pre=p;第69頁/共110頁voidInThreading(BiThrTreep，BiThrTree&pre)

{

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

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

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

//過程中緊隨其后，即始終指向p所指結(jié)點在中序序列中的前驅(qū)。

if(p){

InThreading(p->Lchild,pre);

//對左子樹進行線索化

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

//對右子樹進行線索化

}//if

}//InThreading第70頁/共110頁voidInOrderThreading(BiThrTree&Thead,BiThrTreeBT)

{

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

//的中序線索鏈表，Thead指向線索鏈表中的頭結(jié)點。

BiThrTreepre;

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

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

//建頭結(jié)點

Thead->Rchild=Thead;

//右指針回指

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

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

else{

Thead->Lchild=BT;pre=Thead;

InThreading(BT,pre);

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

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

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

Thead->Rchild=pre;

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

}//else

}//InOrderThreading第71頁/共110頁樹的存儲結(jié)構(gòu)——樹的雙親表示法樹的雙親鏈表存儲表示

constMAX_TREE_SIZE=100;

typedefstruct{

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

ElemTypedata;

intparent;

//雙親位置域

}PTNode;

typedefstruct{

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

PTNodenodes[MAX_TREE_SIZE];

intr,n;

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

}PTree;

第72頁/共110頁A-1B0E1H2I2J2C0D0F7G7K9該樹的雙親鏈表如下所示

01532648710911第73頁/共110頁樹的孩子表示法讓每個結(jié)點的“子樹根”構(gòu)成一個線性表，以鏈表作它的存儲結(jié)構(gòu)，令其頭指針和結(jié)點的數(shù)據(jù)元素構(gòu)成一個結(jié)點，并將所有這樣的結(jié)點存放在一個地址連續(xù)的存儲空間里，所構(gòu)成的樹的存儲結(jié)構(gòu)稱為樹的孩子鏈表。第74頁/共110頁樹的孩子鏈表存儲表示

typedefstructCTNode{

//孩子結(jié)點

intchild;

structCTNode*next;

}*ChildPtr;

typedefstruct{

ElemTypedata;

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

ChildPtrfirstchild;

//孩子鏈表頭指針

}CTBox;

typedefstruct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;

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

}CTree;第75頁/共110頁第76頁/共110頁樹和森林的孩子兄弟表示法樹和森林的二叉鏈表(孩子-兄弟）存儲表示

typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

樹中每個結(jié)點都設(shè)有兩個指針：

firstchild：指向該結(jié)點的“第一個”子樹根結(jié)點

nextsibling：指向它的"下一個"兄弟結(jié)點

第77頁/共110頁第78頁/共110頁可將上圖所示的二叉鏈表看成是下列二叉樹的存儲結(jié)構(gòu)由此，通過存儲結(jié)構(gòu)的一致性作為“媒介”，可建立森林和二叉樹之間一一對應(yīng)的關(guān)系

第79頁/共110頁森林和二叉樹的轉(zhuǎn)換假設(shè)森林

F={T1,T2,…,Tn}可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹

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

若森林F為空集，則二叉樹B為空樹；否則，由森林中第一棵樹的根結(jié)點ROOT(T1)復(fù)制得二叉樹的根Node(root)，由森林中第一棵樹的子樹森林轉(zhuǎn)換得到二叉樹中的左子樹LBT，由森林中刪去第一棵樹之后由其余樹構(gòu)成的森林{T2,T3,…,Tn}轉(zhuǎn)換得到二叉樹中的右子樹RBT第80頁/共110頁第81頁/共110頁反之，對于任意一棵二叉樹B=(LBT,Node(root),RBT)可轉(zhuǎn)換得到由n棵樹構(gòu)成的森林F={T1,T2,…,Tn}

若二叉樹B為空樹,則與其對應(yīng)的森林F為空集；否則，由二叉樹的根結(jié)點Node(root)復(fù)制得森林中第一棵樹的根結(jié)點ROOT(T1)，由二叉樹中的左子樹LBT轉(zhuǎn)換構(gòu)造森林中第一棵樹的子樹森林，由二叉樹中的右子樹RBT轉(zhuǎn)換構(gòu)造森林中其余樹構(gòu)成的森林{T2,T3,…,Tn}第82頁/共110頁樹的遍歷樹的遍歷：從根結(jié)點出發(fā)，對樹中各個結(jié)點進行一次且僅進行一次訪問對樹進行遍歷可有兩條搜索路徑：一條是從左到右；另一條是按層次從上到下

第83頁/共110頁對樹進行從左到右遍歷的過程中要途徑根結(jié)點兩次，由對根的訪問時機不同可得下列兩個算法：

一、先根(次序)遍歷樹

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

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

第84頁/共110頁森林的遍歷一、先序遍歷森林

若森林不空，則可依下列次序進行遍歷

(1)訪問森林中第一棵樹的根結(jié)點；

(2)先序遍歷第一棵樹中的子樹森林；

(3)先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

第85頁/共110頁二、中序遍歷森林

若森林不空，則可依下列次序進行遍歷：

(1)中序遍歷第一棵樹中的子樹森林；

(2)訪問森林中第一棵樹的根結(jié)點；

(3)中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

第86頁/共110頁容易看出，樹的先根遍歷即森林的先序遍歷可對應(yīng)到二叉樹的先序遍歷，樹的后根遍歷即森林的中序遍歷可對應(yīng)到二叉樹的中序遍歷。

第87頁/共110頁最優(yōu)樹和赫夫曼編碼最優(yōu)樹：又稱赫夫曼樹（HuffmanTree）是一類帶權(quán)路徑長度最短的樹路徑：從樹的根結(jié)點到其余結(jié)點的分支構(gòu)成的一條路徑路徑長度：路徑上的分支數(shù)目樹的路徑長度：指的是從樹根到樹中其余每個結(jié)點的路徑長度之和結(jié)點的帶權(quán)路徑長度：從樹根到該結(jié)點之間的路徑長度與該結(jié)點上所帶權(quán)值的乘積第88頁/共110頁樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和假設(shè)樹上有n個葉子結(jié)點，且每個葉子結(jié)點上帶有權(quán)值為wk(k=1,2,…,n)，則樹的帶權(quán)路徑長度為

其中l(wèi)k為帶權(quán)wk的葉子結(jié)點的帶權(quán)路徑長度

第89頁/共110頁

假設(shè)有n個權(quán)值{w1，w2，…wn}，試構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶權(quán)為

wi。顯然，這樣的二叉樹可以構(gòu)造出多棵，其中必存在一棵帶權(quán)路徑長度WPL取最小的二叉樹，稱該二叉樹為最優(yōu)二叉樹。

第90頁/共110頁右圖中的四棵二叉樹，都有5個葉子結(jié)點且?guī)嗤瑱?quán)值5、6、2、9、7，它們的帶權(quán)路徑長度分別為

WPL=7×3+9×3+5×2+6×2+2×2=74

WPL=2×1+6×3+7×4+9×4+5×2=94

WPL=6×2+7×2+5×3+2×3+9×2=65

WPL=2×1+5×3+7×3+9×3+6×3=83

第91頁/共110頁最優(yōu)樹的構(gòu)造方法赫夫曼最早給出了一個構(gòu)造最優(yōu)樹的帶有一般規(guī)律的算法，俗稱赫夫曼算法根據(jù)給定的n個權(quán)值{w1,w2,…wn}，構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空。在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中

重復(fù)(2)和(3)，直到F只含一棵樹為止。這棵樹便是所求的赫夫曼樹。第92頁/共110頁最優(yōu)前綴編碼赫夫曼二叉樹在通訊編碼中的一個應(yīng)用是利用它構(gòu)造一組最優(yōu)前綴編碼。在某些通訊場合，需將傳送的文字轉(zhuǎn)換成由二進制字符組成的字符串第93頁/共110頁

例如，假設(shè)需傳送的電文為“ABACCDA”，它只有

A、B、C和D四種字符，可設(shè)它們的編碼分別為

00、01、10和11，則上述七個字符的電文便為“000100101100”，總長14位。顯然這樣的等長編碼便于譯碼，對方接收時，可按兩位一分進行譯碼。

第94頁/共110頁通常有兩類二進制編碼：一類為等長編碼，這類編碼的二進制串的長度取決于電文中不同的字符個數(shù)，假設(shè)需傳送的電文中只有四種字符，只需兩位字符的串便可分辨，但如果電文中可能出現(xiàn)26種不同字符，則等長編碼串的長度為5。另一類是