數(shù)據(jù)結(jié)構(gòu)與算法b-2014年4月09日課堂

數(shù)據(jù)結(jié)構(gòu)與算二叉主講教 大4.1二叉樹(shù)的概4.2二叉樹(shù)的主要性4.3二叉樹(shù)的抽象數(shù)據(jù)類4.4周游二叉4.5二叉樹(shù)的實(shí)4.6二叉搜索4.7堆與優(yōu)先隊(duì)4.8Huffman編碼信息學(xué) Page4.2二叉樹(shù)的主要性滿二叉樹(shù)定理：非空滿二叉樹(shù)樹(shù)葉數(shù)等于其分支結(jié)點(diǎn)數(shù)加證明：設(shè)二叉樹(shù)結(jié)點(diǎn)數(shù)為n，葉結(jié)點(diǎn)數(shù)m，分支結(jié)點(diǎn)數(shù)為b。有n（總結(jié)點(diǎn)數(shù)=m（葉)+b（分支） (公式4.1)∵每個(gè)分支，恰有兩個(gè)子結(jié)點(diǎn)（滿），故有2*b條邊；一顆二叉樹(shù)，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都恰有一接父結(jié)點(diǎn)，故共有n-1條邊即n-1= (公式∴由(公式4.1)，(公式4.2)n-1=m+b-12b，得出m(葉)=b（分支）+1信息學(xué) Page4.2二叉樹(shù)的性質(zhì)(續(xù)滿二叉樹(shù)定理推論：一個(gè)非空二叉樹(shù)的空子樹(shù)(指針數(shù)目等于其結(jié)點(diǎn)數(shù)加1證明：1設(shè)二叉樹(shù)T，將其所有空子樹(shù)換為樹(shù)葉，記新的擴(kuò)充滿二叉樹(shù)為T(mén)’。原來(lái)T的結(jié)點(diǎn)現(xiàn)在是T’的分支結(jié)2根據(jù)滿二叉樹(shù)定理，新添加的樹(shù)葉數(shù)目等于T結(jié)點(diǎn)個(gè)數(shù)加1。而每個(gè)新添加的樹(shù)葉對(duì)應(yīng)T的一個(gè)空子因此:T中空子樹(shù)數(shù)目等于T中結(jié)點(diǎn)數(shù)加1信息學(xué) Page4.2二叉樹(shù)的性質(zhì)(續(xù)任何一顆二叉樹(shù)，度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)。證明：設(shè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0、1、2的結(jié)點(diǎn)數(shù)分別為=n0，1，2，則nn0n1 (公式n=e+1。由于這些邊是有度為1和2的的結(jié)點(diǎn)發(fā)出的，因此e=n1+2·n2于是:n=e+1=n1+2·n2+1 n0n1+=+2·n21=n21信息學(xué) Page4.2二叉樹(shù)的性質(zhì)(續(xù)信息學(xué) Page4.2二叉樹(shù)的性質(zhì)(續(xù)4.二叉樹(shù)的第i層（根為第0層，i≥0）最多5.高度為深度為1;只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)的高度為1，深度為0的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn)等比數(shù)列求和24+…)6.有n個(gè)結(jié)點(diǎn)（n>0）的完全二叉樹(shù)的高度為log2(n+1)(深度為log2(n+1)-1)信息學(xué) Page二叉樹(shù)的性質(zhì)(續(xù)6.有n個(gè)結(jié)點(diǎn)（n>0）的完全二叉樹(shù)的高度為(n+1)(深度為log2n+1)證明設(shè)所求完全二叉樹(shù)的高度為h它的前h1層都是滿的，最后一層可以滿，也可以不滿，由此得到如下不等式

性質(zhì)5：高度為k(深度為k-

-1＜n

h-

度為1，深度為0)的二叉樹(shù)可變換為2h-1＜n+1取對(duì)數(shù)后得到:h-1＜log2(n+1

信息學(xué) Page大4.1二叉樹(shù)的概4.2二叉樹(shù)的主要性4.3二叉樹(shù)的抽象數(shù)據(jù)類4.4周游二叉4.5二叉樹(shù)的實(shí)4.6二叉搜索4.7堆與優(yōu)先隊(duì)4.8Huffman編碼信息學(xué) Page二叉樹(shù)的抽象數(shù)據(jù)類之上的各種可能運(yùn)算，這些運(yùn)算應(yīng)該適合二叉樹(shù)的各種應(yīng)用：二叉樹(shù)的某些運(yùn)算是針對(duì)整棵樹(shù)初始化二叉合并兩棵二叉二叉樹(shù)的大部分運(yùn)算都是圍繞結(jié)點(diǎn)某個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)、右子結(jié)點(diǎn)、父結(jié)結(jié) 的數(shù)據(jù)信息學(xué) Page參數(shù)T的模板，T是 每個(gè)結(jié)點(diǎn)都有l(wèi)eftchild和rightchild左右子結(jié)點(diǎn)結(jié)另外每個(gè)結(jié)點(diǎn)還包含一個(gè)數(shù)據(jù)域value 信息學(xué) Page二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類template<classT>classBinaryTreeNode{//申明二叉樹(shù)為結(jié)點(diǎn)類的友元類，便 私有數(shù)據(jù)成friendclassTelement;//具體實(shí)現(xiàn)可以補(bǔ)充private的左、右子結(jié)點(diǎn)定信息學(xué) Page二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類 BinaryTreeNode(constT&ele);//拷貝構(gòu)造函BinaryTreeNode(constT&ele,BinaryTreeNode<T>*l,BinaryTreeNode<T>*r);Tvalue() //BinaryTreeNode<T>*leftchild()const;BinaryTreeNode<T>*rightchildconst;信息學(xué) Page二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類//設(shè)置當(dāng)前結(jié)點(diǎn)的左子voidsetLeftchild(BinaryTreeNode<T>*)//設(shè)置當(dāng)前結(jié)點(diǎn)的右子voidsetRightchild(BinaryTreeNode<T>*)//設(shè)置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)voidsetValue(constT&boolisLeaf()const;BinaryTreeNode<T>&operator=(constBinaryTreeNode<T>&信息學(xué) Page二叉樹(shù)的抽象數(shù)據(jù)類template<classclassBinaryTree//二叉樹(shù)根結(jié)點(diǎn)指BinaryTreeNode<T>*//從二叉樹(shù)的root結(jié)點(diǎn)開(kāi)始BinaryTreeNode<T>*GetParentBinaryTreeNode<T>*root,BinaryTreeNode<T>*current信息學(xué) Page二叉樹(shù)的抽象數(shù)據(jù)類 //構(gòu)造函~BinaryTree{DeleteBinaryTree(root);};//析構(gòu)函boolisEmpty //判定二叉樹(shù)//返回二叉樹(shù)根結(jié)BinaryTreeNode<T>*Root(){returnroot;//返回current結(jié)點(diǎn)的父結(jié)BinaryTreeNode<T>*ParentBinaryTreeNode<T>*LeftSiblingBinaryTreeNode<T>*信息學(xué) Page二叉樹(shù)的抽象數(shù)據(jù)類//返回current結(jié)點(diǎn)的右兄BinaryTreeNode<T>*BinaryTreeNode<T>*//以elem作為根結(jié)點(diǎn)，leftTree作為樹(shù)的左子樹(shù)voidCreateTree(constBinaryTreeNode<T>&elem,BinaryTree<T>&leftTree,BinaryTree<T>&rightTree);//刪除二叉樹(shù)或voidDeleteBinaryTree(BinaryTreeNode<T>*信息學(xué) Page二叉樹(shù)的抽象數(shù)據(jù)類//前序周游二叉樹(shù)或其子voidPreOrder(BinaryTreeNode<T>*//中序周游二叉樹(shù)或其子voidInOrder(BinaryTreeNode<T>*//后序周游二叉樹(shù)或其voidPostOrder(BinaryTreeNode<T>*//按層次周游二叉樹(shù)或其子voidLevelOrder(BinaryTreeNode<T>*信息學(xué) Page大4.1二叉樹(shù)的概4.2二叉樹(shù)的主要性4.3二叉樹(shù)的抽象數(shù)據(jù)類4.4周游二叉4.5二叉樹(shù)的實(shí)4.6二叉搜索4.7堆與優(yōu)先隊(duì)4.8Huffman編碼信息學(xué) Page周游二叉周游:系統(tǒng)地?cái)?shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn),且每個(gè)結(jié)點(diǎn)都正好被到一次。信息學(xué) Page二叉樹(shù)周4.4.1深度優(yōu)先周游二叉4.4.2非遞歸深度優(yōu)先周游二叉4.4.3廣度優(yōu)先周游二叉信息學(xué) Page4.4.1深度優(yōu)先周游二叉改變根結(jié)點(diǎn)的周游順序，得到以下三種方案①前序周游(NLR次序)： 信息學(xué) Page示深度周游如下二叉樹(shù)(先序信息學(xué) Page示深度周游如下二叉樹(shù)(中序信息學(xué) Page示深度周游如下二叉樹(shù)(后序信息學(xué) Page示深度周游二叉樹(shù)結(jié)序周游序周游序周游信息學(xué) Page深度優(yōu)先周游二叉（遞歸實(shí)現(xiàn)template<classvoid(BinaryTreeNode<T>*root){if(root!=NULL){ } 信息學(xué) Page二叉樹(shù)中遞歸調(diào)用示A

D

G

完成中 信息學(xué)

H

二叉樹(shù)后遞歸調(diào)用示

C

D

G

完成后 信息學(xué)

H

4.4周游二叉二叉樹(shù)周4.4.1深度優(yōu)先周游二叉4.4.2非遞歸深度優(yōu)先周游二叉4.4.3廣度優(yōu)先周游二叉信息學(xué) Page深度優(yōu)先周游二叉(非遞歸深度優(yōu)先二叉樹(shù)周游是遞歸定義的棧利用一個(gè)棧來(lái)記下尚待周游的結(jié)點(diǎn)或子樹(shù)以備以后 。信息學(xué) Page舉八皇后問(wèn)信息學(xué) Page舉八皇后問(wèn)信息學(xué) Page非遞歸中序周游二叉思想遇到一個(gè)結(jié)點(diǎn)，就把它推入棧中，并去周游它的左子 void信

PageSTL里的stack(需要包含＃include＜通過(guò)命名空間來(lái)區(qū)分不同的類或函數(shù)等，避免導(dǎo)致全局命名問(wèn)題。所謂命名空間，是一種將程序庫(kù)名稱封裝起來(lái){方法，像在各個(gè)程序庫(kù)中立起一道道圍墻usingstd::stack; stack<BinaryTreeNode<T>*aStack;BinaryTreeNode<T>*pointer=root;while(!aStack.empty()||pointer){if(pointer)//當(dāng) 結(jié)構(gòu)指向左孩 信息學(xué) Pageelse

//左子 完畢，轉(zhuǎn) 右子 當(dāng)前結(jié)}}//end 信息學(xué) Page非遞歸前序周游二叉思想遇到一個(gè)結(jié)點(diǎn)， 該結(jié)點(diǎn)，并把此結(jié)點(diǎn)推入棧中，然下降去周游它的左子樹(shù)周游完它的左子樹(shù)后，從棧頂托出這個(gè)結(jié)點(diǎn)，并按照它的右template<classvoid(BinaryTreeNode<T>*信息學(xué) Page{using //使用STL中的stack<BinaryTreeNode<T>*>aStack;BinaryTreeNode<T>*pointer=root;while(!aStack.empty()||pointer){if(pointer)Visit(pointer->value()); 當(dāng)前結(jié)//當(dāng) 結(jié)構(gòu)指向左孩pointer=pointer-}信息學(xué) Pageelse}

//左子 完畢，轉(zhuǎn) 右子//當(dāng) 結(jié)構(gòu)指向右孩pointer=pointer-//棧頂元素退}//end}信息學(xué) Page非遞歸后序周游二叉思想遇到一個(gè)結(jié)點(diǎn)，把它推入棧中，周游它的左子樹(shù)周游結(jié)束后，還不能 問(wèn)處于棧頂?shù)脑摻Y(jié)點(diǎn)再按照它的 結(jié)構(gòu)指示的地址去周游該結(jié)點(diǎn)的右子樹(shù)周游遍右子樹(shù)后才能從棧頂托出該結(jié)點(diǎn) 之信息學(xué) Page解決方案需要給棧中的每個(gè)元素加上一個(gè)特征位，以便欲從棧頂托出一個(gè)結(jié)點(diǎn)時(shí)區(qū)別是從棧頂元素左邊回來(lái)的則要繼續(xù)周游右子樹(shù)，還是從右邊回來(lái)的該結(jié)點(diǎn)的左、右子樹(shù)均已周游特征為L(zhǎng)ft征為Right表示已進(jìn)入該結(jié)點(diǎn)的右子樹(shù)，將從右邊回來(lái)。信息學(xué) Page定義棧中元素類enumTags{Left,Right}; template<classT>class //棧元素的定{//指向二叉樹(shù)結(jié)點(diǎn)BinaryTreeNode<T>*//特征標(biāo)識(shí)申Tags信息學(xué) Page非遞歸后序周游二叉樹(shù)實(shí)template<classvoid(BinaryTreeNode<T>*{usingstd::stack;//使用STL棧部分StackElement<T>ele