數(shù)據(jù)結(jié)構(gòu)與算法第四章樹與二叉樹4/21/20231第1頁，共75頁，2023年，2月20日，星期六第4章樹與二叉樹4.1

樹的基本概念4.2二叉樹4.3

二叉樹的遍歷4.4

線索二叉樹4.5

樹和森林4.6

哈夫曼樹4/21/20232第2頁，共75頁，2023年，2月20日，星期六4.1樹的基本概念4.1.1樹的定義及表示樹:n個結(jié)點(diǎn)的有限集(n>=0)Root樹根子樹子樹4/21/20233第3頁，共75頁，2023年，2月20日，星期六4.1.2樹的常用術(shù)語及運(yùn)算樹的結(jié)點(diǎn)結(jié)點(diǎn)的度---結(jié)點(diǎn)擁有的子樹的個數(shù)葉子結(jié)點(diǎn)---度為0的結(jié)點(diǎn)，又稱終端結(jié)點(diǎn)分枝結(jié)點(diǎn)---度不為0的結(jié)點(diǎn)樹的度---樹內(nèi)結(jié)點(diǎn)度的最大值樹的層次---第一層從根結(jié)點(diǎn)開始，根的孩子在第二層，依此類推樹的深度---樹中結(jié)點(diǎn)的最大層次ADEBCFHIGJKM4/21/20234第4頁，共75頁，2023年，2月20日，星期六4.1.2樹的常用術(shù)語及運(yùn)算孩子(結(jié)點(diǎn))---結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)雙親(結(jié)點(diǎn))---結(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)的子孫ADEBCFHIGJK4/21/20235第5頁，共75頁，2023年，2月20日，星期六4.1.2樹的常用術(shù)語及運(yùn)算樹的基本運(yùn)算(1)setnull(T):初始化操作，置T為空樹。(2)求根結(jié)點(diǎn)ROOT(T)或ROOT(x)。求樹T的根或求結(jié)點(diǎn)x所在的樹的根結(jié)點(diǎn)。若T是空樹或x不在任何一棵樹上，則函數(shù)值為“空”。(3)求雙親結(jié)點(diǎn)RARENT(T,x)。求樹T中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn)x是樹T的根結(jié)點(diǎn)或結(jié)點(diǎn)x不在樹T中，則函數(shù)值為“空”。(4)求孩子結(jié)點(diǎn)CHILD(T,x,i)。求樹T中結(jié)點(diǎn)x的第i個孩子結(jié)點(diǎn)。若結(jié)點(diǎn)x是樹T的葉子或無第i個孩子或結(jié)點(diǎn)x不在樹T中，則函數(shù)值為“空”。(5)建樹creat(x,F)。生成以x結(jié)點(diǎn)為根、以森林F為子樹森林的樹。(6)求右兄弟結(jié)點(diǎn)RIGHT_SIBLING(T,x)。求樹T中結(jié)點(diǎn)x右邊的兄弟。若結(jié)點(diǎn)x是其雙親的最右邊的孩子結(jié)點(diǎn)或結(jié)點(diǎn)x不在樹T中，則函數(shù)值為“空”。4/21/20236第6頁，共75頁，2023年，2月20日，星期六4.1.2樹的常用術(shù)語及運(yùn)算樹的基本運(yùn)算(7)插入子樹操作addchild(y,i,x)。置以結(jié)點(diǎn)x為根的樹為結(jié)點(diǎn)y的第i棵子樹。若原樹中無結(jié)點(diǎn)y或結(jié)點(diǎn)y的子樹個數(shù)<i-1，則空操作。(8)刪除子樹操作delchild(x,i)。刪除結(jié)點(diǎn)x的第i棵子樹。若無結(jié)點(diǎn)x或結(jié)點(diǎn)x的子樹個數(shù)<i，則空操作。(9)遍歷樹traverse(T)。按某個次序依次訪問樹中各個結(jié)點(diǎn)，并使每個結(jié)點(diǎn)只被訪問一次。4/21/20237第7頁，共75頁，2023年，2月20日，星期六4.2二叉樹4.2.1二叉樹的概念每個結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），且二叉樹的子樹有左右之分，其次序不能任意顛倒ADEBCFHIGJK左子樹右子樹4/21/20238第8頁，共75頁，2023年，2月20日，星期六4.2.1二叉樹的概念二叉樹幾種基本形態(tài)：(a)空二又樹(b)僅有根結(jié)點(diǎn)的二叉樹(c)只有右子樹(d)左、右于樹均非空的二叉樹(e)只有左于樹4/21/20239第9頁，共75頁，2023年，2月20日，星期六4.2.1二叉樹的概念二叉樹的基本操作：(1)求根結(jié)點(diǎn)ROOT(BT)或ROOT(x)。求二叉樹BT的根結(jié)點(diǎn)或求結(jié)點(diǎn)x所在二叉樹的根結(jié)點(diǎn)。若BT是空樹或x不在任何二叉樹上，則函數(shù)值為“空”。(2)求雙親結(jié)點(diǎn)PARENT(BT,x)。求二叉樹BT中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn)x是二叉樹BT的根結(jié)點(diǎn)或二叉樹BT中無x結(jié)點(diǎn)，則函數(shù)值為“空”。(3)求孩子（左孩子、右孩子）結(jié)點(diǎn)LCHILD(BT,x)和RCHILD(BT,x)。分別求二叉樹BT中結(jié)點(diǎn)x的左孩子和右孩子結(jié)點(diǎn)。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或不在二叉樹BT中，則函數(shù)值為“空”。(4)初始化二叉樹setnull(BT)。置BT為空樹。(5)建樹二叉樹CRT_BT(x,LBT,RBT)。生成一棵以結(jié)點(diǎn)x為根、二叉樹LBT和RBT分別為左、右子樹的二叉樹。4/21/202310第10頁，共75頁，2023年，2月20日，星期六4.2.1二叉樹的概念二叉樹的基本操作：(6)插入子樹（左、右子樹）INS_LCHILD(BT,y,x)和INS_RCHILD(BT,y,x)。將以結(jié)點(diǎn)x為根且右子樹為空的二叉樹分別置為二叉樹BT中結(jié)點(diǎn)y的左子樹和右子樹。若結(jié)點(diǎn)y有左子樹／右子樹，則插入后是結(jié)點(diǎn)x的右子樹。(7)刪除子樹（左、右子樹）DEL_LCHILD(BT,x)和DEL_RCHILD(BT,x)。分別刪除二叉樹中以結(jié)點(diǎn)x為根的左子樹或右子樹。若x無左子樹或右子樹，則空操作。(8)遍歷二叉樹TRAVERSE(BT)。按某個次序依次訪問二叉樹中各個結(jié)點(diǎn)，并使每個結(jié)點(diǎn)只被訪問一次。4/21/202311第11頁，共75頁，2023年，2月20日，星期六4.2.2二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)(i≥1)。ADEBCFHIGJK20LMNO2122234/21/202312第12頁，共75頁，2023年，2月20日，星期六4.2.2二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)(k≥1),最大結(jié)點(diǎn)數(shù)=20+21+…2K-1=2k-1ADEBCFHIGJKLMNO4/21/202313第13頁，共75頁，2023年，2月20日，星期六4.2.2二叉樹的性質(zhì)性質(zhì)3：對于任何一棵二叉樹T，若其葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則n0=n2+1ADEBCFIGKM設(shè)二叉樹T中1度結(jié)點(diǎn)數(shù)為n1，則二叉樹T結(jié)點(diǎn)總數(shù)為：

n0+n1+n2；二叉樹的分枝總數(shù)為：

n1+2n2，顯然有：

n0+n1+n2=n1+2n2+1∴n0=n2+14/21/202314第14頁，共75頁，2023年，2月20日，星期六4.2.2二叉樹的性質(zhì)完全二叉樹和滿二叉樹

一棵深度為k且有2k-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹ADEBCFHIGJKL滿二叉樹ADEBCFHIGJKLMNO完全二叉樹4/21/202315第15頁，共75頁，2023年，2月20日，星期六二叉樹的特殊形態(tài)—完全二叉樹完全二叉樹是指深度為k的、有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)它的每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)。ADEBCFHIGJKL完全二叉樹ADEBCFHIGJKL非完全二叉樹4/21/202316第16頁，共75頁，2023年，2月20日，星期六4.2.2二叉樹的性質(zhì)性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為不大于log2n+1的整數(shù)

證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有

2k-1-1+1≤n≤2K-1

即:2k-1≤n＜2k

于是k-1≤log2n＜k∵k是整數(shù)∴k＝∟log2n⊿+1ADEBCFHGIJKLMNOADEBCFHG至少2k-1-1+1=2k-1至多2k-14/21/202317第17頁，共75頁，2023年，2月20日，星期六4.2.2二叉樹的性質(zhì)性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹，則對任一結(jié)點(diǎn)i(1≤i≤n)，有：ADEBCFHIGJKL123456789101112(1)如果i=1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親；如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)編號為i/2。(2)如果2i＜n，則結(jié)點(diǎn)i的左孩子編號為2i；否則無左孩子。(3)如果2i+1＜n，則結(jié)點(diǎn)i的右孩子編號為2i+1；否則無右孩子。(4)如果i為奇數(shù)且不為1，則結(jié)點(diǎn)i的左兄弟編號為i-1；否則無左兄弟。(5)如果i為偶數(shù)且小于n，則結(jié)點(diǎn)i的右兄弟編號為i+1；否則無右兄弟。4/21/202318第18頁，共75頁，2023年，2月20日，星期六4.2.3二叉樹的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)ADEBCFHIGJKL123456789101112ABCD…L適合于完全二叉樹4/21/202319第19頁，共75頁，2023年，2月20日，星期六4.2.3二叉樹的存儲結(jié)構(gòu)一般二叉樹的順序存儲結(jié)構(gòu)4/21/202320第20頁，共75頁，2023年，2月20日，星期六4.2.3二叉樹的存儲結(jié)構(gòu)（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)ADEBCFHIGJKL123456789101112ABCDtypedefstructbtnode{elemtpdata;structnode*lchild,*rchild;}bitnode;tpyedefbitnode*bitree4/21/202321第21頁，共75頁，2023年，2月20日，星期六4.2.3二叉樹的存儲結(jié)構(gòu)（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)如果經(jīng)常需要求雙親可以設(shè)置一指向雙親的指針左孩子數(shù)據(jù)右孩子雙親4/21/202322第22頁，共75頁，2023年，2月20日，星期六4.2.4二叉樹的簡單運(yùn)算實現(xiàn)（1）求根節(jié)點(diǎn)：elemtproot(bitreebt){if(bt==NULL)returnNULL;returnbt->data;}4/21/202323第23頁，共75頁，2023年，2月20日，星期六4.2.4二叉樹的簡單運(yùn)算實現(xiàn)（2）建立二叉樹操作bitreecreate(elemtypex,bitreelbt,bitreerbt)/*該運(yùn)算生成一棵以x為根結(jié)點(diǎn)，lbt和rbt分別為左右子樹的二叉樹*/{bitreep;p=(bitree)malloc(sizeof(bitnode));p->data=x;p->lchild=lbt;p->rchild=rbt;returnp;/*返回建成的二叉樹*/}4/21/202324第24頁，共75頁，2023年，2月20日，星期六4.2.4二叉樹的簡單運(yùn)算實現(xiàn)（3）插入左孩子：voidadd_lchild(bitreebt,elemtpx){bitreep;

p=(bitree)malloc(sizeof(bitnode));p->data=x;p->lchild=NULL;p->rchild=NULL;bt->lchild=p;/*插入bt的左孩子域*/}4/21/202325第25頁，共75頁，2023年，2月20日，星期六4.2.4二叉樹的簡單運(yùn)算實現(xiàn)（4）刪除左孩子：voiddelete_lchild(bitreebt){bitreep;p=bt->lchild;*保存左子樹指針*/bt->lchild=NULL;free(p);/*釋放左子樹空間*/}4/21/202326第26頁，共75頁，2023年，2月20日，星期六4.3二叉樹的遍歷二叉樹遍歷：即如何按某條搜索路徑巡訪樹中每個結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問—次．而且僅被訪問—次。主要有以下幾種：先序遍歷

中序遍歷

后序遍歷

層次遍歷

4/21/202327第27頁，共75頁，2023年，2月20日，星期六4.3二叉樹的遍歷先序遍歷若二叉樹為空，則空操作，否則，(1)訪問根結(jié)點(diǎn)；(2)先序遍歷左子樹；(3)先序遍歷右子樹ADEBCFHIGJKL123456789101112BDHIEJKGLFCA4/21/202328第28頁，共75頁，2023年，2月20日，星期六4.3二叉樹的遍歷中序遍歷若二叉樹為空，則空操作；否則，(1)中序遍歷左子樹；(2)訪問根結(jié)點(diǎn)，(3)中序遍歷右子樹。ADEBCFHIGJKL123456789101112DIBAJEKGCFLH4/21/202329第29頁，共75頁，2023年，2月20日，星期六4.3二叉樹的遍歷后序遍歷若二叉樹為空，則空操作；否則，(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問根結(jié)點(diǎn)。ADEBCFHIGJKL123456789101112IDJKEBLACGFH4/21/202330第30頁，共75頁，2023年，2月20日，星期六4.3二叉樹的遍歷層次遍歷：若二叉樹為空，則空操作；否則，從根結(jié)點(diǎn)開始，自頂向下訪問各層，從左到右訪問同一層的結(jié)點(diǎn)。ADEBCFHIGJKL123456789101112BCDEFGHLKJIA4/21/202331第31頁，共75頁，2023年，2月20日，星期六4.3.1遍歷二叉樹的遞歸算法（1）先序遍歷二叉鏈表的遞歸算法：voidpreorder(bitreebt){if(bt==NULL)return;/*遞歸結(jié)束條件*/else{printf(“%d\t”,bt->data);/*前序遍歷左子樹*/preorder(bt->lchild);/*前序遍歷右子樹*/preorder(bt->rchild);}}ADEBCFHIGJKL1234567891011124/21/202332第32頁，共75頁，2023年，2月20日，星期六4.3.1遍歷二叉樹的遞歸算法（1）先序遍歷二叉鏈表的遞歸算法：preorder(A){if(A==NULL)return;else{printf(“A”);preorder(B);preorder(C);}}preorder(B){if(B==NULL)return;else{printf(“B”);preorder(D);preorder(E);}}preorder(D){if(B==NULL)return;else{printf(“D”);preorder(H);preorder(I);}}preorder(H)4/21/202333第33頁，共75頁，2023年，2月20日，星期六4.3.1遍歷二叉樹的遞歸算法（2）中序遍歷二叉鏈表的遞歸算法：voidinorder(bitreebt){if(bt==NULL)return;/*遞歸結(jié)束條件*/else{/*中序遍歷左子樹*/inorder(bt->lchild);/*訪問根結(jié)點(diǎn)*/printf(“%d\t”,bt->data);/*中序遍歷右子樹*/inorder(bt->rchild);}}ADEBCFHIGJKL1234567891011124/21/202334第34頁，共75頁，2023年，2月20日，星期六4.3.1遍歷二叉樹的遞歸算法（3）后序遍歷二叉鏈表的遞歸算法：voidpostorder(bitreebt){if(bt==NULL)return;/*遞歸結(jié)束條件*/else{postorder(bt->lchild);/*后序遍歷左子樹*/postorder(bt->rchild);/*后序遍歷右子樹*/printf(“%d\t”,bt->data);/*訪問根結(jié)點(diǎn)*/}}ADEBCFHIGJKL1234567891011124/21/202335第35頁，共75頁，2023年，2月20日，星期六4.3.2遍歷二叉樹的非遞歸算法使用?；蜿犃校梢詫崿F(xiàn)二叉樹遍歷的非遞歸算法。（1）先序遍歷二叉鏈表的非遞歸算法：#defineMAXSIZE100voidnrpreorder(bitreebt){bitreestack[MAXSIZE],p;inttop=0;p=bt;do{while(p!=NULL){printf(“%d\t”,p->data);if(p->rchild!=NULL)/*如果右子樹不空*/stack[++top]=p->rchild;/*右孩子進(jìn)棧*/p=p->lchild;}if(top>0)p=stack[top--];}while(top>0);/*當(dāng)棧不空時繼續(xù)遍歷*/}ADEBCFHIGJKL123456789101112思路：沿左子樹一直深入，并把所遇到結(jié)點(diǎn)的非空右孩子進(jìn)棧；訪問完左孩子后，將右孩子出棧遍歷其右子樹。4/21/202336第36頁，共75頁，2023年，2月20日，星期六4.3.2遍歷二叉樹的非遞歸算法（2）中序遍歷二叉鏈表的非遞歸算法：#defineMAXSIZE100voidnrinorder(bitreebt){bitreestack[MAXSIZE],p;inttop=0;p=bt;do{while(p!=NULL){stack[++top]=p;/*所遇結(jié)點(diǎn)進(jìn)棧*/p=p->lchild;}/*繼續(xù)搜索p的左子樹*/if(top>0){p=stack[top--];/*出棧一個結(jié)點(diǎn)*/printf(“%d\t”,p->data);/*訪問結(jié)點(diǎn)*/p=p->rchild;}/*繼續(xù)搜索右子樹*/}while(top>0);}ADEBCFHIGJKL123456789101112思路：與前序遍歷類同，只是沿左子樹向下搜索的過程中先將所遇結(jié)點(diǎn)進(jìn)棧，待遍歷完左子樹返回時從棧頂退出結(jié)點(diǎn)并訪問，然后再遍歷右子樹。

4/21/202337第37頁，共75頁，2023年，2月20日，星期六4.3.2遍歷二叉樹的非遞歸算法（3）二叉樹的層次遍歷：voidlayer_travel_bitree(bitree*bt){bitree*p;//初始化隊列Q，隊列的元素為指向bitree結(jié)點(diǎn)的指針類型

init_Queue(Q);//根結(jié)點(diǎn)地址入隊in_queue(Q,bt);while(!queue_empty(Q)){p=out_queue(Q);//出隊

visit(p);//左孩子結(jié)點(diǎn)地址入隊

if(p->lp!=NULL)in_queue(Q,p->lp);//右孩子結(jié)點(diǎn)地址入隊

if(p->rp!=NULL)in_queue(Q,p->rp);}}ADEBCFHIGJKL1234567891011124/21/202338第38頁，共75頁，2023年，2月20日，星期六4.3.3遍歷序列與二叉樹的復(fù)原必需至少提供2個不同的遍歷序列，才能復(fù)原唯一的二叉樹。1.利用前序序列和中序序列恢復(fù)二叉樹例：前序ABDCEFG

中序DBAFEGC思路：前序序列確定根結(jié)點(diǎn)中序列確定左子樹和右子樹4/21/202339第39頁，共75頁，2023年，2月20日，星期六4.3.3遍歷序列與二叉樹的復(fù)原2.利用后序序列和中序序列恢復(fù)二叉樹例：后序DBFGECA

中序DBAFEGC思路：后序序列確定根結(jié)點(diǎn)中序序列確定左子樹和右子樹4/21/202340第40頁，共75頁，2023年，2月20日，星期六4.3.3遍歷序列與二叉樹的復(fù)原必需至少提供2個不同的遍歷序列，才能復(fù)原唯一的二叉樹。1.利用前序序列和中序序列恢復(fù)二叉樹例：前序ABDCEFG

中序DBAFEGC4/21/202341第41頁，共75頁，2023年，2月20日，星期六4.3.4基于遍歷的幾種二叉樹運(yùn)算的

實現(xiàn)和應(yīng)用舉例1.查找結(jié)點(diǎn)x的運(yùn)算2.求二叉樹中的葉子結(jié)點(diǎn)數(shù)目3.求二叉樹的高度4/21/202342第42頁，共75頁，2023年，2月20日，星期六1.查找結(jié)點(diǎn)x的運(yùn)算查找二叉樹bt中的結(jié)點(diǎn)x，可以結(jié)合在四種遍歷算法中的任何一個算法中進(jìn)行。在此我們以前序遍歷來實現(xiàn)查找運(yùn)算的遞歸算法。

bitreesearch(bitreebt,elemtypex){if(bt!=NULL){if(bt->data==x)returnbt;search(bt->lchild,x);/*在左子樹中查找*/search(bt->rchild,x);/*在右子樹中查找*/}elsereturnNULL;}4/21/202343第43頁，共75頁，2023年，2月20日，星期六2.求二叉樹中的葉子結(jié)點(diǎn)數(shù)目在遍歷過程中對所遇結(jié)點(diǎn)判斷是否為葉子結(jié)點(diǎn)，若是則統(tǒng)計變量加1，直到遍歷完所有結(jié)點(diǎn)，葉子結(jié)點(diǎn)總數(shù)即可求得。下面給出利用中序遍歷求葉子結(jié)點(diǎn)數(shù)的遞歸算法：intcountleaf(bitreebt){intnum=0;if(bt!=NULL)if((bt->lchild==NULL)&&(bt->rchild==NULL))num++;elsenum=countleaf(bt->lchild)+countleaf(bt->rchild);returnnum;}4/21/202344第44頁，共75頁，2023年，2月20日，星期六3.求二叉樹的高度可以在二叉樹的前序或后序遍歷過程中求出，下面給出的算法是在后序遍歷過程中求深度的遞歸算法。

inttreedepth(bitreebt){inth,lh,rh;if(bt==NULL)h=0;else{lh=treedepth(bt->lchild);/*左子樹高度賦lh*/rh=treedepth(bt->rchild);/*右子樹高度賦rh*/if(lh>=rh)h=lh+1;elseh=rh+1;}returnh;}4/21/202345第45頁，共75頁，2023年，2月20日，星期六4.4線索二叉樹4.4.1線索二叉樹的概念思考：二叉樹的遍歷產(chǎn)生了一線性序列,如何不再通過重新遍歷二叉樹,而能夠直接找到任一結(jié)點(diǎn)的前驅(qū)和后繼呢？ABCDEFGHI方法一：結(jié)點(diǎn)中增加指向前驅(qū)和后繼的指針左孩子前驅(qū)數(shù)據(jù)右孩子后繼缺點(diǎn)：空間利用率低4/21/202346第46頁，共75頁，2023年，2月20日，星期六4.4.1線索二叉樹的概念方法二：增加兩個標(biāo)志位rtag和ltag,利用現(xiàn)有的空指針域，n個結(jié)點(diǎn)的二叉樹必有n+1個空指針域左孩子ltag數(shù)據(jù)右孩子rtagABCDEFHI4/21/202347第47頁，共75頁，2023年，2月20日，星期六線索二叉樹的類型定義typedefenum{0,1}ptrtag;typedefstructbithnode{elemtypedata;structbithnode*lchild,*rchild;ptrtagltag,rtag;}bithrnode;typedefbithrnode*bithrtree;4/21/202348第48頁，共75頁，2023年，2月20日，星期六4.4.1線索二叉樹的概念中序線索二叉樹舉例中序序列DBHEIAFCGA00B00C00D11E00H11I11G11F1101二叉樹中序線索后的結(jié)果4/21/202349第49頁，共75頁，2023年，2月20日，星期六4.4.2線索二叉樹的構(gòu)造算法建立線索二叉樹的過程稱作對二叉樹線索化，線索化需要在遍歷的過程中來實現(xiàn)。在對二叉樹的某種次序遍歷過程中，一邊遍歷一邊建立線索，若當(dāng)前訪問結(jié)點(diǎn)的左孩子域為空則建立前趨線索，若右孩子域為空則建立后繼線索。為實現(xiàn)這一過程，可設(shè)指針pre指向剛剛訪問過的結(jié)點(diǎn)，指針p指向當(dāng)前結(jié)點(diǎn)，就可以方便前趨和后繼線索的填入。4/21/202350第50頁，共75頁，2023年，2月20日，星期六4.4.2線索二叉樹的構(gòu)造算法中序遍歷線索化二叉鏈表的算法：4/21/202351第51頁，共75頁，2023年，2月20日，星期六4.4.3線索二叉樹上的運(yùn)算實現(xiàn)遍歷中序線索二叉樹查找結(jié)點(diǎn)GA00B00C00D11E00H11I11G11F1101思路：先找到最左結(jié)點(diǎn)，然后不斷找后繼,直到回到頭結(jié)點(diǎn);查結(jié)點(diǎn)后繼時若遇到右孩子不為空時，后繼即為右子樹的最左下結(jié)點(diǎn)。t4/21/202352第52頁，共75頁，2023年，2月20日，星期六4.4.3線索二叉樹上的運(yùn)算實現(xiàn)例：中序線索二叉樹的中序遍歷：voidinorderthr(bithrtreet){bithrtreep;p=t->lchild;while(p!=t)/*空樹或遍歷結(jié)束時p=t*/{while(p->ltag==0)p=p->lchild;/*找最左下結(jié)點(diǎn)*/printf(“%d\t”,p->data);while((p->rtag==1)&&(p->rchild!=t)){p=p->rchild;printf(“%d\t”,p->data);}p=p->rchild;}}4/21/202353第53頁，共75頁，2023年，2月20日，星期六4.5樹和森林4.5.1樹和森林的存儲結(jié)構(gòu)1、雙親表示法0A-11B02D03C04I15J16…7G38K6ADEBCFHIGJKL4/21/202354第54頁，共75頁，2023年，2月20日，星期六4.5.1樹和森林的存儲結(jié)構(gòu)結(jié)點(diǎn)定義:typedefstructnode{elemtpdata;intparent;//指示雙親結(jié)點(diǎn)的下標(biāo)

}typedefstruct{nodetree[maxlen];intnum;//結(jié)點(diǎn)個數(shù)

}tree_parent;1、雙親表示法0A-11B02D03C04I15J16…7G38K64/21/202355第55頁，共75頁，2023年，2月20日，星期六4.5.1樹和森林的存儲結(jié)構(gòu)2、孩子表示法ABDC…GKADEBCFHIGJKLBDCIJEFLGH4/21/202356第56頁，共75頁，2023年，2月20日，星期六4.5.1樹和森林的存儲結(jié)構(gòu)3、孩子兄弟表示法AADEBCFHGJLBDCJEHFLGtypedefstructcsnode{elemtpdata;structcsnode*first,*next;}cstree;4/21/202357第57頁，共75頁，2023年，2月20日，星期六4.5.2樹和森林與二叉樹之間的轉(zhuǎn)換1.森林轉(zhuǎn)換成二叉樹例ADEBCFHIGJ方法：依次將每棵樹都轉(zhuǎn)換成二叉樹；最后將每棵樹作為前一棵二叉樹的右子樹；每棵樹轉(zhuǎn)換法則：將根結(jié)點(diǎn)第一個孩子轉(zhuǎn)為其左孩子，其他孩子轉(zhuǎn)換為第一個孩子的右邊孩子；4/21/202358第58頁，共75頁，2023年，2月20日，星期六4.5.2樹和森林與二叉樹之間的轉(zhuǎn)換2.二叉樹轉(zhuǎn)換成森林ACBDEFGHIJ逆過程，主要時將右子樹斷開，斷開的原則時其左孩子不為空4/21/202359第59頁，共75頁，2023年，2月20日，星期六4.5.3樹和森林的遍歷由樹的結(jié)構(gòu)定義可以引出樹的兩種遍歷：先（根）序遍歷：先訪問根結(jié)點(diǎn)，然后先序遍歷每棵子樹；對應(yīng)于二叉樹的先根序遍歷。ACBGDHJIFE先根序遍歷序列是：A,B,E,F,C,G,D,H,I,J,KK4/21/202360第60頁，共75頁，2023年，2月20日，星期六4.5.3樹和森林的遍歷后（根）序遍歷：先依此后序遍歷每棵子樹，然后訪問根結(jié)點(diǎn)。對應(yīng)二叉樹的中根序遍歷。ACBGDHJIFE先根序遍歷序列是：E,F,B,G,C,I,J,K,H,D,AK4/21/202361第61頁，共75頁，2023年，2月20日，星期六4.6哈夫曼樹4.6.1哈夫曼樹的概念及其構(gòu)造算法10856721.路徑和路徑長度2.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度3.樹的帶權(quán)路徑長度WPL=帶權(quán)樹4/21/202362第62頁，共75頁，2023年，2月20日，星期六4.6.1哈夫曼樹的概念及其構(gòu)造算法4.哈夫曼樹:最優(yōu)二叉樹，帶權(quán)路徑長度最小的樹例：葉子結(jié)點(diǎn)的權(quán)為7,5,2,47524247575244/21/202363第63頁，共75頁，2023年，2月20日，星期六4.6.1哈夫曼樹的概念及其構(gòu)造算法5.哈夫曼算法Huffman給出了一個建立哈夫曼樹的算法：例：2，6，6，8，12，14286681412201428484/21/202364第64頁，共75頁，2023年，2月20日，星期六4.6.2哈夫曼樹的應(yīng)用——哈夫曼編碼傳送的電文為'ABACCDA‘(1)定長編碼：A,B,C,D編碼為00,01,10,11傳輸?shù)拈L度為總長14位(2)可變長編碼:A,B,C,D編碼為0,00,1,01傳輸?shù)拈L度為總長9位,但卻無法譯碼(3)使用可變長編碼的前綴編碼，使每個符號唯一編碼,用哈夫曼樹構(gòu)造最短的前綴編碼.4/21/202365第65頁，共75頁，2023年，2月20日，星期六4.6.2哈夫曼樹的應(yīng)用——哈夫曼編碼例：字符集a,b,c,d,e字符出現(xiàn)的次數(shù)為6,4,1,10,5，請對它們進(jìn)行哈夫曼編碼1546510101626cbead011110004/21/202366第66頁，共75頁，2023年，2月20日，星期六4.6.3哈夫曼算法的靜態(tài)實現(xiàn)1.二叉樹的靜態(tài)鏈表實現(xiàn)0A12-11B3402C5603D7814E-1-116…7H-1-138I-1-13ADEBCFHIGLCHILDRCHILDPARENT4/21/202367第67頁，共75頁，2023年，2月20日，星期六2.哈夫曼樹的靜態(tài)實現(xiàn)cbaed260c-1-1511b-1-1542e-1-1653a-1-1764d-1-171051465652810734816867-126哈夫曼樹的靜態(tài)存儲結(jié)構(gòu)16105514610左右雙親權(quán)4/21/202368第68頁，共75頁，2023年，2月20日，星期六2.哈夫曼樹的靜態(tài)實現(xiàn)0c-1-1511b-1-1542e-1-1653a-1-1764d-1-171051465652810734816867-126左右雙親權(quán)哈夫曼樹的類型定義#definemaxnodenumber100typedefstruct{intweight;intparent,lchild,rchild;}htnode;/*定義結(jié)點(diǎn)類型*/定義哈夫曼樹類型typedefhtnode*huffmantree;

定義哈夫曼樹的存儲區(qū)域htnodeht[maxnodenumber];

4/21/202369第69頁，共75頁，2023年，2月20日，星期六2.哈夫曼樹的靜態(tài)實現(xiàn)0-1-1-101-1-1-102-1-1-103-1-1-104-1-1-105-1-1-106-1-1-107-1-1-108-1-1-10左右雙親權(quán)哈夫曼樹的創(chuàng)建過程例：a,b,c,d,e:6,4,1,10,5641510521551045661603772667884/21/202370第70頁，共75頁，2023年，2月20日，星期六3.哈夫曼編碼的實現(xiàn)思考：如何從已知的哈夫曼樹得出哈夫曼編碼