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

數(shù)據(jù)結(jié)構(gòu)第六章1第1頁，課件共39頁，創(chuàng)作于2023年2月主要討論的問題：樹的定義；二叉樹的定義與性質(zhì),二叉樹的遍歷,線索二叉樹,樹與森林哈夫曼樹及應用.§6.1樹的定義與基本術語.回憶線性結(jié)構(gòu)的特點.

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

顯然：上述樹的定義是一個遞歸定義。3第3頁，課件共39頁，創(chuàng)作于2023年2月.常用術語與基本概念.結(jié)點的度、樹的度、葉子結(jié)點、分支結(jié)點.

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

4第4頁，課件共39頁，創(chuàng)作于2023年2月§6.2二叉樹.二叉樹的定義是由n(n>=0)個結(jié)點的有限集合，它或為空樹(n=0),或由一個根結(jié)點和至多兩棵稱為根的左子樹和右子樹的互不相交的二叉樹組成..結(jié)論:二叉樹中不存在度大于2的結(jié)點，并且二叉樹的子樹有左子樹和右子樹之分.即二叉樹是度不大于2的有序樹..

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

?

?+1續(xù)證i>1的情形11第11頁，課件共39頁，創(chuàng)作于2023年2月性質(zhì)5的證明（續(xù)）：

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

?+1由二叉樹的性質(zhì)二可得:第j-1層最后一個結(jié)點為2j-1-1;又根據(jù)完全二叉樹的特點知:第j層的第一個結(jié)點應為i=2j-1-1+1=2j-1.又因為i的左孩必為第j+1層的第一個結(jié)點，顯然其編號應為（2j-1）+1即2j.因為2j=2*2j-1=2i（i為2j-1）續(xù)證i>1的情形12第12頁，課件共39頁，創(chuàng)作于2023年2月j-1jj+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1….….kk-1.…

?

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

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

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

26第26頁，課件共39頁，創(chuàng)作于2023年2月intJudgeComplete(BiTreebt){inttag=0;BiTreep=bt,Q[];//根結(jié)點不標記if(p==null)return1;QueueInit(Q);QueueIn(Q,p);while(!QueueEmpty(Q))

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

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

q=p->rchild;}33第33頁，課件共39頁，創(chuàng)作于2023年2月.樹的存儲.雙親表示法(自學)，孩子表示法(自學)，孩子兄弟表示法(二叉樹表示法)．§6.4樹和森林.孩子兄弟表示法存儲示意圖.森林與二叉樹的轉(zhuǎn)換.樹與二叉樹的轉(zhuǎn)換.方法：

1)對每個孩子進行自左至右的排序；2)在兄弟之間加一條虛線；3)對每個結(jié)點，除了左孩子外，去除其與其余孩子之間的聯(lián)系；4)以根結(jié)點為軸心，將整個樹順時針轉(zhuǎn)45度(實線在左，虛線在右)。34第34頁，課件共39頁，創(chuàng)作于2023年2月.樹由幾部分組成？.樹由根與去除根外的子樹森林兩部分組成.樹的遍歷.樹的遍歷：先序遍歷與后序遍歷．.森林的遍歷.森林由幾部分組成？.森林由三部分組成：第一棵樹的根，第一樹去除根后的子樹森林，其它樹組成的森林三部分組成．.森林的遍