數據結構第六章第一頁，共三十九頁，2022年，8月28日1主要討論的問題：樹的定義；二叉樹的定義與性質,二叉樹的遍歷,線索二叉樹,樹與森林哈夫曼樹及應用.§6.1樹的定義與基本術語.回憶線性結構的特點.

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

顯然：上述樹的定義是一個遞歸定義。第三頁，共三十九頁，2022年，8月28日3.常用術語與基本概念.結點的度、樹的度、葉子結點、分支結點.

.內部結點、結點的孩子、兄弟、結點的祖先、結點的子孫、結點的層次..樹的深度、無序樹、有序樹、森林.

第四頁，共三十九頁，2022年，8月28日4§6.2二叉樹.二叉樹的定義是由n(n>=0)個結點的有限集合，它或為空樹(n=0),或由一個根結點和至多兩棵稱為根的左子樹和右子樹的互不相交的二叉樹組成..結論:二叉樹中不存在度大于2的結點，并且二叉樹的子樹有左子樹和右子樹之分.即二叉樹是度不大于2的有序樹..

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

?

?+1續證i>1的情形第十一頁，共三十九頁，2022年，8月28日11性質5的證明（續）：

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

?+1由二叉樹的性質二可得:第j-1層最后一個結點為2j-1-1;又根據完全二叉樹的特點知:第j層的第一個結點應為i=2j-1-1+1=2j-1.又因為i的左孩必為第j+1層的第一個結點，顯然其編號應為（2j-1）+1即2j.因為2j=2*2j-1=2i（i為2j-1）續證i>1的情形第十二頁，共三十九頁，2022年，8月28日12j-1jj+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1….….kk-1.…

?

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

}分析:二叉樹后序遍歷的應用..查閱資料:求二叉樹高度,度為0/1/2結點個數,判斷二叉樹相等,實現二叉樹復制等.(檢查)第二十三頁，共三十九頁，2022年，8月28日23.二叉樹遍歷非遞歸算法.先序遍歷的非遞歸算法分析：各階段棧的內容及輸出情況．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;//右孩子進棧}}}第二十四頁，共三十九頁，2022年，8月28日24例6要求二叉樹按二叉鏈表形式存儲，(1)寫一個建立二叉樹的算法.(2)寫一個判別給定的二叉樹是否是完全二叉樹的算法..同理,模仿上例查閱資料寫出中序遍歷與后序遍歷的非遞歸算法.(檢查)分析:判定是否是完全二叉樹，可以使用隊列，在遍歷中利用完全二叉樹“若某結點無左子女就不應有右子女”的原則進行判斷。第二十五頁，共三十九頁，2022年，8月28日25即:1.當檢查當某個接點只有右孩子時,則退出.

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

第二十六頁，共三十九頁，2022年，8月28日26intJudgeComplete(BiTreebt){inttag=0;BiTreep=bt,Q[];//根結點不標記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;//前面有結點無右孩子①elsetag=1;if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入隊elseif(p->rchild)//前面有結點無左孩子②return0;elsetag=1;

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

q=p->rchild;}第三十三頁，共三十九頁，2022年，8月28日33.樹的存儲.雙親表示法(自學)，孩子表示法(自學)，孩子兄弟表示法(二叉樹表示法)．§6.4樹和森林.孩子兄弟表示法存儲示意圖.森林與二叉樹的轉換.樹與二叉樹的轉換.方法：

1)對每個孩子進行自左至右的排序；2)在兄弟之間加一條虛線；3)對每個結點，除了左孩子外，去除其與其余孩子之間的聯系；4)以根結點為軸心，將整個樹順時針轉45度(實線在左，虛線在右)。第三十四頁，共三十九頁，2022年，8月28日34.樹由幾部分組成？.樹由根與去除根外的子樹森林兩部分組成.樹的遍歷.樹的遍歷：先序遍歷與后序遍歷．