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

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