數(shù)據(jù)結(jié)構(gòu)與算法 第四章 樹(shù)與二叉樹(shù)

數(shù)據(jù)結(jié)構(gòu)與算法第四章樹(shù)與二叉樹(shù)7/24/20231第1頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月第4章樹(shù)與二叉樹(shù)4.1

樹(shù)的基本概念4.2二叉樹(shù)4.3

二叉樹(shù)的遍歷4.4

線索二叉樹(shù)4.5

樹(shù)和森林4.6

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

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

n1+2n2，顯然有：

n0+n1+n2=n1+2n2+1∴n0=n2+17/24/202314第14頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.2二叉樹(shù)的性質(zhì)完全二叉樹(shù)和滿二叉樹(shù)

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

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

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-17/24/202317第17頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.2二叉樹(shù)的性質(zhì)性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)，有：ADEBCFHIGJKL123456789101112(1)如果i=1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親；如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)編號(hào)為i/2。(2)如果2i＜n，則結(jié)點(diǎn)i的左孩子編號(hào)為2i；否則無(wú)左孩子。(3)如果2i+1＜n，則結(jié)點(diǎn)i的右孩子編號(hào)為2i+1；否則無(wú)右孩子。(4)如果i為奇數(shù)且不為1，則結(jié)點(diǎn)i的左兄弟編號(hào)為i-1；否則無(wú)左兄弟。(5)如果i為偶數(shù)且小于n，則結(jié)點(diǎn)i的右兄弟編號(hào)為i+1；否則無(wú)右兄弟。7/24/202318第18頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)ADEBCFHIGJKL123456789101112ABCD…L適合于完全二叉樹(shù)7/24/202319第19頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)7/24/202320第20頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)ADEBCFHIGJKL123456789101112ABCDtypedefstructbtnode{elemtpdata;structnode*lchild,*rchild;}bitnode;tpyedefbitnode*bitree7/24/202321第21頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如果經(jīng)常需要求雙親可以設(shè)置一指向雙親的指針左孩子數(shù)據(jù)右孩子雙親7/24/202322第22頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.4二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn)（1）求根節(jié)點(diǎn)：elemtproot(bitreebt){if(bt==NULL)returnNULL;returnbt->data;}7/24/202323第23頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.4二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn)（2）建立二叉樹(shù)操作bitreecreate(elemtypex,bitreelbt,bitreerbt)/*該運(yùn)算生成一棵以x為根結(jié)點(diǎn)，lbt和rbt分別為左右子樹(shù)的二叉樹(shù)*/{bitreep;p=(bitree)malloc(sizeof(bitnode));p->data=x;p->lchild=lbt;p->rchild=rbt;returnp;/*返回建成的二叉樹(shù)*/}7/24/202324第24頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.4二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(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的左孩子域*/}7/24/202325第25頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.2.4二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn)（4）刪除左孩子：voiddelete_lchild(bitreebt){bitreep;p=bt->lchild;*保存左子樹(shù)指針*/bt->lchild=NULL;free(p);/*釋放左子樹(shù)空間*/}7/24/202326第26頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3二叉樹(shù)的遍歷二叉樹(shù)遍歷：即如何按某條搜索路徑巡訪樹(shù)中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)—次．而且僅被訪問(wèn)—次。主要有以下幾種：先序遍歷

中序遍歷

后序遍歷

層次遍歷

7/24/202327第27頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3二叉樹(shù)的遍歷先序遍歷若二叉樹(shù)為空，則空操作，否則，(1)訪問(wèn)根結(jié)點(diǎn)；(2)先序遍歷左子樹(shù)；(3)先序遍歷右子樹(shù)ADEBCFHIGJKL123456789101112BDHIEJKGLFCA7/24/202328第28頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3二叉樹(shù)的遍歷中序遍歷若二叉樹(shù)為空，則空操作；否則，(1)中序遍歷左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)，(3)中序遍歷右子樹(shù)。ADEBCFHIGJKL123456789101112DIBAJEKGCFLH7/24/202329第29頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3二叉樹(shù)的遍歷后序遍歷若二叉樹(shù)為空，則空操作；否則，(1)后序遍歷左子樹(shù)；(2)后序遍歷右子樹(shù)；(3)訪問(wèn)根結(jié)點(diǎn)。ADEBCFHIGJKL123456789101112IDJKEBLACGFH7/24/202330第30頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3二叉樹(shù)的遍歷層次遍歷：若二叉樹(shù)為空，則空操作；否則，從根結(jié)點(diǎn)開(kāi)始，自頂向下訪問(wèn)各層，從左到右訪問(wèn)同一層的結(jié)點(diǎn)。ADEBCFHIGJKL123456789101112BCDEFGHLKJIA7/24/202331第31頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.1遍歷二叉樹(shù)的遞歸算法（1）先序遍歷二叉鏈表的遞歸算法：voidpreorder(bitreebt){if(bt==NULL)return;/*遞歸結(jié)束條件*/else{printf(“%d\t”,bt->data);/*前序遍歷左子樹(shù)*/preorder(bt->lchild);/*前序遍歷右子樹(shù)*/preorder(bt->rchild);}}ADEBCFHIGJKL1234567891011127/24/202332第32頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.1遍歷二叉樹(shù)的遞歸算法（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)7/24/202333第33頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.1遍歷二叉樹(shù)的遞歸算法（2）中序遍歷二叉鏈表的遞歸算法：voidinorder(bitreebt){if(bt==NULL)return;/*遞歸結(jié)束條件*/else{/*中序遍歷左子樹(shù)*/inorder(bt->lchild);/*訪問(wèn)根結(jié)點(diǎn)*/printf(“%d\t”,bt->data);/*中序遍歷右子樹(shù)*/inorder(bt->rchild);}}ADEBCFHIGJKL1234567891011127/24/202334第34頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.1遍歷二叉樹(shù)的遞歸算法（3）后序遍歷二叉鏈表的遞歸算法：voidpostorder(bitreebt){if(bt==NULL)return;/*遞歸結(jié)束條件*/else{postorder(bt->lchild);/*后序遍歷左子樹(shù)*/postorder(bt->rchild);/*后序遍歷右子樹(shù)*/printf(“%d\t”,bt->data);/*訪問(wèn)根結(jié)點(diǎn)*/}}ADEBCFHIGJKL1234567891011127/24/202335第35頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.2遍歷二叉樹(shù)的非遞歸算法使用?；蜿?duì)列，可以實(shí)現(xiàn)二叉樹(shù)遍歷的非遞歸算法。（1）先序遍歷二叉鏈表的非遞歸算法：#defineMAXSIZE100voidnrpreorder(bitreebt){bitreestack[MAXSIZE],p;inttop=0;p=bt;do{while(p!=NULL){printf(“%d\t”,p->data);if(p->rchild!=NULL)/*如果右子樹(shù)不空*/stack[++top]=p->rchild;/*右孩子進(jìn)棧*/p=p->lchild;}if(top>0)p=stack[top--];}while(top>0);/*當(dāng)棧不空時(shí)繼續(xù)遍歷*/}ADEBCFHIGJKL123456789101112思路：沿左子樹(shù)一直深入，并把所遇到結(jié)點(diǎn)的非空右孩子進(jìn)棧；訪問(wèn)完左孩子后，將右孩子出棧遍歷其右子樹(shù)。7/24/202336第36頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.2遍歷二叉樹(shù)的非遞歸算法（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的左子樹(shù)*/if(top>0){p=stack[top--];/*出棧一個(gè)結(jié)點(diǎn)*/printf(“%d\t”,p->data);/*訪問(wèn)結(jié)點(diǎn)*/p=p->rchild;}/*繼續(xù)搜索右子樹(shù)*/}while(top>0);}ADEBCFHIGJKL123456789101112思路：與前序遍歷類同，只是沿左子樹(shù)向下搜索的過(guò)程中先將所遇結(jié)點(diǎn)進(jìn)棧，待遍歷完左子樹(shù)返回時(shí)從棧頂退出結(jié)點(diǎn)并訪問(wèn)，然后再遍歷右子樹(shù)。

7/24/202337第37頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.2遍歷二叉樹(shù)的非遞歸算法（3）二叉樹(shù)的層次遍歷：voidlayer_travel_bitree(bitree*bt){bitree*p;//初始化隊(duì)列Q，隊(duì)列的元素為指向bitree結(jié)點(diǎn)的指針類型

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

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

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

if(p->rp!=NULL)in_queue(Q,p->rp);}}ADEBCFHIGJKL1234567891011127/24/202338第38頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.3遍歷序列與二叉樹(shù)的復(fù)原必需至少提供2個(gè)不同的遍歷序列，才能復(fù)原唯一的二叉樹(shù)。1.利用前序序列和中序序列恢復(fù)二叉樹(shù)例：前序ABDCEFG

中序DBAFEGC思路：前序序列確定根結(jié)點(diǎn)中序列確定左子樹(shù)和右子樹(shù)7/24/202339第39頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.3遍歷序列與二叉樹(shù)的復(fù)原2.利用后序序列和中序序列恢復(fù)二叉樹(shù)例：后序DBFGECA

中序DBAFEGC思路：后序序列確定根結(jié)點(diǎn)中序序列確定左子樹(shù)和右子樹(shù)7/24/202340第40頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.3遍歷序列與二叉樹(shù)的復(fù)原必需至少提供2個(gè)不同的遍歷序列，才能復(fù)原唯一的二叉樹(shù)。1.利用前序序列和中序序列恢復(fù)二叉樹(shù)例：前序ABDCEFG

中序DBAFEGC7/24/202341第41頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月4.3.4基于遍歷的幾種二叉樹(shù)運(yùn)算的

實(shí)現(xiàn)和應(yīng)用舉例1.查找結(jié)點(diǎn)x的運(yùn)算2.求二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)目3.求二叉樹(shù)的高度7/24/202342第42頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月1.查找結(jié)點(diǎn)x的運(yùn)算查找二叉樹(shù)bt中的結(jié)點(diǎn)x，可以結(jié)合在四種遍歷算法中的任何一個(gè)算法中進(jìn)行。在此我們以前序遍歷來(lái)實(shí)現(xiàn)查找運(yùn)算的遞歸算法。

bitreesearch(bitreebt,elemtypex){if(bt!=NULL){if(bt->data==x)returnbt;search(bt->lchild,x);/*在左子樹(shù)中查找*/search(bt->rchild,x);/*在右子樹(shù)中查找*/}elsereturnNULL;}7/24/202343第43頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月2.求二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)目在遍歷過(guò)程中對(duì)所遇結(jié)點(diǎn)判斷是否為葉子結(jié)點(diǎn)，若是則統(tǒng)計(jì)變量加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;}7/24/202344第44頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月3.求二叉樹(shù)的高度可以在二叉樹(shù)的前序或后序遍歷過(guò)程中求出，下面給出的算法是在后序遍歷過(guò)程中求深度的遞歸算法。

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

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

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

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

7/24/202369第69頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月2.哈夫曼樹(shù)的靜態(tài)實(shí)現(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)哈夫曼樹(shù)的創(chuàng)建過(guò)程例：a,b,c,d,e:6,4,1,10,5641510521551045661603772667887/24/202370第70頁(yè)，課件共75頁(yè)，創(chuàng)作于2023年2月3.哈夫曼編碼的實(shí)現(xiàn)思考：如何從已知的哈夫曼樹(shù)得出哈夫曼編碼提示：從葉子