基本數(shù)據(jù)結(jié)構(gòu)0904數(shù)據(jù)結(jié)構(gòu)11樹B

傳智播客數(shù)據(jù)結(jié)構(gòu)教程（11）,講師：尹成QQ:77025077博客:,C/C+,算法+實戰(zhàn),傳智播客,高薪就業(yè),第2頁,2.二叉樹的性質(zhì)(3+2),性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點（i1）。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點（k0）。性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)n0必定為n21（即n0=n2+1）,上堂課內(nèi)容回顧,1.樹的基本知識,樹的定義、若干術(shù)語、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、基本運算,第3頁,對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質(zhì)：,性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為log2n1,性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點，其左孩子編號必為2i，其右孩子編號為2i1；其雙親的編號必為i/2（i1時為根,除外）。,第4頁,問:設(shè)一棵完全二叉樹具有1000個結(jié)點，則它有500個葉子結(jié)點，有499個度為2的結(jié)點，有1個結(jié)點只有非空左子樹，有0個結(jié)點只有非空右子樹。,法1：先求全部葉子數(shù)。n0489(末層)11(k-1層)=500個；法2：先求2度結(jié)點數(shù)。n2=255(k-2層)244(k-1層)=499個；這兩種方法的缺點：都要先計算樹的深度k=log2n1=10;,法3：無需求樹深k，便可快捷求出完全二叉樹的葉子數(shù)：n0=n/2/取大于n/2的最小整數(shù)值可由二叉樹性質(zhì)5輕松證明！(編號為i的結(jié)點，其孩子編號必為2i和2i+1),已知最后一個結(jié)點編號為n，則其雙親n/2肯定是最后一個非葉子結(jié)點。其編號之后的全部結(jié)點都是葉子了！故，n0=n-n/2=n/2,問:設(shè)一棵完全二叉樹具有n個結(jié)點,第一個葉子節(jié)點的編號是？第i個呢？,第5頁,問:設(shè)一棵完全二叉樹具有301個結(jié)點，則它有個度為2的結(jié)點，有個葉子結(jié)點，有個結(jié)點只有非空左子樹，有個結(jié)點只有非空右子樹，第21個葉子結(jié)點編號是。,舉一反三,第6頁,第6章樹和二叉樹（Treetypedefstructnodeintdata;tree_pointerleft_child,right_child;node;,則三種遍歷算法可寫出:,回憶2：遞歸的幾個基本特點：,longintfact(n)/求n!intn;longf;if(n1)f=n*fact(n-1);elsef=1;return(f);,第10頁,DLR(NODE*root)if(root)/非空二叉樹printf(“%d”,root-data);/訪問DDLR(root-lchild);/遞歸遍歷左子樹DLR(root-rchild);/遞歸遍歷右子樹,結(jié)點數(shù)據(jù)類型自定義typedefstructnodeintdata;structnodelchild,*rchild；NODE;NODE*root;,先序遍歷算法,第11頁,中序遍歷算法LDR(NODE*root)if(root!=NULL)LDR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);,后序遍歷算法LRD(NODE*root)if(root!=NULL)LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);,第12頁,對遍歷的分析：,1.從前面的三種遍歷算法可以知道：如果將printf語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。,從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。,第1次經(jīng)過時訪問先序遍歷第2次經(jīng)過時訪問中序遍歷第3次經(jīng)過時訪問后序遍歷,2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)/每個結(jié)點只訪問一次空間效率:O(n)/棧占用的最大輔助空間（精確值：樹深為k的遞歸遍歷需要k+1個輔助單元！）,除去printf的遍歷算法XX(NODE*root)if(root)XX(root-lchild);XX(root-rchild);,第13頁,voidtraversal(structnode*root)if(root)printf(“%c”,root-data);traversal(root-lchild);printf(“%c”,root-data);traversal(root-rchild);,遍歷增強版：右圖二叉樹執(zhí)行下列操作輸出序列是什么？,先序中序遍歷：,ABDDBEEACC,ABDDEEBCCA,先序后序遍歷呢？,第14頁,例：編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。,思路：輸出葉子結(jié)點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。,DLR_CountLeafNum(NODE*root)/采用中序遍歷的遞歸算法if(root)/非空二叉樹條件，還可寫成if(root!=NULL)if(!root-lchild,第15頁,注：要實現(xiàn)遍歷運算必須先把二叉樹存入機內(nèi)。,思路：利用前序遍歷來建樹（結(jié)點值陸續(xù)從鍵盤輸入，用DLR為宜）BintreecreateBTpre()BintreeT;charch;scanf(“%c”,思考：怎樣銷毀樹？采用哪種遍歷順序較好？如何用非遞歸算法建樹？,怎樣建樹？借助于哪種遍歷比較好？,AB#CD#E#F#GH#,第16頁,習(xí)題討論：,1.求二叉樹深度，或從x結(jié)點開始的子樹深度。P132算法思路：只查各結(jié)點后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。技巧：遞歸時應(yīng)當(dāng)從葉子開始向上計數(shù)，層深者保留。否則不易確定層數(shù)。2.按層次輸出二叉樹中所有結(jié)點。P129算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結(jié)點的指針是個好辦法，而不必拘泥于遞歸算法。技巧：當(dāng)根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩子出隊時又令它的左右孩子結(jié)點入隊，由此便可產(chǎn)生按層次輸出的效果。,第17頁,3.判別給定二叉樹是否為完全二叉樹（即順序二叉樹）。算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況(前k-1層都是滿的，且第k層左邊也滿）技巧:按層序遍歷方式，先把所有結(jié)點（不管當(dāng)前結(jié)點是否有左右孩子）都入隊列.若為完全二叉樹,則層序遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。,有獎?wù)骷?第18頁,特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？,【嚴題集6.31】證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。,例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。分析：由后序遍歷特征，根結(jié)點必在后序序列尾部（即A）；由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（即FHG）；繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。,第19頁,中序遍歷：BDCEAFHG后序遍歷：DECBHGFA,（BDCE）,（FHG）,A,B,F,（DCE）,（HG）,C,DE,G,H,A,B,B,F,F,此問題的遞歸算法該如何編制？,第20頁,先序遍歷：ABCDEFGH,后序遍歷：DECBHGFA,問：若已知先序和后序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？,先序ABC后序BCA可否唯一確定？,第21頁,voidtraversal(structnode*root)if(root)printf(“%c”,root-data);traversal(root-lchild);printf(