樹數據結構與算法1引言

前述我們所研究的數據結構線性表是線性結構。本章將研究的樹型結構是一種動態的，非線性的，可描述結構層次特性的數據結構。這種結構是按分枝關系把信息聯系起來的數據組織形式。在日常生活中這種結構是不少見的，如：2家譜圖(譜系圖)ChangChang父祖父祖母Chang母外祖父外祖母3行政機構圖中央人民政府湖南省湖北省……上海市長沙………全省各地市………各市、縣、區4UNIX文件目錄5XML文件結構6樹型的網絡拓撲結構7編譯程序中使用語法樹8樹型結構小節客觀世界中廣泛存在樹結構樹結構也在計算科學領域中被廣泛的（創造和）應用以上各例的數據(信息)組織形式，均稱為樹型結構。當然它與植物樹有所不同，(它的根在上，枝在下)9樹的定義和基本術語10樹的定義一棵樹(tree)T是由一個或一個以上結點組成的有限集其中有一個特定的結點R稱為T的根結點。集合(T－{R})中的其余結點可被劃分為n≥0個互不相交的子集T1，T2，…,Tn，其中每個子集本身又是一棵樹，并且其相應的根結點R1，R2，…,Rn是R的子結點子集Ti(1≤i≤n)稱為樹T的子樹(subtree)。子樹可如下排序：Ti排在Tj之前，當且僅當i<j為方便起見,子樹從左到右排列,其中T1被稱為R的最左子樹,R1被稱為R的最左子結點11ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:12結點:結點的度:樹的度:葉子結點:分支結點:數據元素+若干指向子樹的分支分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM13(從根到結點的)路徑：孩子結點、雙親結點兄弟結點、堂兄弟祖先結點、子孫結點結點的層次:樹的深度：由從根到該結點所經分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1，第l層的結點的子樹根結點的層次為l+1樹中葉子結點所在的最大層次14任何一棵非空樹是一個二元組

Tree=（root，F）其中：root被稱為根結點

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF15對比樹型結構和線性結構的結構特點16~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數據元素

(無前驅)

根結點

(無前驅)最后一個數據元素

(無后繼)多個葉子結點

(無后繼)其它數據元素(一個前驅、一個后繼)其它數據元素(一個前驅、多個后繼)17樹的ADT18數據對象D：D是具有相同特性的數據元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數據元素root；

(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數據關系R：19

基本操作：查找類

插入類刪除類20

Root(T)//求樹的根結點

查找類：Value(T,cur_e)//求當前結點的元素值

Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子

RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹

TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷21InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構造樹Assign(T,cur_e,value)//給當前結點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結點p的第i棵子樹22

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)//刪除結點p的第i棵子樹23樹結點的ADT//GeneraltreenodeADTtemplate<classElem>classGTNode{public:

GTNode(const

Elem&);//Constructor~GTNode();//Destructor

Elemvalue();//Returnvalue

bool

isLeaf();//TRUEifisaleaf

GTNode*parent();//Returnparent

GTNode*leftmost_child();//Firstchild

GTNode*right_sibling();//RightsiblingvoidsetValue(Elem&);//Setvalue

voidinsert_first(GTNode<Elem>*n);voidinsert_next(GTNode<Elem>*n);

voidremove_first();//Removefirstchildvoidremove_next();//Removesibling};24樹的ADT//GeneraltreenodeADTtemplate<classElem>classGenTree{private：voidprinthelp(GTNode*);//printhelperfunctionpublic:

GenTree();//constructor~GenTree();//Destructorvoidclear();//Sendnodestofreestore

GTNode*root();//Returntheroot//Combinetwosubtree

Voidnewroot(Elem&,GTNode<Elem>*,GTNode<Elem>*);Voidprint();//Printatree};25二叉樹的定義和性質26二叉樹BinaryTrees二叉樹(binarytree)是結點(node)的有限集合，這個集合或者為空(empty)，或者由一個根結點(root)以及兩棵二叉樹組成,這兩棵二叉樹分別稱作這個根的左子樹(leftsubtree)和右子樹(rightsubtree),這兩棵二叉樹分別與根結點相連且彼此不相交.

2728二叉樹的五種基本形態N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹29二叉樹的特性(性質1)特性一：在二叉樹中，第i層上的結點數最多為2i1(i≥1);證明(歸納法)：當i=1時，只有一個結點，2i1=20=1(歸納基礎)歸納假設：假定對所有的j,1≤j<i

命題成立，即第j層上結點總數最多為2j1個結點。那么，可以證明j=i時命題成立。30歸納步驟：由歸納假設可知，i1層上的結點總數最多為2i2。由于二叉樹每個結點的度最大為2，所以第i層上的結點最大數為第i1層上結點最大數的2倍，即22i2，從而得證，i層上最大結點數為2i1.31特性二：深度為k的二叉樹至多有2k1個結點.(k≥1)證明：深度為k的二叉樹結點最大數為每一層結點最大數之和。由特性一得：二叉樹的特性(性質2)32特性三：對任一棵二叉樹，若葉結點數為n0,度為2的結點數為n2，則有n0=n2+1成立證明：設度為1的結點數為n1，則二叉樹的結點總數為：n=n0+n1+n2

…………(1)二叉樹的特性(性質3)33設二叉樹的分支總數為B，除根結點外，每一個結點都有一個分支進入，則B=n1又因為度為1的結點發出一個分支，度為2的結點發出2個分支所以：B=n1+2n2從而得n=n1+2n2+1…………(2)由(1),(2)式得n0=n2+1成立.34FullandCompleteBinaryTrees滿二叉樹(fullbinarytree)的每一個結點或者是一個分支結點，并恰有兩個非空子結點；或者是葉結點.完全二叉樹(completebinarytree)從根結點起每一層的結點從左到右連續填充,除了最下面一層以外其余各層都是滿的,并且最下面一層的結點都集中在該層的最左邊.35特性四：具有n個結點的完全二叉樹，其深度為：

k=log2n+1證：根據性質2和完全二叉樹的定義，設完全二叉樹的深度為k，則2k11

<n≤2k1深度為k1的完全二叉樹的最大結點數深度為k的完全二叉樹的最大結點數即2k1≤

n<2k于是有k1≤log2n<kk為整數k=log2n

+1得證完全二叉樹的特性(性質4)36特性五：如果對一棵有n個結點的完全二叉樹(其深度為log2n+1)的結點按層次自上而下，從左至右編號，則對任一編號為i的結點(1≤i≤n)有2)若2i≤n

則結點i的左孩子是編號為2i的結點;否則結點i無左孩子（結點i為葉子結點）。1)若i=1,則該結點為根結點，無雙親，若i1,則結點i的雙親是編號為i/2

的結點。記為parent(i)=i/2

完全二叉樹的特性(性質5)3)若2i+1≤n

則結點i的右孩子是結點2i+1;否則結點i無右孩子。3748925106371結點3×2＋1<10,所以結點3的左孩子序號為3*2=6，右孩子結點序號為3×2＋1＝7。結點10的雙親結點序號為10/2＝5例子38滿二叉樹定理Theorem:非空滿二叉樹的葉結點數等于其分支結點數加1.39滿二叉樹定理證明1Theorem:非空滿二叉樹的葉結點數等于其分支結點數加1.證明(byMathematicalInduction數學歸納法):初始情況:沒有分支結點的非空二叉樹有一個葉結點。有一個分支結點的滿二叉樹有兩個葉結點，即當n=0及n=1時定理成立.歸納假設:設任意一棵有n-1個分支結點的滿二叉樹T有n個葉結點.40滿二叉樹定理證明1(續)歸納步驟:假設樹T有n個分支結點，取一個左右子結點均為葉結點的分支結點I。去掉I的兩個子結點，則I成為葉結點，把新樹記為T'，T'有n-1個分支結點.根據歸納假設，T‘有n個葉結點的滿二叉樹.現在把兩個葉結點歸還給I,我們又得到樹T,它有n個分支結點。但原先的葉結點I現在變成了分支結點，所以葉結點只增加了一個,于是，樹T有n個分支結點和n+1個葉結點.因此，根據歸納原理，定理對任意的n≥0成立。41滿二叉樹定理證明2Theorem:非空滿二叉樹的葉結點數等于其分支結點數加1.證明2:設分支結點數為n,根據滿二叉樹的定義,每一個分支結點都有兩個非空子結點,所以共有2n個非空子結點,加上根結點,該二叉樹總共有2n+1個結點,除去n個分支結點,剩下n+1個葉結點42滿二叉樹定理的推論Theorem:一棵非空二叉樹空子樹的數目等于其結點數目加1.Proof:Replaceallnullpointerswithapointertoanemptyleafnode.Thisisafullbinarytree.43滿二叉樹定理的推論的證明1證明1：設二叉樹T，將其所有空子樹換成葉結點，把新的二叉樹記為T‘。所有原來樹T的結點現在是樹T’的分支結點。由于樹T中的分支結點要么有兩個非空子結點,要么有一個非空子結點和一個空子樹,而這個空子樹在T‘中已換成了非空子結點;并且樹T中的每個葉結點都有兩個空子樹,在樹T’中都換成了兩個非空子結點,所以樹T‘中的每個分支結點都有兩個非空子結點,所以樹T’是滿二叉樹。根據滿二叉樹定理，新添加的葉結點數目等于樹T的結點數目加1，而每個新添加的葉結點對應樹T的一棵空子樹，因此樹T中空子樹的數目等于樹T中結點數目加1。44滿二叉樹定理的推論的證明2Theorem:一棵非空二叉樹空子樹的數目等于其結點數目加1.證明2：假設樹T有n個結點,其中有一個是根結點，其余n-1個都是非空子結點。如果把空子樹也算作子結點的話，那么每個結點都有兩個子結點,n個結點就有2n個子結點。既然非空子結點數目為n-1，所以必有有n+1個子結點為空。45二叉樹的ADT46數據對象D：D是具有相同特性的數據元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數據元素root；

(2)當n>1時，其余結點可分為不相交的有限集

Tl、Tr，其中每一個子集本身又是一棵符合本定義的二叉樹，稱為根root的子樹。

數據關系R：47二叉樹結點的ADT//Binarytreenodeabstractclasstemplate<classElem>classBinNode{public:virtualElem&val()=0;//Returnthenode'selementvirtualvoidsetVal(const

Elem&)=0;//Setthenode'selementvirtualBinNode*left()const=0;//Returnthenode'sleftchildvirtualvoidsetLeft(BinNode*)=0;//Setthenode'sleftchildvirtualBinNode*right()const=0;//Returnthenode'srightchildvirtualvoidsetRight(BinNode*)=0;//Setthenode'srightchildvirtualbool

isLeaf()=0;//Returntrueiffthenodeisaleaf};48BinaryTreeNodeClass(1)//Binarytreenodeclasstemplate<classElem>classBinNodePtr:publicBinNode<Elem>{private:

Elemit;//Thenode'svalue

BinNodePtr*lc;//Pointertoleftchild

BinNodePtr*rc;//Pointertorightchildpublic:

BinNodePtr(){lc=rc=NULL;}

BinNodePtr(Eleme,BinNodePtr*l=NULL,

BinNodePtr*r=NULL){it=e;lc=l;rc=r;}

49BinaryTreeNodeClass(2)

Elem&val(){returnit;}voidsetVal(const

Elem&e){it=e;}inlineBinNode<Elem>*left()const{returnlc;}voidsetLeft(BinNode<Elem>*b){lc=(BinNodePtr*)b;}inlineBinNode<Elem>*right()const{returnrc;}voidsetRight(BinNode<Elem>*b){rc=(BinNodePtr*)b;}

bool

isLeaf(){return(lc==NULL