楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha

第5章樹和二叉樹北京師范大學(xué)教育技術(shù)學(xué)院楊開城楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第1頁!一、樹的基本概念樹的定義任何一個非空樹是這樣一個包含n個結(jié)點的有限集合：⑴唯一存在一個結(jié)點R，它沒有前驅(qū)，被稱為根；⑵當(dāng)n>1時，除了根之外，其他結(jié)點可分為m(m>0)個不相交的子集T1,T2,…,Tm，其中每一個子集都是一棵樹，它們的根的前驅(qū)是R，這些子集被稱為R的子樹?；拘g(shù)語根葉子分枝結(jié)點內(nèi)部結(jié)點雙親孩子祖先子孫兄弟堂兄弟度層次深度(高度)有序樹無序樹森林楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第2頁!二、二叉樹——定義和基本性質(zhì)(1)定義：二叉樹（BinaryTree）是一種特殊的樹形結(jié)構(gòu)。它的特點是每個結(jié)點最多有兩個子樹，而且子樹分左右，不能任意顛倒，我們通常稱之為左子樹和右子樹。楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第3頁!二、二叉樹——定義和基本性質(zhì)(2)基本性質(zhì)：⑴二叉樹的第i層最多有2i-1（i≥1）個結(jié)點。⑵深度是k的二叉樹，最多有2k－1個結(jié)點。⑶設(shè)任意一棵二叉樹中，葉子結(jié)點數(shù)為n0，度是1的結(jié)點(即單枝結(jié)點)數(shù)為n1，度為2的結(jié)點(即雙枝結(jié)點)數(shù)為n2，則有：n0=n2+1。⑷具有n個結(jié)點的完全二叉樹的深度是⑸對于一個n個結(jié)點的完全二叉樹，自上而下、自左向右給結(jié)點編號，根結(jié)點編號為1。如果已知某結(jié)點編號是i，那么①如果i=1，那么結(jié)點是根，如果i＞1，那么它的雙親是i/2,即②如果2i＞n，那么該結(jié)點沒有左孩子，否則它的左孩子是2i；③如果2i+1＞n，那么該結(jié)點沒有右孩子，否則它的右孩子是2i+1。楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第4頁!二、二叉樹——存儲結(jié)構(gòu)(2)2．二叉樹的鏈?zhǔn)酱鎯Χ骀湵眍愋投x：typedefstructbtreenode{chardata;/*數(shù)據(jù)域可以是任意類型*/structbtreenode*lchild,*rchild;/*指向左右孩子的指針*/}BTREENODE,*BTREENODEPTR,*BTREE;三叉鏈表類型定義：typedefstructbtreenode{chardata;structbtreenode*lchild,*rchild;structbtreenode*parent;/*指向雙親的指針*/}PBTREENODE,*PBTREENODEPTR,*PBTREE;楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第5頁!二、二叉樹——建立與銷毀(2)typedefBTREENODEPTRelemtype;BTREECreateBtree1(char*str){/*字符串str是廣義表字符串，以它作為輸入數(shù)據(jù)，返回建立的二叉樹*/BTREEroot=NULL;/*二叉樹根結(jié)點指針*/BTREENODEPTRp;inttag,i,len;intmark;/*記錄掃描到的字符類型，1代表字母,2代表(,3代表逗號,4代表)*/SQSTACKs;/*棧中存放左右孩子為生成完畢的結(jié)點*/if(str[0]==0)returnroot;/*廣義表是空，返回NULL*/root=(BTREENODEPTR)malloc(sizeof(BTREENODE));/*生成根結(jié)點*/if(root==NULL)returnroot;/*假設(shè)str[0]是字母*/root->data=str[0];root->lchild=root->rchild=NULL;len=strlen(str);/*初始化棧，容量是字符串的長度*/InitSqstack(&s,len);楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第6頁!二、二叉樹——建立與銷毀(4)case',': if(mark==3)returnNULL;/*連續(xù)出現(xiàn)逗號，廣義表非法*/ mark=3;/*掃描到逗號*/ tag=1;/*準(zhǔn)備生成棧頂結(jié)點的右孩子*/ break;default:if(mark==1)returnNULL;/*連續(xù)出現(xiàn)兩個字母，廣義表非法*/mark=1;/*掃描到字母*/

/*如果?？?，找不到當(dāng)前結(jié)點的雙親，廣義表非法*/ if(IsSqstackEmpty(s))returnNULL;

/*生成當(dāng)前結(jié)點，并與棧頂結(jié)點建立孩子關(guān)系*/ p=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p==NULL) returnNULL; p->data=str[i];p->lchild=p->rchild=NULL; if(tag==0)s.elem[s.top]->lchild=p;/*當(dāng)前結(jié)點是棧頂結(jié)點的左孩子*/ elses.elem[s.top]->rchild=p;/*當(dāng)前結(jié)點是棧頂結(jié)點的左孩子*/ break; }returnroot;}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第7頁!三、二叉樹的遍歷——算法(1)遍歷的規(guī)則：先序遍歷：ABDHJEICFG中序遍歷：DJHBEIAFCG后序遍歷：JHDIEBFGCA層序遍歷：ABCDEFGHIJ遍歷的遞歸算法⑴先序遍歷voidPreOrder(BTREEroot,char*str){/*先序遍歷二叉樹root，將遍歷結(jié)果存放在str中，str一開始為空*/chartmpstr[10];if(root==NULL)return;sprintf(tmpstr,"%c",root->data);/*將數(shù)據(jù)域數(shù)據(jù)轉(zhuǎn)化為字符串tmpstr*/strcat(str,tmpstr);/*將tmpstr續(xù)接到str后*/PreOrder(root->lchild,str);/*遍歷左子樹*/PreOrder(root->rchild,str);/*遍歷右子樹*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第8頁!三、二叉樹的遍歷——算法(3)遍歷的遞歸算法⑶后序遍歷voidPostOrder(BTREEroot,char*str){/*后序遍歷二叉樹root，將遍歷結(jié)果存放在str中，str一開始為空*/chartmpstr[10];if(root==NULL)return;PostOrder(root->lchild,str);/*遍歷左子樹*/PostOrder(root->rchild,str);/*遍歷右子樹*//*開始訪問根結(jié)點*/sprintf(tmpstr,"%c",root->data);strcat(str,tmpstr);}調(diào)用方法charstr[80];str[0]=0;PreOrder(root,str);printf("%s",str);楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第9頁!三、二叉樹的遍歷——算法(5)遍歷的非遞歸算法⑵中序遍歷voidInOrder1(BTREEroot,char*str){chartmpstr[20];SQSTACKs;BTREENODEPTRp;InitSqstack(&s,MAXCOUNT);p=root;Push(&s,p);/*將初始問題（根結(jié)點）入棧*/while(1)/*無限循環(huán)，?？胀顺?/{p=s.elem[s.top];/*取棧頂問題p*/while(p->lchild!=NULL)/*只要當(dāng)前問題p的左孩子不空，就繼續(xù)向左遞歸分解*/{p=p->lchild;/*p被遞歸分解為它的左孩子*/Push(&s,p);/*問題p入棧，為了找到p的右孩子，生成第二個問題*/ }while(!IsSqstackEmpty(s))/*棧中可能會連續(xù)存放遞歸終點的問題*/{Pop(&s,&p);/*棧頂問題p出棧*/sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*無論p是否是遞歸終點，都要訪問p結(jié)點自身*/楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第10頁!三、二叉樹的遍歷——算法(7)遍歷的非遞歸算法⑶后序遍歷voidPostOrder1(BTREEroot,char*str){chartmpstr[20];SQSTACKs;BTREENODEPTRp;InitSqstack(&s,MAXCOUNT);p=root;Push(&s,p);/*將問題p入棧*/while(1){p=s.elem[s.top];/*取棧頂問題p*/while(p->lchild!=NULL)/*當(dāng)前問題p左孩子不空，需要遞歸分解*/{p=p->lchild;/*p遞歸分解為它的左孩子*/Push(&s,p);/*將問題p入棧，為了找到它的右孩子，即第二個問題*/ }楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第11頁!三、二叉樹的遍歷——算法(9) if(IsSqstackEmpty(s)) {/*?？眨瑒t遍歷結(jié)束*/ DestroySqstack(&s); return; } }//出棧處理while(1)}}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第12頁!三、二叉樹的遍歷——算法的應(yīng)用(1)1．求二叉樹的深度intGetHeight(BTREEroot){/*返回二叉樹root的深度值*/intlh,rh;if(root==NULL)return0;/*空樹，深度是0*/lh=GetHeight(root->lchild);/*遞歸調(diào)用獲得左子樹的深度*/rh=GetHeight(root->rchild);/*遞歸調(diào)用獲得右子樹的深度*//*取左右子樹深度值大者，作為子樹的深度，這個樹的深度是子樹深度加1*/if(lh>=rh)returnlh+1;elsereturnrh+1;}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第13頁!三、二叉樹的遍歷——算法的應(yīng)用(3)3．利用層序遍歷序列建立二叉樹輸入數(shù)據(jù)的例子：“ABC@DE@”和“ABCDE@”BTREECreateBtree2(char*str){/*字符串str中是二叉樹的層序輸入序列字符串，返回所建立的二叉樹*/BTREEroot=NULL;BTREENODEPTRp1,p2;SQQUEUEq;intk;if(str[0]==0)returnroot;/*生成根結(jié)點，數(shù)據(jù)域是str[0]*/root=(BTREE)malloc(sizeof(BTREENODE));if(root==NULL)returnNULL;root->data=str[0];root->lchild=root->rchild=NULL;/*左右孩子默認(rèn)為空*/InitSqqueue(&q,100);/*初始化隊列*/EnSqqueue(&q,root);/*將根結(jié)點入隊*/楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第14頁!三、二叉樹的遍歷——算法的應(yīng)用(5)if(str[k]!=0)/*未到字符串末尾，可以為結(jié)點p1生成右孩子*/{if(str[k]!='@'){p2=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p2==NULL) {DestroyBtree(root);returnNULL; } p2->data=str[k];p2->lchild=p2->rchild=NULL; p1->rchild=p2; EnSqqueue(&q,p2); } k++; } }//whileDestroySqqueue(&q);returnroot;}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第15頁!四、線索化二叉樹(2)線索化的二叉樹的數(shù)據(jù)類型typedefstructthrbtreenode{chardata;intltag,rtag;/*ltag是0時，lchild指向左孩子，ltag是1時，lchild指向前驅(qū)；rtag是0時，rchild指向右孩子，rtag是1時，rchild指向后繼*/structthrbtreenode*lchild,*rchild;}THRBTREENODE,*THRBTREENODEPTR,*THRBTREE;算法思想在中序遍歷過程中建立線索；設(shè)置一個全局變量保存在遍歷過程中當(dāng)前結(jié)點的前驅(qū)；為了方便使用，我們?yōu)榫€索化了的二叉樹設(shè)定另一個頭結(jié)點head，head的左孩子指向真正二叉樹的根結(jié)點，右孩子最終指向中序序列的最后一個結(jié)點（為了方便逆序遍歷二叉樹時很容易找到最后一個結(jié)點）。

楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第16頁!四、線索化二叉樹(4)voidInOrderThr(THRBTREEp)/*為二叉樹建立線索*/{if(p==NULL)return;/*遞歸終點*/InOrderThr(p->lchild);/*為左子樹建立線索*/

/*這時pre是p的前驅(qū)*/if(pre!=NULL&&pre->rchild==NULL){/*如果pre不空，并且pre的右孩子是NULL，將pre的右孩子指向p*/ pre->rtag=1;/*表明pre->rchild是線索指針*/ pre->rchild=p; }if(p->lchild==NULL){/*如果p的左孩子是NULL，將p的左孩子指向pre*/ p->ltag=1;/*表明p->lchild是線索指針*/ p->lchild=pre; }pre=p;/*在遍歷其他結(jié)點之前，pre指向p*/InOrderThr(p->rchild);/*為右子樹建立線索*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第17頁!四、線索化二叉樹(6)先序線索化算法voidPreOrderThr(THRBTREEp)/*先序遍歷的線索化操作*/{if(p==NULL)return;

/*建立pre與p之間的前驅(qū)后繼關(guān)系*/if(pre!=NULL&&pre->rchild==NULL){pre->rtag=1;pre->rchild=p; }if(p->lchild==NULL){p->ltag=1;p->lchild=pre; }pre=p;/*pre指向p*/if(p->ltag==0)PreOrderThr(p->lchild);/*建立左子樹的線索*/if(p->rtag==0)PreOrderThr(p->rchild);/*建立右子樹的線索*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第18頁!五、哈夫曼樹(1)哈夫曼樹，又稱最優(yōu)樹，是一種帶權(quán)路徑長度最短的樹。路徑長度：樹中某結(jié)點到其子樹另一結(jié)點之間的分枝個數(shù)。樹的路徑長度：從根到每一個結(jié)點的路徑長度之和。樹的帶權(quán)路徑長度：所有葉子結(jié)點帶權(quán)路徑長度之和。假設(shè)一個二叉樹有n個葉子結(jié)點，每個葉子結(jié)點的路徑長度是lk

，權(quán)值是Wk

，那么整個二叉樹的帶權(quán)路徑長度記為：哈夫曼樹可以分為二叉哈夫曼樹和多叉哈夫曼樹。楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第19頁!五、哈夫曼樹(3)哈夫曼樹的構(gòu)造將n個帶權(quán)結(jié)點自成n個子樹，每個子樹只有一個根結(jié)點，這樣我們就得到一個n棵二叉樹的集合F={T1,T2,…,Tn}。執(zhí)行循環(huán)：選取F中權(quán)值最小的兩棵樹Ti和Tj，生成一棵以這兩棵樹為左右子樹的新二叉樹Tk，Tk根結(jié)點的權(quán)值是Ti和Tj根結(jié)點權(quán)值之和。將Ti,和Tj從F集合中刪除，將Tk加入到F集合中。直到F集合中只有一棵二叉樹為止。楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第20頁!五、哈夫曼樹(5)for(i=1;str[i]!=0;i++)/*掃描字符串，計算有多少種字符*/{for(j=i-1;j>=0;j--)/*檢查str[0..i-1]中有無str[i]*/ if(str[i]==str[j])break;if(j==-1)num++;/*str[i]次出現(xiàn)，num增1*/ }/*n個葉子結(jié)點的哈夫曼樹，其他結(jié)點個數(shù)是n-1。還需要1個單元存放葉子結(jié)點個數(shù)*/num=2*num;ht=(HUFFMANTREE)malloc(num*sizeof(HUFFMANNODE));if(ht==NULL)returnNULL;for(i=0;i<num;i++)/*初始化所有的數(shù)組單元，每個單元自成一棵樹*/{ht[i].w=0;/*權(quán)值歸零*/ht[i].lchild=ht[i].rchild=-1;/*左右孩子為空，用-1表示NULL*/ }

楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第21頁!五、哈夫曼樹(7)for(i=0;i<num-1;i++)/*對葉子結(jié)點按照權(quán)值升序排序*/{k=i;for(j=i+1;j<num;j++)if(ht[j+1].w<ht[k+1].w) k=j;if(k!=i){tmpht=ht[i+1]; ht[i+1]=ht[k+1];ht[k+1]=tmpht;}}ht[0].w=num;/*用ht的首單元存放葉子結(jié)點個數(shù)*/returnht;/*返回數(shù)組*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第22頁!五、哈夫曼樹(9)for(j=num+i-1;j>=k+2;j--)/*將新結(jié)點hfnode有序插入到數(shù)組中*/if(ht[j].w>hfnode.w) ht[j+1]=ht[j];elsebreak;ht[j+1]=hfnode;root=j+1;/*root一直跟隨新生成的結(jié)點,最后一個新生成的結(jié)點是根*/}returnroot;}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第23頁!五、哈夫曼樹(11)else{/*不是遞歸終點，繼續(xù)遞歸調(diào)用*/ len=strlen(codestr); codestr[len]='0';/*左分支編碼是0*/

/*向左孩子遞歸之前，調(diào)整路徑上的編碼序列，末尾增加0*/ codestr[len+1]=0; GetHuffmanCode(ht,ht[root].lchild,codestr);/*向左遞歸*/ len=strlen(codestr);/*右分支編碼是1，向右孩子遞歸之前，將原編碼末尾0改為1*/ codestr[len-1]='1'; GetHuffmanCode(ht,ht[root].rchild,codestr);/*向右遞歸*//*左右孩子遞歸返回后，向上返回之前，刪掉編碼末尾的一位*/ len=strlen(codestr); codestr[len-1]=0; }}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第24頁!六、樹和森林——樹的存儲(2)2．孩子－雙親表示法typedefstruct{chardata;/*假定樹結(jié)點的數(shù)據(jù)域是char型*/intparent;/*結(jié)點的雙親，-1表示NULL*/CHILDNODEchildlink;/*孩子鏈表的頭結(jié)點*/}CPTREENODE;楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第25頁!六、樹和森林——森林與二叉樹的轉(zhuǎn)換楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第26頁!導(dǎo)航圖(1)楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第27頁!導(dǎo)航圖(3)楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第28頁!導(dǎo)航圖(5)楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第29頁!二、二叉樹——存儲結(jié)構(gòu)(1)1．二叉樹的順序存儲#defineN50/*最大結(jié)點數(shù)*/typedefelemtypeSQBTREE[N+1];/*數(shù)組0號單元空閑，不存放結(jié)點*/楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第30頁!二、二叉樹——建立與銷毀(1)1．二叉樹的建立——以廣義表字符串作為輸入例子：

A（B（D（,H（J,））,E（,I））,C（F,G））【算法思想】從左向右掃描廣義表字符串，我們會遇到這樣幾種字符：①字母，字母代表結(jié)點，遇到字母時，當(dāng)然要建立結(jié)點。需要設(shè)定一個棧，將所有左右孩子沒有生成完畢的結(jié)點保存起來。當(dāng)前結(jié)點的雙親必然是棧頂結(jié)點。②左括號，左括號前面一定是一個字母。因此遇到左括號時，意味著要生成前面字母結(jié)點的左右孩子，這時要將前面字母的結(jié)點入棧。③逗號，逗號的前面是某個結(jié)點的左孩子，后面是某個結(jié)點的右孩子。④右括號，右括號意味著某個結(jié)點的左右孩子都生成完畢，這個結(jié)點一定位于棧頂。這時需要出棧操作。楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第31頁!二、二叉樹——建立與銷毀(3)p=root;/*p指向當(dāng)前生成的結(jié)點*/mark=1;/*標(biāo)明掃描到字母*/for(i=1;str[i]!=0;i++)/*開始從左向右掃描字符串*/switch(str[i]){case'(': if(mark==2)returnNULL;/*連續(xù)出現(xiàn)（,非法*/ mark=2;/*掃描到左括號*/ Push(&s,p);/*將當(dāng)前結(jié)點入棧*/ tag=0;/*標(biāo)明準(zhǔn)備生成左孩子*/ break;case')': mark=4;/*掃描到右括號*/

/*棧頂結(jié)點左右孩子生成完畢，出棧*/ if(!Pop(&s,&p))/*括號不配對*/ returnNULL; break;楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第32頁!二、二叉樹——建立與銷毀(4)2．二叉樹的銷毀voidDestroyBtree(BTREEroot){/*銷毀二叉樹的遞歸算法*/if(root==NULL)return;/*銷毀左子樹*/DestroyBtree(root->lchild);/*銷毀右子樹*/DestroyBtree(root->rchild);root->lchild=NULL;root->rchild=NULL;free(root);/*釋放結(jié)點內(nèi)存*/}ABCDE楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第33頁!三、二叉樹的遍歷——算法(2)遍歷的遞歸算法⑵中序遍歷voidInOrder(BTREEroot,char*str){/*中序遍歷二叉樹root，將遍歷結(jié)果存放在str中，str一開始為空*/chartmpstr[10];if(root==NULL)return;InOrder(root->lchild,str);/*遍歷左子樹*/

/*開始訪問根結(jié)點*/sprintf(tmpstr,"%c",root->data);/*將數(shù)據(jù)域數(shù)據(jù)轉(zhuǎn)化為字符串tmpstr*/strcat(str,tmpstr);/*將tmpstr續(xù)接到str后*/InOrder(root->rchild,str);/*遍歷右子樹*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第34頁!三、二叉樹的遍歷——算法(4)遍歷的非遞歸算法⑴先序遍歷voidPreOrder1(BTREEroot,char*str){chartmpstr[20];SQSTACKs;BTREENODEPTRp;InitSqstack(&s,MAXCOUNT);/*初始化棧,MAXCOUNT根據(jù)需要定義*/p=root;/*p指向根結(jié)點*/Push(&s,p);/*將當(dāng)前結(jié)點入棧*/while(!IsSqstackEmpty(s))/*棧中有未遍歷的子樹*/{Pop(&s,&p);/*彈出棧頂問題（子樹p）*/sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*訪問這顆子樹的根結(jié)點*/

/*將p遞歸分解為它的左右子樹，先將右子樹入棧，再將左子樹入棧*/if(p->rchild!=NULL)Push(&s,p->rchild);if(p->lchild!=NULL)Push(&s,p->lchild);}DestroySqstack(&s);}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第35頁!三、二叉樹的遍歷——算法(6)if(p->rchild!=NULL){/*如果p的右孩子不空，將p的右孩子入棧，即將第二個問題入棧*/ Push(&s,p->rchild); break;/*轉(zhuǎn)去繼續(xù)遞歸分解*/ } }if(IsSqstackEmpty(s)){/*如果發(fā)現(xiàn)棧空，遍歷結(jié)束*/DestroySqstack(&s);return; }}}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第36頁!三、二叉樹的遍歷——算法(8)while(1)/*出棧處理循環(huán)*/{if(s.elem[s.top]->rchild!=NULL) {/*如果棧頂結(jié)點右孩子不空，棧頂問題需要繼續(xù)遞歸分解*/ p=s.elem[s.top]->rchild;/*p指向棧頂結(jié)點的右孩子*/ Push(&s,p);/*問題p入棧*/ break;/*轉(zhuǎn)去遞歸分解*/}/*棧頂結(jié)點右孩子為空，才可以進(jìn)行出棧處理，可能會將遞歸終點連續(xù)出棧*/ while(!IsSqstackEmpty(s)) {if(s.elem[s.top]->rchild==NULL||s.elem[s.top]->rchild==p) {/*棧頂問題是遞歸終點的條件：右孩子是空(一般首先遇到)或者它的右孩子是原棧頂結(jié)點p（這個條件只有在出棧處理時才是遞歸終點的條件）*/ Pop(&s,&p);/*棧頂問題p出棧*/ sprintf(tmpstr,"%c",p->data);/*訪問結(jié)點p*/ strcat(str,tmpstr);} else break;/*否則跳出彈出遞歸終點的循環(huán)*/ }楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第37頁!三、二叉樹的遍歷——算法(10)層序遍歷

voidLayerOrder(BTREEroot,char*str){/*層序遍歷二叉樹root,遍歷結(jié)果放在str中，str一開始為空*/chartmpstr[20];SQQUEUEqu;BTREENODEPTRp;InitSqqueue(&qu,MAXCOUNT);EnSqqueue(&qu,root);/*將根結(jié)點入隊*/while(!IsSqqueueEmpty(qu))/*只要隊列不空就循環(huán)，隊列空則遍歷完畢*/{DeSqqueue(&qu,&p);/*出隊一個結(jié)點p*/sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*訪問結(jié)點p*/if(p->lchild!=NULL)/*將左孩子入隊*/EnSqqueue(&qu,p->lchild);if(p->rchild!=NULL)/*將左孩子入隊*/EnSqqueue(&qu,p->rchild);}}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第38頁!三、二叉樹的遍歷——算法的應(yīng)用(2)2．計算葉子結(jié)點的總數(shù)intCountLeaf(BTREEroot){/*返回二叉樹root中葉子結(jié)點總數(shù)*/intlnum,rnum;if(root==NULL)return0;/*空樹，葉子結(jié)點個數(shù)是0*/lnum=CountLeaf(root->lchild);/*遞歸調(diào)用求左子樹葉子結(jié)點個數(shù)*/rnum=CountLeaf(root->rchild);/*遞歸調(diào)用求右子樹葉子結(jié)點個數(shù)*//*如果左右子樹葉子的和是0，說明當(dāng)前結(jié)點是葉子，返回1；否則返回左右子樹葉子結(jié)點的和*/if((lnum+rnum)==0)return1;elsereturnlnum+rnum;}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第39頁!三、二叉樹的遍歷——算法的應(yīng)用(4)k=1;/*k是字符串str的下標(biāo)，從1開始向后掃描*/while(!IsSqqueueEmpty(q)){/*隊列不空，意味著還有結(jié)點的左右孩子沒有建立*/DeSqqueue(&q,&p1);/*出隊一個結(jié)點p1*/if(str[k]!=0)/*如果字符串沒有到末尾，可以為p1生成左孩子結(jié)點*/{if(str[k]!='@')/*左孩子結(jié)點不是空，生成結(jié)點*/{ p2=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p2==NULL)/*生成結(jié)點失敗，銷毀已經(jīng)建立的二叉樹，返回NULL*/ {DestroyBtree(root);returnNULL;} p2->data=str[k];p2->lchild=p2->rchild=NULL; p1->lchild=p2;/*p2成為p1的左孩子*/ EnSqqueue(&q,p2);/*將p2入隊*/ }/*如果str[k]是@，什么都不做*/ k++;/*下標(biāo)先后移動*/ }楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第40頁!四、線索化二叉樹(1)由于任何一個二叉樹的結(jié)點都有兩個指針域，當(dāng)指針域是NULL時，它是空閑的。如果這種情況下，將指針域分別指向前驅(qū)和后繼，對于查找結(jié)點的前驅(qū)后繼是非常方便的。用于這個目的的lchild和rchild指針被稱為線索。將lchild和rchild分別指向前驅(qū)和后繼的操作被稱為線索化?！締栴}】已知一棵二叉樹，如何在中序遍歷序列中確定結(jié)點B和結(jié)點I的前驅(qū)后繼結(jié)點呢？【結(jié)論】如果結(jié)點具有左右子樹，我們很容易確定它的前驅(qū)和后繼。如果結(jié)點的左右孩子是NULL，確定起來就非常繁瑣。楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第41頁!四、線索化二叉樹(3)線索化算法THRBTREENODEPTRpre;/*全局變量pre*/THRBTREEInOrderThread(THRBTREEroot){/*為root建立線索，返回線索化了的二叉樹的頭結(jié)點指針*/THRBTREEhead;/*線索化二叉樹的頭結(jié)點*/head=(THRBTREENODEPTR)malloc(sizeof(THRBTREENODE));if(head==NULL)returnNULL;pre=NULL;/*pre初始值是NULL*/head->lchild=root;/*頭結(jié)點左孩子指向二叉樹的根*/head->rchild=NULL;/*頭結(jié)點右孩子初始化為NULL*/InOrderThr(root);/*為二叉樹建立線索*/head->rchild=pre;/*這時，pre指向中序遍歷最后一個結(jié)點*/returnhead;/*返回頭結(jié)點指針*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第42頁!四、線索化二叉樹(5)利用中序線索遍歷二叉樹voidTraverseInOrderThr(THRBTREEroot,char*str){/*遍歷線索化了的二叉樹，將遍歷結(jié)果存放在str中*/chartmpstr[20];THRBTREENODEPTRp;p=root;/*p指向根結(jié)點*/while(1)/*遍歷循環(huán)*/{while(p->ltag==0)/*尋找p的最左端結(jié)點*/p=p->lchild;sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*訪問結(jié)點p*/while(p->rtag==1&&p->rchild!=NULL)/*沿著線索指針遍歷后繼結(jié)點*/{p=p->rchild;sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);}if(p->rchild==NULL)return;/*遇到最后一個結(jié)點，返回*/elsep=p->rchild;/*p有右孩子，跳到右分枝*/}}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第43頁!四、線索化二叉樹(7)后序線索化算法voidPostOrderThr(THRBTREEp)/*后序遍歷的線索化*/{if(p==NULL)return;PostOrderThr(p->lchild);/*建立左子樹的線索*/PostOrderThr(p->rchild);/*建立右子樹的線索*/

/*建立pre和p之間的前驅(qū)后繼關(guān)系*/if(pre!=NULL&&pre->rchild==NULL){pre->rtag=1;pre->rchild=p; }if(p->lchild==NULL){p->ltag=1;p->lchild=pre; }pre=p;/*將p指向pre*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第44頁!五、哈夫曼樹(2)【問題】在某兩地之間的一次網(wǎng)絡(luò)通訊業(yè)務(wù)中，發(fā)送的字符串是“ACCEEBBBEECCDDDDCDDEEEE”，并且已知這類通訊業(yè)務(wù)只發(fā)送ABCDE這5種字符。問如何對ABCDE這5種字符進(jìn)行編碼，才使得通訊時發(fā)送的數(shù)據(jù)總量最小（成本最低）？【解決方案】方案1：直接發(fā)送字符的ASCII碼發(fā)送的數(shù)據(jù)量：(1+3+5+6+8)×8=184(比特)。方案2：A：000B：001C：010D：011E：100發(fā)送的數(shù)據(jù)量：(1+3+5+6+8)×3=69(比特)方案3：A：0B：1C：00D：01E：001發(fā)送的數(shù)據(jù)量：1+3+5*2+6*2+8*3=50(比特)方案4：A：000B：001C：01D：10E：11發(fā)送的數(shù)據(jù)量：(1+3)*3+(5+6+8)*2=50(比特)楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第45頁!五、哈夫曼樹(4)typedefstruct{charch;/*結(jié)點字符*/intw;/*結(jié)點權(quán)值*/intlchild,rchild;/*左右孩子，是數(shù)組下標(biāo)*/}HUFFMANNODE,*HUFFMANTREE;初始化存放哈夫曼樹的數(shù)組HUFFMANTREEInitHuffman(void){/*接受字符串輸入，將字符出現(xiàn)的個數(shù)作為權(quán)值，返回只包含葉子結(jié)點的HUFFMANNODE數(shù)組，這個數(shù)組的首單元存放葉子結(jié)點的個數(shù)*/charstr[80];intnum;inti,j,k;HUFFMANTREEht;HUFFMANNODEtmpht;printf("pleaseinputthestringforhuffmancoding:\n");gets(str);/*輸入字符串*/if(str[0]==0)returnNULL;num=1;/*出現(xiàn)的字符個數(shù)，即葉子結(jié)點個數(shù)*/楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第46頁!五、哈夫曼樹(6)num=0;/*葉子結(jié)點總量*/for(i=0;str[i]!=0;i++)/*重新掃描字符串，將計數(shù)信息作為結(jié)點的權(quán)值*/{for(j=0;j<num;j++)/*尋找與字符str[i]相同的葉子結(jié)點*/if(ht[j+1].ch==str[i])break;if(j==num)/*未找到，即發(fā)現(xiàn)新字符*/{ ht[num+1].ch=str[i];/*新葉子結(jié)點，記錄字符信息*/ ht[num+1].w++;/*權(quán)值增1，最初是0*/ num++;/*葉子結(jié)點個數(shù)增1*/

}elseht[j+1].w++;/*找到了，相應(yīng)的葉子結(jié)點權(quán)值增1*/}楊開成數(shù)據(jù)結(jié)構(gòu)C語言cha共55頁，您現(xiàn)在瀏覽的是第47頁!五、哈夫曼樹(8)生成哈夫曼樹intCreateHuffman(HUFFMANTREEht){/*在數(shù)組ht中生成哈夫曼樹，返回哈夫曼樹的根結(jié)點下標(biāo)*/inti,num,k,j,root;HUFFMANNODEhfnode;num=ht[0].w;f