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

數(shù)據(jù)結(jié)構(gòu)與算法

—二叉樹主講教員:段凌宇2014年4月09日

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2大綱4.1二叉樹的概念4.2二叉樹的主要性質(zhì)4.3二叉樹的抽象數(shù)據(jù)類型4.4周游二叉樹4.5二叉樹的實(shí)現(xiàn)4.6二叉搜索樹4.7堆與優(yōu)先隊(duì)列4.8Huffman編碼樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page34.2二叉樹的主要性質(zhì)1.滿二叉樹定理：非空滿二叉樹樹葉數(shù)等于其分支結(jié)點(diǎn)數(shù)加1

證明：設(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條邊；一顆二叉樹，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都恰有一條邊聯(lián)接父結(jié)點(diǎn)，故共有n-1條邊。即n-1=2b(公式4.2)∴由(公式4.1)，(公式4.2)得n-1=m+b-1=2b，得出m(葉)=b（分支）+1北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page44.2二叉樹的性質(zhì)(續(xù))2.滿二叉樹定理推論：一個(gè)非空二叉樹的空子樹(指針)數(shù)目等于其結(jié)點(diǎn)數(shù)加1。

證明：1)

設(shè)二叉樹T，將其所有空子樹換為樹葉，記新的擴(kuò)充滿二叉樹為T’。原來T的結(jié)點(diǎn)現(xiàn)在是T’的分支結(jié)點(diǎn)。

2)

根據(jù)滿二叉樹定理，新添加的樹葉數(shù)目等于T結(jié)點(diǎn)個(gè)數(shù)加1。而每個(gè)新添加的樹葉對(duì)應(yīng)T的一個(gè)空子樹。

因此:T中空子樹數(shù)目等于T中結(jié)點(diǎn)數(shù)加1。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page54.2二叉樹的性質(zhì)(續(xù))3.任何一顆二叉樹，度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)。

證明：設(shè)有n個(gè)結(jié)點(diǎn)的二叉樹的度為0、1、2的結(jié)點(diǎn)數(shù) 分別為=n0，n1，n2，則

n=n0+n1+n2 (公式4.3)

設(shè)邊數(shù)為e。因?yàn)槌酝?，每個(gè)結(jié)點(diǎn)都有一條邊進(jìn)入，故

n=e+1。由于這些邊是有度為1和2的的結(jié)點(diǎn)發(fā)出的， 因此e=n1+2·n2

于是:n=e+1=n1+2·n2+1（公式4.4）因此由公式（4.3)（4.4）得

n0+n1+n2=n1+2·n2+1

即n0=n2+1

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page64.2二叉樹的性質(zhì)(續(xù))二叉樹的高度定義為二叉樹中層數(shù)最大的葉結(jié)點(diǎn)的層數(shù)加1二叉樹的深度定義為二叉樹中層數(shù)最大的葉結(jié)點(diǎn)的層數(shù)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page74.2二叉樹的性質(zhì)(續(xù)）4.二叉樹的第i層（根為第0層，i≥0）最多有2i個(gè)結(jié)點(diǎn)。5.高度為k(深度為k-1;只有一個(gè)根結(jié)點(diǎn)的二叉樹的高度為1，深度為0)的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(等比數(shù)列求和:1+2+4+…)6.有n個(gè)結(jié)點(diǎn)（n>0）的完全二叉樹的高度為log2(n+1)(深度為log2(n+1)-1)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page84.2二叉樹的性質(zhì)(續(xù)）6.有n個(gè)結(jié)點(diǎn)（n>0）的完全二叉樹的高度為log2(n+1)(深度為log2(n+1)-1)證明：

設(shè)所求完全二叉樹的高度為h，由完全二叉樹的定義可知，它的前h-1層都是滿的，最后一層可以滿，也可以不滿，由此得到如下不等式：2h-1-1＜n≤2h-1可變換為：2h-1

＜n+1≤2h

取對(duì)數(shù)后得到:h-1＜log2(n+1)≤h即log2(n+1)≤h＜log2(n+1)+1性質(zhì)5：高度為k(深度為k-1;只有一個(gè)根結(jié)點(diǎn)的二叉樹的高度為1，深度為0)的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page9大綱4.1二叉樹的概念4.2二叉樹的主要性質(zhì)4.3二叉樹的抽象數(shù)據(jù)類型4.4周游二叉樹4.5二叉樹的實(shí)現(xiàn)4.6二叉搜索樹4.7堆與優(yōu)先隊(duì)列4.8Huffman編碼樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page104.3二叉樹的抽象數(shù)據(jù)類型定義了二叉樹的邏輯結(jié)構(gòu)之后，需要考慮在二叉樹邏輯結(jié)構(gòu)之上的各種可能運(yùn)算，這些運(yùn)算應(yīng)該適合二叉樹的各種應(yīng)用：二叉樹的某些運(yùn)算是針對(duì)整棵樹的初始化二叉樹合并兩棵二叉樹二叉樹的大部分運(yùn)算都是圍繞結(jié)點(diǎn)進(jìn)行的訪問某個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)、右子結(jié)點(diǎn)、父結(jié)點(diǎn)訪問結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11二叉樹結(jié)點(diǎn)抽象數(shù)據(jù)類型BinaryTreeNode是帶有參數(shù)T

的模板，T是存儲(chǔ)在結(jié)點(diǎn)中的數(shù)據(jù)類型每個(gè)結(jié)點(diǎn)都有l(wèi)eftchild和rightchild左右子結(jié)點(diǎn)結(jié)構(gòu)另外每個(gè)結(jié)點(diǎn)還包含一個(gè)數(shù)據(jù)域value。為了強(qiáng)調(diào)抽象數(shù)據(jù)類型與存儲(chǔ)無關(guān)，我們并沒有具體規(guī)定該抽象數(shù)據(jù)類型的存儲(chǔ)方式。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12二叉樹結(jié)點(diǎn)的抽象數(shù)據(jù)類型template<classT>classBinaryTreeNode{ //申明二叉樹為結(jié)點(diǎn)類的友元類，便于訪問私有數(shù)據(jù)成員

friendclassBinaryTree;

private://二叉樹結(jié)點(diǎn)數(shù)據(jù)域

Telement;//具體實(shí)現(xiàn)可以補(bǔ)充private的左、右子結(jié)點(diǎn)定義北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13二叉樹結(jié)點(diǎn)的抽象數(shù)據(jù)類型public: BinaryTreeNode(); //缺省構(gòu)造函數(shù)

BinaryTreeNode(constT&ele);//拷貝構(gòu)造函數(shù)

//給定了結(jié)點(diǎn)值和左右子樹的構(gòu)造函數(shù)

BinaryTreeNode(constT&ele, BinaryTreeNode<T>*l, BinaryTreeNode<T>*r); Tvalue()const;//返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)

//返回當(dāng)前結(jié)點(diǎn)指向的左子樹(指針) BinaryTreeNode<T>*leftchild()const;

//返回當(dāng)前結(jié)點(diǎn)指向的右子樹(指針) BinaryTreeNode<T>*rightchild()const; 北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page14二叉樹結(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&val); //判定當(dāng)前結(jié)點(diǎn)是否為葉結(jié)點(diǎn),若是返回true boolisLeaf()const;

//重載賦值操作符

BinaryTreeNode<T>&operator= (constBinaryTreeNode<T>&Node);};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15二叉樹的抽象數(shù)據(jù)類型

template<classT> classBinaryTree{

private:

//二叉樹根結(jié)點(diǎn)指針

BinaryTreeNode<T>*root; //從二叉樹的root結(jié)點(diǎn)開始，

//查找current結(jié)點(diǎn)的父結(jié)點(diǎn) BinaryTreeNode<T>*GetParent(BinaryTreeNode<T>*root, BinaryTreeNode<T>*current);

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16二叉樹的抽象數(shù)據(jù)類型public:BinaryTree(root=NULL); //構(gòu)造函數(shù)

~BinaryTree(){DeleteBinaryTree(root);};//析構(gòu)函數(shù)

boolisEmpty()const; //判定二叉樹是否為空樹

//返回二叉樹根結(jié)點(diǎn)

BinaryTreeNode<T>*Root(){returnroot;};

//返回current結(jié)點(diǎn)的父結(jié)點(diǎn)

BinaryTreeNode<T>*Parent(BinaryTreeNode<T>* current); //返回current結(jié)點(diǎn)的左兄弟

BinaryTreeNode<T>*LeftSibling( BinaryTreeNode<T>*current);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17二叉樹的抽象數(shù)據(jù)類型//返回current結(jié)點(diǎn)的右兄弟BinaryTreeNode<T>*RightSibling( BinaryTreeNode<T>*current);//以elem作為根結(jié)點(diǎn)，leftTree作為樹的左子樹,//rightTree作為樹的右子樹，構(gòu)造一棵新的二叉樹voidCreateTree(constBinaryTreeNode<T>&elem, BinaryTree<T>&leftTree, BinaryTree<T>&rightTree);//刪除二叉樹或其子樹voidDeleteBinaryTree(BinaryTreeNode<T>*root);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18二叉樹的抽象數(shù)據(jù)類型//前序周游二叉樹或其子樹voidPreOrder(BinaryTreeNode<T>*root)；//中序周游二叉樹或其子樹voidInOrder(BinaryTreeNode<T>*root)； //后序周游二叉樹或其子樹voidPostOrder(BinaryTreeNode<T>*root)；//按層次周游二叉樹或其子樹voidLevelOrder(BinaryTreeNode<T>*root)；};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page19大綱4.1二叉樹的概念4.2二叉樹的主要性質(zhì)4.3二叉樹的抽象數(shù)據(jù)類型4.4周游二叉樹4.5二叉樹的實(shí)現(xiàn)4.6二叉搜索樹4.7堆與優(yōu)先隊(duì)列4.8Huffman編碼樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page204.4周游二叉樹

周游:系統(tǒng)地訪問數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn),且每個(gè)結(jié)點(diǎn)都正好被訪問到一次。周游一棵二叉樹的過程實(shí)際上就是把二叉樹的結(jié)點(diǎn)放入一個(gè)線性序列的過程，或者說把二叉樹進(jìn)行線性化。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21二叉樹周游

4.4.1深度優(yōu)先周游二叉樹4.4.2非遞歸深度優(yōu)先周游二叉樹4.4.3廣度優(yōu)先周游二叉樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page224.4.1深度優(yōu)先周游二叉樹

改變根結(jié)點(diǎn)的周游順序，得到以下三種方案： ①前序周游(NLR次序)：訪問根結(jié)點(diǎn)；前 序周游左子樹；前序周游右子樹。

②中序周游(LNR次序)：中序周游左子 樹；訪問根結(jié)點(diǎn)；中序周游右子樹。

③后序周游(LRN次序)：后序周游左子 樹；后序周游右子樹；訪問根結(jié)點(diǎn)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page23示例深度周游如下二叉樹(先序)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24示例深度周游如下二叉樹(中序)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25示例深度周游如下二叉樹(后序)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26示例深度周游二叉樹結(jié)果①前序周游：ABDCEGFHI②中序周游：DBAEGCHFI③后序周游：DBGEHIFCA北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page27深度優(yōu)先周游二叉樹（遞歸實(shí)現(xiàn)）template<classT>voidBinaryTree<T>::DepthOrder(BinaryTreeNode<T>*root){

if(root!=NULL){ Visit(root); //前序

DepthOrder(root->leftchild());//訪問左子樹

Visit(root); //中序

DepthOrder(root->rightchild());//訪問右子樹

Visit(root); //后序

}}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page28二叉樹中序游歷

遞歸調(diào)用示例InOrderAInOrderBInOrderCInOrderDInOrderEInOrderFInOrderGInOrderHInOrderIVisit(A)Visit(B)Visit(C)Visit(D)InOrderNULLInOrderNULLVisit(E)InOrderNULLInOrderNULLVisit(F)InOrderNULLVisit(G)InOrderNULLInOrderNULLVisit(H)InOrderNULLInOrderNULLVisit(I)InOrderNULL完成中序游歷InOrder(A)中序周游：DBAEGCHFI北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page29二叉樹后序游歷

遞歸調(diào)用示例POrderAPOrderBPOrderCPOrderDPOrderEPOrderFPOrderGPOrderHPOrderIVisit(B)Visit(D)POrderNULLPOrderNULLVisit(E)POrderNULLPOrderNULLVisit(F)POrderNULLVisit(G)POrderNULLPOrderNULLVisit(H)POrderNULLPOrderNULLVisit(I)POrderNULL完成后序游歷POrder(A)后序周游：DBGEHIFCAVisit(C)Visit(A)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page304.4周游二叉樹

二叉樹周游4.4.1深度優(yōu)先周游二叉樹4.4.2非遞歸深度優(yōu)先周游二叉樹4.4.3廣度優(yōu)先周游二叉樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page31深度優(yōu)先周游二叉樹(非遞歸)深度優(yōu)先二叉樹周游是遞歸定義的；棧是實(shí)現(xiàn)遞歸的最常用的結(jié)構(gòu)；利用一個(gè)棧來記下尚待周游的結(jié)點(diǎn)或子樹，以備以后訪問。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page32舉例

八皇后問題系統(tǒng)地搜索問題的解深度優(yōu)先的方式搜索解空間問題的解空間通常是在搜索問題解的過程中動(dòng)態(tài)產(chǎn)生的工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止?；厮荼本┐髮W(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page33舉例

八皇后問題回溯回溯法在用來求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束?；厮莘ㄔ谟脕砬髥栴}的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。它適用于解一些組合數(shù)較大的問題。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page34非遞歸中序周游二叉樹思想：遇到一個(gè)結(jié)點(diǎn)，就把它推入棧中，并去周游它的左子樹周游完左子樹后，從棧頂托出這個(gè)結(jié)點(diǎn)并訪問之，然后按照它的右鏈接指示的地址再去周游該結(jié)點(diǎn)的右子樹。template<classT>voidBinaryTree<T>::InOrderWithoutRecusion(BinaryTreeNode<T>*root)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page35{ usingstd::stack; //使用STL中的stack stack<BinaryTreeNode<T>*>aStack; BinaryTreeNode<T>*pointer=root;while(!aStack.empty()||pointer){ if(pointer){

//當(dāng)前結(jié)點(diǎn)地址入棧

aStack.push(pointer);

//當(dāng)前鏈接結(jié)構(gòu)指向左孩子

pointer=pointer->leftchild();}

使用c++標(biāo)準(zhǔn)命名空間里的stack，就是STL里的stack(需要包含＃include＜stack＞才可以使用)。通過聲明命名空間來區(qū)分不同的類或函數(shù)等，避免導(dǎo)致全局命名沖突問題。所謂命名空間，是一種將程序庫名稱封裝起來的方法，像在各個(gè)程序庫中立起一道道圍墻。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36else{

//左子樹訪問完畢，轉(zhuǎn)向訪問右子樹

pointer=aStack.top(); //訪問當(dāng)前結(jié)點(diǎn)

Visit(pointer->value());

//當(dāng)前鏈接結(jié)構(gòu)指向右孩子

pointer=pointer->rightchild();

//棧頂元素退棧

aStack.pop(); }}//endwhile}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page37非遞歸前序周游二叉樹思想：遇到一個(gè)結(jié)點(diǎn)，就訪問該結(jié)點(diǎn)，并把此結(jié)點(diǎn)推入棧中，然后下降去周游它的左子樹；周游完它的左子樹后，從棧頂托出這個(gè)結(jié)點(diǎn)，并按照它的右鏈接指示的地址再去周游該結(jié)點(diǎn)的右子樹結(jié)構(gòu)。template<classT>voidBinaryTree<T>::PreOrderWithoutRecusion (BinaryTreeNode<T>*root)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page38{ usingstd::stack; //使用STL中的stack stack<BinaryTreeNode<T>*>aStack; BinaryTreeNode<T>*pointer=root;while(!aStack.empty()||pointer){ if(pointer){

Visit(pointer->value());//訪問當(dāng)前結(jié)點(diǎn)

//當(dāng)前結(jié)點(diǎn)地址入棧

aStack.push(pointer); //當(dāng)前鏈接結(jié)構(gòu)指向左孩子

pointer=pointer->leftchild();}

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page39else{//左子樹訪問完畢，轉(zhuǎn)向訪問右子樹

pointer=aStack.top(); //當(dāng)前鏈接結(jié)構(gòu)指向右孩子

pointer=pointer->rightchild();//棧頂元素退棧

aStack.pop(); } }//endwhile}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page40非遞歸后序周游二叉樹思想:遇到一個(gè)結(jié)點(diǎn)，把它推入棧中，周游它的左子樹；周游結(jié)束后，還不能馬上訪問處于棧頂?shù)脑摻Y(jié)點(diǎn)，而是要再按照它的右鏈接結(jié)構(gòu)指示的地址去周游該結(jié)點(diǎn)的右子樹；周游遍右子樹后才能從棧頂托出該結(jié)點(diǎn)并訪問之。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page41解決方案：需要給棧中的每個(gè)元素加上一個(gè)特征位，以便欲從棧頂托出一個(gè)結(jié)點(diǎn)時(shí)區(qū)別是從棧頂元素左邊回來的(則要繼續(xù)周游右子樹)，還是從右邊回來的(該結(jié)點(diǎn)的左、右子樹均已周游)。特征為Left表示已進(jìn)入該結(jié)點(diǎn)的左子樹，將從左邊回來；特征為Right表示已進(jìn)入該結(jié)點(diǎn)的右子樹，將從右邊回來。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page42定義棧中元素類型StackElement enumTags

{Left,Right}; //特征標(biāo)識(shí)定義

template<classT> classStackElement //棧元素的定義

{

public:

//指向二叉樹結(jié)點(diǎn)的鏈接

BinaryTreeNode<T>*pointer;

//特征標(biāo)識(shí)申明

Tagstag; }