數(shù)據(jù)結(jié)構(gòu)第六章

數(shù)據(jù)結(jié)構(gòu)第六章1第一頁(yè)，共三十九頁(yè)，編輯于2023年，星期三主要討論的問(wèn)題：樹(shù)的定義；二叉樹(shù)的定義與性質(zhì),二叉樹(shù)的遍歷,線索二叉樹(shù),樹(shù)與森林哈夫曼樹(shù)及應(yīng)用.§6.1樹(shù)的定義與基本術(shù)語(yǔ).回憶線性結(jié)構(gòu)的特點(diǎn).

.非線性結(jié)構(gòu)的特點(diǎn):至少存在一個(gè)數(shù)據(jù)元素有兩個(gè)或兩個(gè)以上的直接前驅(qū)（或直接后繼）元素的數(shù)據(jù)結(jié)構(gòu)..人類的族譜、各種社會(huì)關(guān)系、各類分類編碼；操作系統(tǒng)的文件系統(tǒng)、編譯程序的語(yǔ)法樹(shù)；Internet中的DNS（域名系統(tǒng)）-----層次結(jié)構(gòu)第二頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.樹(shù)的定義(遞歸定義)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合T，對(duì)于任意一棵非空樹(shù)，它滿足：(1)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。(2)當(dāng)n＞1時(shí)，其余結(jié)點(diǎn)可分為m(m＞0)個(gè)互不相交的有限集T1，T2，….，Tm，其中每個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)。

顯然：上述樹(shù)的定義是一個(gè)遞歸定義。3第三頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.常用術(shù)語(yǔ)與基本概念.結(jié)點(diǎn)的度、樹(shù)的度、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn).

.內(nèi)部結(jié)點(diǎn)、結(jié)點(diǎn)的孩子、兄弟、結(jié)點(diǎn)的祖先、結(jié)點(diǎn)的子孫、結(jié)點(diǎn)的層次..樹(shù)的深度、無(wú)序樹(shù)、有序樹(shù)、森林.

4第四頁(yè)，共三十九頁(yè)，編輯于2023年，星期三§6.2二叉樹(shù).二叉樹(shù)的定義是由n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諛?shù)(n=0),或由一個(gè)根結(jié)點(diǎn)和至多兩棵稱為根的左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)組成..結(jié)論:二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)，并且二叉樹(shù)的子樹(shù)有左子樹(shù)和右子樹(shù)之分.即二叉樹(shù)是度不大于2的有序樹(shù)..

二叉樹(shù)的五種形態(tài).5第五頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.二叉樹(shù)的性質(zhì)性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)(i>=1).性質(zhì)2:高度為k的二叉樹(shù)中至多有2k-1個(gè)結(jié)點(diǎn)(k>=1).性質(zhì)3:在任意一棵二叉樹(shù)中,若其葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則有：n0=n2+1.性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為6第六頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.滿二叉樹(shù)是指高度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)..特點(diǎn)：每一層上都有含有最大結(jié)點(diǎn)數(shù)..結(jié)點(diǎn)編號(hào):從上到下,從左到右按自然數(shù)編號(hào)..完全二叉樹(shù)高度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)是一棵完全二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與高度為k的滿二叉樹(shù)中層次編號(hào)1--n相對(duì)應(yīng).7第七頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.完全二叉樹(shù)的特點(diǎn)1)除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都有集中在該層最左邊的若干位置.2)葉子結(jié)點(diǎn)只可能在層次最大的兩層出現(xiàn).3)對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為k，則其左分支下的子孫的最大層次為k或k+1.性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為8第八頁(yè)，共三十九頁(yè)，編輯于2023年，星期三性質(zhì)5:對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)(從上到下,自左到右)對(duì)任一結(jié)點(diǎn)i(1<=i<=n),有如下三個(gè)性質(zhì)：(1)若i=1(根結(jié)點(diǎn))，則i無(wú)雙親；若i＞1，則i的雙親為(2)若i≤n/2，結(jié)點(diǎn)i的左孩子是結(jié)點(diǎn)2i；否則(即2i>n)，若i＞n/2，則i無(wú)左孩子。(3)若i≤(n-1)/2，結(jié)點(diǎn)i的或孩子是結(jié)點(diǎn)2i+1;否則(即2i+1>n),結(jié)點(diǎn)i無(wú)右孩。9第九頁(yè)，共三十九頁(yè)，編輯于2023年，星期三性質(zhì)5的證明:對(duì)i=1,由完全二叉樹(shù)定義知，其左孩為結(jié)2，右孩為結(jié)點(diǎn)3；若2>n(即2i>n)，顯然結(jié)點(diǎn)2不存在，即此時(shí)i無(wú)左孩；若3>n（即2i+1>n），則結(jié)點(diǎn)3不存在。由此：對(duì)于i=1時(shí)，上述性質(zhì)(2),(3)成立。后續(xù)證明i>1的情形10第十頁(yè)，共三十九頁(yè)，編輯于2023年，星期三性質(zhì)5的證明(續(xù)):對(duì)i>1,將結(jié)點(diǎn)i處于某層第一個(gè)結(jié)點(diǎn)和該層任意一個(gè)結(jié)點(diǎn)兩種情形分別證明:情況一：設(shè)結(jié)點(diǎn)i為第j層()的第一個(gè)結(jié)點(diǎn).j-1jj+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1….….kk-1.…

?

?+1續(xù)證i>1的情形11第十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期三性質(zhì)5的證明（續(xù)）：

?j-1jj+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1….….kk-1.…

?+1由二叉樹(shù)的性質(zhì)二可得:第j-1層最后一個(gè)結(jié)點(diǎn)為2j-1-1;又根據(jù)完全二叉樹(shù)的特點(diǎn)知:第j層的第一個(gè)結(jié)點(diǎn)應(yīng)為i=2j-1-1+1=2j-1.又因?yàn)閕的左孩必為第j+1層的第一個(gè)結(jié)點(diǎn)，顯然其編號(hào)應(yīng)為（2j-1）+1即2j.因?yàn)?j=2*2j-1=2i（i為2j-1）續(xù)證i>1的情形12第十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期三j-1jj+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1….….kk-1.…

?

?+1所以當(dāng)2j>n（即2i>n）時(shí)，編號(hào)為2j的結(jié)點(diǎn)不存在，即：此時(shí)i必?zé)o左孩(因?yàn)樽疃嘀挥衝個(gè)結(jié)點(diǎn)).同理：結(jié)點(diǎn)i如有右孩，則其右孩必為第j+1層上的第二個(gè)結(jié)點(diǎn)，其編號(hào)為2i+1(即2j+1)否則,若2i+1>n,則i必?zé)o右孩.續(xù)證i>1的情形二性質(zhì)5的證明（續(xù)）：13第十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期三對(duì)于第j層的任意第k個(gè)結(jié)點(diǎn)，設(shè)上述(2),(3)的斷言成立，即對(duì)于任意的i=k,當(dāng)2j-1<k<2j-1時(shí)，若結(jié)點(diǎn)k有左孩，則必為2k；若結(jié)點(diǎn)k有右孩，則必為2k+1.由此：當(dāng)i=k+1(2j-1<k≤2j-1)時(shí)，由于k+1是k的右兄弟(若堂兄弟)，若k+1有左孩，則應(yīng)為2(k+1)，同理，如(k+1)結(jié)點(diǎn)有右孩，則應(yīng)為2(k+1)+1.而由完全二叉樹(shù)的特點(diǎn)知，這顯然是正確的，由此性質(zhì)五(2),(3)完全成立.2k2k+12k+2j-1jji=2j-1-1i=2j-12j=2i2j+1=2i+12j-1….….kk-1.…k+12k+3性質(zhì)5的證明（續(xù)）：14第十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例1:任意一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，已知它有m個(gè)葉子結(jié)點(diǎn)，試證明非葉子結(jié)點(diǎn)有(m-1)個(gè)度為2，其余度為1.例2:已知完全二叉樹(shù)的第七層有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多是多少.15第十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)．順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次自上而下，自左至右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素．結(jié)論：完全二叉樹(shù)適合于順序存儲(chǔ)結(jié)構(gòu)．．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表表示法16第十六頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例3.有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存放在一維數(shù)組A[1..n]中,試據(jù)此建立一棵用二叉鏈表表示的二叉樹(shù),根由tree指向.分析：1)樹(shù)的遞歸定義2)樹(shù)由幾部分組成？BiTreeCreat(ElemTypeA[],inti){BiTreetree;if(i<=n){tree=(BiTree)malloc(sizeof(BiNode));tree->data=A[i];if(2*i>n)tree->lchild=null；elsetree->lchild=Creat(A,2*i)；if(2*i+1>n)tree->rchild=null；elsetree->rchild=Creat(A,2*i+1)；}returntree；}17第十七頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例4要求二叉樹(shù)按二叉鏈表形式存儲(chǔ)，(1)寫(xiě)一個(gè)建立二叉樹(shù)的算法.(2)寫(xiě)一個(gè)判別給定的二叉樹(shù)是否是完全二叉樹(shù)的算法.BiTreeCreat(){ElemTypex；BiTreebt;scanf(“%d”,&x);//本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x==0)bt=null;elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode));bt->data=x;bt->lchild=creat();bt->rchild=creat();}elseerror(“輸入錯(cuò)誤”)；returnbt;｝18第十八頁(yè)，共三十九頁(yè)，編輯于2023年，星期三§6.3遍歷二叉樹(shù)和線索二叉樹(shù).遍歷二叉樹(shù)按某條搜索路徑訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次．.先左后右的搜索路徑/先右后左的搜索路徑..先左后右的搜索路徑有三種：先序遍歷，中序遍歷和后序遍歷．19第十九頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.按先序遍歷/中序遍歷/后序遍歷把非線性的二叉樹(shù)結(jié)構(gòu)變?yōu)榱司€性結(jié)構(gòu)．.那么，變換后的線性結(jié)構(gòu)能否恢復(fù)為原來(lái)的二叉樹(shù)？NO.先序遍歷與中序遍歷／中序遍歷和后序遍歷能唯一確定該二叉樹(shù)．20第二十頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例5.設(shè)一棵二叉樹(shù)的先序遍歷序列:ABDFCEGH,中序遍歷序列:BFDAGEHC，畫(huà)出這棵二叉樹(shù)．.二叉樹(shù)層次遍歷(廣度優(yōu)先遍歷).按以上的搜索路徑遍歷一棵二叉樹(shù)稱之為二叉樹(shù)的深度優(yōu)先遍歷．搜索路徑：從二叉樹(shù)的根開(kāi)始，自頂向下，同一層從左向右．21第二十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.二叉樹(shù)遍歷遞歸算法.先序遍歷的遞歸算法voidpreorder(BiTreetree){if(tree!=null)visit(tree->data);//訪問(wèn)二叉樹(shù)的結(jié)點(diǎn)preorder(tree->lchild);preorder(tree->rchild);}.同理,可寫(xiě)出中序遍歷和后序遍歷的遞歸算法22第二十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.二叉樹(shù)遍歷是二叉樹(shù)應(yīng)用的基礎(chǔ).例5.二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),設(shè)計(jì)遞歸算法求給定二叉樹(shù)的所有結(jié)點(diǎn)數(shù).intsize(BiTreetree){if(tree==null)return0;elsereturnsize(tree->lchild)+size(tree->rchild)+1;

}分析:二叉樹(shù)后序遍歷的應(yīng)用..查閱資料:求二叉樹(shù)高度,度為0/1/2結(jié)點(diǎn)個(gè)數(shù),判斷二叉樹(shù)相等,實(shí)現(xiàn)二叉樹(shù)復(fù)制等.(檢查)23第二十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.二叉樹(shù)遍歷非遞歸算法.先序遍歷的非遞歸算法分析：各階段棧的內(nèi)容及輸出情況．voidpreorder(BiTreep){BiTrees[Maxsize];inttop=0;while(p!=NULL||top){while(p!=NULL){visit(p->data);s[++top]=p;p=p->lchild;//左孩子進(jìn)棧}if(top!=0){p=s[top--];p=p->rchild;//右孩子進(jìn)棧}}}24第二十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例6要求二叉樹(shù)按二叉鏈表形式存儲(chǔ)，(1)寫(xiě)一個(gè)建立二叉樹(shù)的算法.(2)寫(xiě)一個(gè)判別給定的二叉樹(shù)是否是完全二叉樹(shù)的算法..同理,模仿上例查閱資料寫(xiě)出中序遍歷與后序遍歷的非遞歸算法.(檢查)分析:判定是否是完全二叉樹(shù)，可以使用隊(duì)列，在遍歷中利用完全二叉樹(shù)“若某結(jié)點(diǎn)無(wú)左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。25第二十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期三即:1.當(dāng)檢查當(dāng)某個(gè)接點(diǎn)只有右孩子時(shí),則退出.

2.當(dāng)檢查到某個(gè)接點(diǎn)只有左孩子或沒(méi)有孩子結(jié)點(diǎn),這時(shí)要保證隊(duì)列中后面的結(jié)點(diǎn)都沒(méi)有孩子,才是完全二叉樹(shù),所以要設(shè)置一個(gè)flag標(biāo)記.一旦發(fā)現(xiàn)這種情況，就標(biāo)記該結(jié)點(diǎn).根據(jù)flag判斷是否有孩子，如果有，那么就不是完全二叉樹(shù);如果隊(duì)列取空時(shí)，沒(méi)有出現(xiàn)有孩子的結(jié)點(diǎn)，那么就是完全二叉樹(shù)。

26第二十六頁(yè)，共三十九頁(yè)，編輯于2023年，星期三intJudgeComplete(BiTreebt){inttag=0;BiTreep=bt,Q[];//根結(jié)點(diǎn)不標(biāo)記if(p==null)return1;QueueInit(Q);QueueIn(Q,p);while(!QueueEmpty(Q))

{p=QueueOut(Q);//出隊(duì)if(p->lchild&&!tag)QueueIn(Q,p->lchild);//左子女入隊(duì)elseif(p->lchild)return0;//前面有結(jié)點(diǎn)無(wú)右孩子①elsetag=1;if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入隊(duì)elseif(p->rchild)//前面有結(jié)點(diǎn)無(wú)左孩子②return0;elsetag=1;

}return1;}27第二十七頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.線索二叉樹(shù).對(duì)于任意的二叉樹(shù)，采用二叉鏈表表示，有多少個(gè)空的指針域？.在遍歷二叉樹(shù)的過(guò)程中，利用這些空的指針域?qū)⒈闅v產(chǎn)生的線性序列的前驅(qū)與后繼保留下來(lái)．.改進(jìn)二叉鏈表的結(jié)構(gòu)．28第二十八頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.線索二叉樹(shù):加上線索的二叉樹(shù)．.線索：在線索鏈表中指向結(jié)點(diǎn)前驅(qū)和后繼的指針．.線索化：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程．.畫(huà)線索化二叉樹(shù)．.二叉樹(shù)線索化算法29第二十九頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例6.設(shè)有二叉樹(shù)BT，每個(gè)結(jié)點(diǎn)包括ltag，lchild，data，rchild，rtag五個(gè)字段，依次為左標(biāo)志、左兒子，數(shù)據(jù)，右兒子，右標(biāo)志．給出將二叉樹(shù)BT建成前序（即先序）線索二叉樹(shù)的遞歸算法.分析：對(duì)每個(gè)結(jié)點(diǎn)線索化時(shí)，應(yīng)知道其前驅(qū)和后繼的指針值．對(duì)于前驅(qū)結(jié)點(diǎn)的值，可設(shè)置一變量pre來(lái)記錄．對(duì)于其后繼結(jié)點(diǎn)的值，由于是按遍歷次序來(lái)進(jìn)行的．因此，在線索化該結(jié)點(diǎn)時(shí)還不知道，因而設(shè)置了也沒(méi)有意義..存在一個(gè)問(wèn)題即：線索化時(shí)只能進(jìn)行前趨線索化，后繼線索化無(wú)法進(jìn)行．.線索化分2步進(jìn)行：當(dāng)T為當(dāng)前結(jié)點(diǎn)時(shí)，可進(jìn)行前驅(qū)線索化，當(dāng)Ｔ的后繼為當(dāng)前結(jié)點(diǎn)時(shí)再對(duì)Ｔ進(jìn)行后繼線索化．30第三十頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.線索化分2步進(jìn)行：當(dāng)T為當(dāng)前結(jié)點(diǎn)時(shí)，可進(jìn)行前驅(qū)線索化，當(dāng)Ｔ的后繼為當(dāng)前結(jié)點(diǎn)時(shí)再對(duì)Ｔ進(jìn)行后繼線索化．.從另一角度:當(dāng)T為當(dāng)前結(jié)點(diǎn)時(shí)要完成兩個(gè)操作:T的前驅(qū)線索化(需要判斷條件),T的前驅(qū)結(jié)點(diǎn)(由pre指示)的后繼線索化和并為后繼結(jié)點(diǎn)的線索化做準(zhǔn)備.31第三十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期三BiThrTreepre=null;//設(shè)置前驅(qū)voidPreOrderThreat(BiThrTreeBT){if(BT!=null){if(BT->lchild==null){BT->ltag=1;BT->lchild=pre;}if(pre!=null&&pre->rtag==1)pre->rchild=BT;if(BT->rchild==null)BT->rtag=1;pre=BT;//前驅(qū)后移if(BT->ltag==0)PreOrderThreat(BT->lchild);PreOrderThreat(BT->rchild)}}32第三十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期三例7.設(shè)計(jì)算法求先序線索二叉樹(shù)中指針p所指結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)的指針.分析:若某一結(jié)點(diǎn)p有左孩子,則該結(jié)點(diǎn)的左孩子便是p的后繼;否則,p的右孩子便是它的后繼.BiTNode*PreNext(BiTNode*p){BiTNode*q;if(p->ltag==0)q=p->lchild;else

q=p->rchild;}33第三十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.樹(shù)的存儲(chǔ).雙親表示法(自學(xué))，孩子表示法(自學(xué))，孩子兄弟表示法(二叉樹(shù)表示法)．§6.4樹(shù)和森林.孩子兄弟表示法存儲(chǔ)示意圖.森林與二叉樹(shù)的轉(zhuǎn)換.樹(shù)與二叉樹(shù)的轉(zhuǎn)換.方法：

1)對(duì)每個(gè)孩子進(jìn)行自左至右的排序；2)在兄弟之間加一條虛線；3)對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系；4)以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)45度(實(shí)線在左，虛線在右)。34第三十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期三.樹(shù)由幾部分組成？.樹(shù)由根與去除根外的子樹(shù)森林兩部分組成.樹(shù)的遍歷.樹(shù)的遍歷：先序遍歷與后序遍歷．.森林的遍歷.森林由幾部分組成？.森林由三部分組成：第一棵樹(shù)的根，第一樹(shù)去除根后的子樹(shù)森林，其它樹(shù)組成的森林三部分組成．.森林的遍歷：先序遍