數(shù)據(jù)結(jié)構(gòu)中的樹

1樹與二叉樹2樹和森林的概念兩種樹：自由樹與有根樹。

自由樹： 一棵自由樹Tf

可定義為一個(gè)二元組Tf

=(V,E)

其中V={v1,...,vn}

是由n(n＞0)個(gè)元素組成的有限非空集合，稱為頂點(diǎn)集合。E={(vi,vj)|vi,vj

V,1≤i,j≤n}

是n-1個(gè)序?qū)Φ募希Q為邊集合，E

中的元素(vi,vj）稱為邊或分支。3自由樹有根樹： 一棵有根樹T，簡稱為樹，它是n(n≥0)

個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，T稱為空樹；否則，T

是非空樹，記作

4r是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為m(m

0)個(gè)互不相交的有限集合T1,T2,…,Tm，每個(gè)集合又是一棵樹，并且稱之為根的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。5樹的基本術(shù)語子女：若結(jié)點(diǎn)的子樹非空，結(jié)點(diǎn)子樹的根即為該結(jié)點(diǎn)的子女。雙親：若結(jié)點(diǎn)有子女，該結(jié)點(diǎn)是子女雙親。1層2層4層3層depth=4DACBIJHGFEMLK6兄弟：同一結(jié)點(diǎn)的子女互稱為兄弟。度：結(jié)點(diǎn)的子女個(gè)數(shù)即為該結(jié)點(diǎn)的度；樹中各個(gè)結(jié)點(diǎn)的度的最大值稱為樹的度。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)即為分支結(jié)點(diǎn)，亦稱為非終端結(jié)點(diǎn)。葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)即為葉結(jié)點(diǎn)，亦稱為終端結(jié)點(diǎn)。祖先：某結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上的各個(gè)結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。子孫：某結(jié)點(diǎn)的所有下屬結(jié)點(diǎn)，都是該結(jié)點(diǎn)的子孫。7結(jié)點(diǎn)的層次：規(guī)定根結(jié)點(diǎn)在第一層，其子女結(jié)點(diǎn)的層次等于它的層次加一。以下類推。深度：結(jié)點(diǎn)的深度即為結(jié)點(diǎn)的層次；離根最遠(yuǎn)結(jié)點(diǎn)的層次即為樹的深度。1層2層4層3層depth=4DACBIJHGFEMLK8高度：規(guī)定葉結(jié)點(diǎn)的高度為1，其雙親結(jié)點(diǎn)的高度等于它的高度加一。有序樹：樹中結(jié)點(diǎn)的各棵子樹T0,T1,…是有次序的，即為有序樹。無序樹：樹中結(jié)點(diǎn)的各棵子樹之間的次序是不重要的，可以互相交換位置。森林：森林是m（m≥0）棵樹的集合。

9樹的抽象數(shù)據(jù)類型template<classT>classTree{//對象:樹是由n(≥0)個(gè)結(jié)點(diǎn)組成的有限集合。在//類界面中的position是樹中結(jié)點(diǎn)的地址。在順序//存儲(chǔ)方式下是下標(biāo)型,在鏈表存儲(chǔ)方式下是指針//型。T是樹結(jié)點(diǎn)中存放數(shù)據(jù)的類型,要求所有結(jié)//點(diǎn)的數(shù)據(jù)類型都是一致的。public:Tree();

~Tree();

10BuildRoot(constT&value);

//建立樹的根結(jié)點(diǎn)

positionFirstChild(positionp);

//返回

p第一個(gè)子女地址,無子女返回0 positionNextSibling(positionp);

//返回p下一兄弟地址,若無下一兄弟返回0 positionParent(positionp);

//返回

p雙親結(jié)點(diǎn)地址,若

p為根返回0TGetData(positionp);

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

p中存放的值

boolInsertChild(positionp,T&value);

//在結(jié)點(diǎn)

p下插入值為

value的新子女,若插

//入失敗,函數(shù)返回false,否則返回true11

boolDeleteChild(positionp,inti);

//刪除結(jié)點(diǎn)p

的第

i

個(gè)子女及其全部子孫結(jié)

//點(diǎn),若刪除失敗,則返回false,否則返回true

voidDeleteSubTree(positiont);

//刪除以t

為根結(jié)點(diǎn)的子樹

boolIsEmpty();

//判樹空否,若空則返回true,否則返回false

voidTraversal(positionp);

//遍歷以

p

為根的子樹};

12二叉樹的五種不同形態(tài)LLRR二叉樹(BinaryTree)二叉樹的定義

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。13二叉樹的性質(zhì)性質(zhì)1

若二叉樹結(jié)點(diǎn)的層次從1開始,則在二叉樹的第i層最多有

2i-1

個(gè)結(jié)點(diǎn)。(i≥1)

[證明用數(shù)學(xué)歸納法]性質(zhì)2

深度為k

的二叉樹最少有k

個(gè)結(jié)點(diǎn)，最多有2k-1個(gè)結(jié)點(diǎn)。(k≥1)

因?yàn)槊恳粚幼钌僖?個(gè)結(jié)點(diǎn)，因此，最少結(jié)點(diǎn)數(shù)為k。最多結(jié)點(diǎn)個(gè)數(shù)借助性質(zhì)1：用求等比級數(shù)前k項(xiàng)和的公式20+21+22+…+2k-1=2k-114性質(zhì)3

對任何一棵二叉樹，如果其葉結(jié)點(diǎn)有n0個(gè),度為2的非葉結(jié)點(diǎn)有n2個(gè),則有n0＝n2＋1

若設(shè)度為1的結(jié)點(diǎn)有n1個(gè)，總結(jié)點(diǎn)數(shù)為n， 總邊數(shù)為e，則根據(jù)二叉樹的定義，

n=n0+n1+n2

e

=2n2+n1=n-1

因此，有2n2+n1=n0+n1+n2-1

n2=n0-1n0=n2+115定義1

滿二叉樹(FullBinaryTree)

定義2

完全二叉樹(CompleteBinaryTree)─若設(shè)二叉樹的深度為k，則共有k層。除第k層外，其它各層(1～k-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。16性質(zhì)4

具有n(n≥0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2(n+1)

設(shè)完全二叉樹的深度為k，則有

2k-1-1<n

≤2k-1

變形2k-1<n+1≤2k

取對數(shù)

k-1<log2(n+1)≤k

有

log2(n+1)=k上面k-1層結(jié)點(diǎn)數(shù)包括第k層的最大結(jié)點(diǎn)數(shù)23-124-117性質(zhì)5

如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號1,2,…,n，則有以下關(guān)系：

若i=1,則i無雙親若i>1,則i的雙親為i／2若2*i<=n,則i的左子女為

2*i， 若2*i+1<=n,則i的右子女為2*i+1若i為奇數(shù),且i!=1,

則其左兄弟為i-1,若若

i為偶數(shù),且i!=n,

則其右兄弟為i+11234856791018二叉樹的抽象數(shù)據(jù)類型template<classT>classBinaryTree{//對象:結(jié)點(diǎn)的有限集合,二叉樹是有序樹public:

BinaryTree(); //構(gòu)造函數(shù)

BinaryTree(BinTreeNode<T>*lch,

BinTreeNode<T>*rch,Titem);

//構(gòu)造函數(shù),以item為根,lch和rch為左、右子

//樹構(gòu)造一棵二叉樹

intDepth(); //求樹深度

intSize(); //求樹中結(jié)點(diǎn)個(gè)數(shù)19

boolIsEmpty(); //判二叉樹空否？

BinTreeNode<T>*Parent(BinTreeNode<T>*t);

//求結(jié)點(diǎn)t的雙親

BinTreeNode<T>*LeftChild

(BinTreeNode<T>*t);

//求結(jié)點(diǎn)t的左子女

BinTreeNode<T>*RightChild(BinTreeNode<T>*t);

//求結(jié)點(diǎn)t的右子女

boolInsert

(Titem); //在樹中插入新元素

boolRemove(Titem); //在樹中刪除元素

boolFind(T&item); //判斷item是否在樹中

boolgetData(T&item); //取得結(jié)點(diǎn)數(shù)據(jù)20

BinTreeNode<T>*getRoot(); //取根

voidpreOrder(void(*visit)(BinTreeNode<T>*t)); //前序遍歷,visit是訪問函數(shù)

voidinOrder(void(*visit)(BinTreeNode<T>*t));

//中序遍歷,visit是訪問函數(shù)

voidpostOrder(void(*visit)(BinTreeNode<T>*t));

//后序遍歷,(*visit)是訪問函數(shù)

voidlevelOrder(void(*visit)(BinTreeNode<T>*t));

//層次序遍歷,visit是訪問函數(shù)};21完全二叉樹一般二叉樹的順序表示的順序表示二叉樹的順序表示1123456789

10

1412346789

12

14248910567312376489125101113221371531極端情形:只有右單支的二叉樹137153123二叉樹結(jié)點(diǎn)定義：每個(gè)結(jié)點(diǎn)有3個(gè)數(shù)據(jù)成員，data域存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)，leftChild和rightChild分別存放指向左子女和右子女的指針。leftChilddatarightChilddataleftChildrightChild二叉鏈表二叉樹的鏈表表示24leftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表二叉樹的鏈表表示每個(gè)結(jié)點(diǎn)增加一個(gè)指向雙親的指針parent，使得查找雙親也很方便。25二叉樹鏈表表示的示例AAABBBCCCDDDFFFEEErootrootroot26二叉樹遍歷二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作

V

遍歷根的左子樹記作

L

遍歷根的右子樹記作

R則可能的遍歷次序有

前序VLR

鏡像VRL

中序

LVR

鏡像RVL

后序LRV

鏡像RLV27中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(diǎn)(V)；中序遍歷右子樹(R)。遍歷結(jié)果

a+b*c

-

d

-

e/f中序遍歷(InorderTraversal)--/+*abcdef28二叉樹遞歸的中序遍歷算法template<classT>voidBinaryTree<T>::InOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){if(subTree!=NULL){

InOrder(subTree->leftChild,visit);

//遍歷左子樹

visit(subTree); //訪問根結(jié)點(diǎn)

InOrder(subTree->rightChild,visit);

//遍歷右子樹

}};29前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結(jié)果

-+a*b

-

cd/ef前序遍歷(PreorderTraversal)--/+*abcdef30二叉樹遞歸的前序遍歷算法template<classT>voidBinaryTree<T>::PreOrder(BinTreeNode<T>*subTree,void(*visit)

(BinTreeNode<T>*t)){if(subTree!=NULL){

visit(subTree); //訪問根結(jié)點(diǎn)

PreOrder(subTree->leftChild,visit);

//遍歷左子樹

PreOrder(subTree->rightChild,visit);

//遍歷右子樹

}};31后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(diǎn)(V)。遍歷結(jié)果

abcd

-*+ef/-后序遍歷(PostorderTraversal)--/+*abcdef32二叉樹遞歸的后序遍歷算法template<classT>voidBinaryTree<T>::PostOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t){if(subTree!=NULL){

PostOrder(subTree->leftChild,visit);

//遍歷左子樹

PostOrder(subTree->rightChild,visit); //遍歷右子樹

visit(subTree); //訪問根結(jié)點(diǎn)

}};33template<classT>intBinaryTree<T>::Size(BinTreeNode<T>*

subTree)const{//私有函數(shù)：利用二叉樹后序遍歷算法計(jì)算二叉//樹的結(jié)點(diǎn)個(gè)數(shù)

if(subTree==NULL)return0; //空樹

elsereturn1+Size(subTree->leftChild)

+

Size(subTree->rightChild);};應(yīng)用二叉樹遍歷的事例34template<classT>intBinaryTree<T>::Height(BinTreeNode<T>*subTree)const{//私有函數(shù)：利用二叉樹后序遍歷算法計(jì)算二叉//樹的高度或深度

if(subTree==NULL)return0; //空樹高度為0 else{ inti=Height(subTree->leftChild);intj=Height(subTree->rightChild); return(i<j)?j+1:i+1; };35利用二叉樹前序遍歷建立二叉樹以遞歸方式建立二叉樹。輸入結(jié)點(diǎn)值的順序必須對應(yīng)二叉樹結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。36層次序遍歷二叉樹就是從根結(jié)點(diǎn)開始，按層次逐層遍歷，如圖：遍歷順序abcdef--+/*層次序遍歷二叉樹的算法37這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一層的結(jié)點(diǎn)直接進(jìn)到隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)訪問它們。算法是非遞歸的。38abcdeQa訪問a,進(jìn)隊(duì)Qa出隊(duì)訪問b,進(jìn)隊(duì)訪問c,進(jìn)隊(duì)bcQb出隊(duì)訪問d,進(jìn)隊(duì)cdQc出隊(duì)訪問e,進(jìn)隊(duì)deQd出隊(duì)eQe出隊(duì)39層次序遍歷的（非遞歸）算法template<classT>voidBinaryTree<T>::levelOrder(void(*visit)(BinTreeNode<T>*t)){if(root==NULL)return;

Queue<BinTreeNode<T>*>Q;

BinTreeNode<T>*p=root;

visit(p);Q.EnQueue(p);

while(!Q.IsEmpty()){Q.DeQueue(p);if(p->leftChild!=NULL){

40visit(p->leftChild);

Q.EnQueue(p->leftChild);}if(p->rightChild!=NULL){visit(p->rightChild);

Q.EnQueue(p->rightChild);}}};41由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}

和中序序列{HBDFAEKCG

},構(gòu)造二叉樹過程如下：HBDFEKCGAEKCGABHDF42前序序列{ABHFDECKG}KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG43如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。固定前序排列，選擇所有可能的中序排列，可能構(gòu)造多少種不同的二叉樹？61234578961237584944例如,有3個(gè)數(shù)據(jù){1,2,3

}，可得5種不同的二叉樹。它們的前序排列均為

123，中序序列可能是321，231，213，132，123。前序序列為123，中序序列為

312

的二叉樹不存在。12312312312312345線索化二叉樹

(ThreadedBinaryTree)又稱為穿線樹。通過二叉樹的遍歷，可將二叉樹中所有結(jié)點(diǎn)的數(shù)據(jù)排列在一個(gè)線性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。希望不必每次都通過遍歷找出這樣的線性序列。只要事先做預(yù)處理，將某種遍歷順序下的前驅(qū)、后繼關(guān)系記在樹的存儲(chǔ)結(jié)構(gòu)中，以后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。46線索(Thread)增加前驅(qū)Pred指針和后繼Succ指針的二叉樹predleftChilddatarightChildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc47這種設(shè)計(jì)的缺點(diǎn)是每個(gè)結(jié)點(diǎn)增加兩個(gè)指針，當(dāng)結(jié)點(diǎn)數(shù)很大時(shí)存儲(chǔ)消耗較大。改造樹結(jié)點(diǎn)，將pred指針和succ指針壓縮到leftChild和rightChild的空閑指針中，并增設(shè)兩個(gè)標(biāo)志ltag和rtag，指明指針是指示子女還是前驅(qū)／后繼。后者稱為線索。ltag(或rtag)=0，表示相應(yīng)指針指示左子女（或右子女結(jié)點(diǎn)）；當(dāng)ltag(或rtag)=1,表示相應(yīng)指針為前驅(qū)（或后繼）線索。leftChildltagdatartagrightChild

48leftChildltagdatartagrightChild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111線索化二叉樹及其鏈表表示49線索化二叉樹的類定義template<classT>structThreadNode{ //線索二叉樹的結(jié)點(diǎn)類

intltag,rtag; //線索標(biāo)志

ThreadNode<T>*leftChild,*rightChild;

//線索或子女指針

Tdata; //結(jié)點(diǎn)數(shù)據(jù)

ThreadNode(constTitem)//構(gòu)造函數(shù)

:data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0){} };50template<classT>classThreadTree{ //線索化二叉樹類protected:

ThreadNode<T>*root; //樹的根指針

voidcreateInThread(ThreadNode<T>*current,

ThreadNode<T>*&pre);

//中序遍歷建立線索二叉樹

ThreadNode<T>*parent(ThreadNode<T>*t);

//尋找結(jié)點(diǎn)t的雙親結(jié)點(diǎn)public:

ThreadTree():root(NULL){} //構(gòu)造函數(shù)51voidcreateInThread();//建立中序線索二叉樹

ThreadNode<T>*First(ThreadNode<T>*current);

//尋找中序下第一個(gè)結(jié)點(diǎn)

ThreadNode<T>*Last(ThreadNode<T>*current);

//尋找中序下最后一個(gè)結(jié)點(diǎn)

ThreadNode<T>*Next(ThreadNode<T>*current);

//尋找結(jié)點(diǎn)在中序下的后繼結(jié)點(diǎn)

ThreadNode<T>*Prior(ThreadNode<T>*current);

//尋找結(jié)點(diǎn)在中序下的前驅(qū)結(jié)點(diǎn)

……… };52通過中序遍歷建立中序線索化二叉樹0A00B00C00D00E0rootpre==NULLcurrent530A0

1B00C00D00E0rootpre==NULLcurrent540A0

1B00C0

1D00E0rootprecurrent550A0

1B00C0

1D1

0E0rootprecurrent560A0

1B00C0

1D1

1E0rootprecurrent570A0

1B00C0

1D1

1E1

rootprecurrent580A0

1B00C1

1D1

1E1

rootpre后處理59樹的存儲(chǔ)表示A(B(E,F),C,D(G))

結(jié)點(diǎn)的utype域沒有畫出ABCDEFGABEFCDG1、廣義表表示60ABCDEFGdataparentABCDEFG-100011301234562、雙親表示樹中結(jié)點(diǎn)的存放順序一般不做特殊要求，但為了操作實(shí)現(xiàn)的方便，有時(shí)也會(huì)規(guī)定結(jié)點(diǎn)的存放順序。例如，可以規(guī)定按樹的前序次序存放樹中的各個(gè)結(jié)點(diǎn)，或規(guī)定按樹的層次次序安排所有結(jié)點(diǎn)。

613、子女鏈表表示無序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個(gè)子女結(jié)點(diǎn)。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456624、子女指針表示一個(gè)合理的想法是在結(jié)點(diǎn)中存放指向每一個(gè)子女結(jié)點(diǎn)的指針。但由于各個(gè)結(jié)點(diǎn)的子女?dāng)?shù)不同，每個(gè)結(jié)點(diǎn)設(shè)置數(shù)目不等的指針，將很難管理。為此，設(shè)置等長的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)相等，等于樹的度（degree）。這保證結(jié)點(diǎn)有足夠的指針指向它的所有子女結(jié)點(diǎn)。但可能產(chǎn)生很多空閑指針，造成存儲(chǔ)浪費(fèi)。63等數(shù)量的鏈域ABCDEFG

datachild1child2child3childdABCDEFG空鏈域2n+1個(gè)645、子女-兄弟表示也稱為樹的二叉樹表示。結(jié)點(diǎn)構(gòu)造為：firstChild指向該結(jié)點(diǎn)的第一個(gè)子女結(jié)點(diǎn)。無序樹時(shí)，可任意指定一個(gè)結(jié)點(diǎn)為第一個(gè)子女。nextSibling指向該結(jié)點(diǎn)的下一個(gè)兄弟。任一結(jié)點(diǎn)在存儲(chǔ)時(shí)總是有順序的。若想找某結(jié)點(diǎn)的所有子女，可先找firstChild,再反復(fù)用nextSibling沿鏈掃描。

datafirstChildnextSibling65樹的子女-

兄弟表示

datafirstChildnextSiblingABCDEFGABCDGFE66堆(Heap)template<classT,classE>classMinPQ{//最小優(yōu)先級隊(duì)列類的定義public:

VirtualboolInsert(E&d)=0;

VirtualboolRemove(E&d)=0;};

優(yōu)先級隊(duì)列每次出隊(duì)列的是優(yōu)先權(quán)最高的元素。用堆實(shí)現(xiàn)其存儲(chǔ)表示，能夠高效運(yùn)作。67最小堆完全二叉樹順序表示

Ki≤K2i+1&&Ki≤K2i+2最大堆完全二叉樹順序表示Ki≥K2i+1&&Ki≥K2i+2090987877878454565653131532323531717堆的定義68堆的元素下標(biāo)計(jì)算由于堆存儲(chǔ)在下標(biāo)從0開始計(jì)數(shù)的一維數(shù)組中，因此在堆中給定下標(biāo)為i

的結(jié)點(diǎn)時(shí)如果

i=0，結(jié)點(diǎn)i

是根結(jié)點(diǎn)，無雙親；否則結(jié)點(diǎn)i

的父結(jié)點(diǎn)為結(jié)點(diǎn)(i-1)/2)；如果2i+1＞n-1，則結(jié)點(diǎn)i

無左子女；否則結(jié)點(diǎn)i

的左子女為結(jié)點(diǎn)2i+1；如果2i+2＞n-1，則結(jié)點(diǎn)i無右子女；否則結(jié)點(diǎn)i的右子女為結(jié)點(diǎn)

2i+2。69自下向上逐步調(diào)整為最小堆currentPos=i=3currentPos=i=25353171778780923456587i0923456587i將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆70currentPos=i=15353171778780923456587i0923456587i71currentPos=i=05353171778780923456587i0923456587i09725353171778780923456587i0923456587i1773樹的應(yīng)用例子---決策樹74樹的應(yīng)用例子---文件系統(tǒng)搜索樹7576二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(Key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。左子樹和右子樹也是二叉搜索樹。77351545504025102030二叉搜索樹例結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼；右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼；注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。78如果對一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。二叉搜索樹的類定義#include<iostream.h>#include<stdlib.h>template<classE,classK>structBSTNode{ //二叉樹結(jié)點(diǎn)類

Edata; //數(shù)據(jù)域

BSTNode<E,K>*left,*right;//左子女和右子女79BSTNode(){left=NULL;right=NULL;

}

//構(gòu)造函數(shù)

BSTNode(constEd,BSTNode<E,K>*L=NULL,

BSTNode<E,K>*R=NULL){data=d;left=L;right=R;}

//構(gòu)造函數(shù)～BSTNode(){} //析構(gòu)函數(shù)

voidsetData(Ed){data=d;} //修改

EGetData(){returndata;} //提取

booloperator<(constE&x)

//重載：判小于

{returndata.key<x.key;}80booloperator>(constE&x)

//重載：判大于

{returndata.key>x.key;}booloperator==(constE&x)

//重載：判等于

{returndata.key==x.key;}};template<classE,classK>classBST{ //二叉搜索樹類定義public:BST(){root=NULL;

} //構(gòu)造函數(shù)

BST(Kvalue); //構(gòu)造函數(shù)

～BST(){}; //析構(gòu)函數(shù)

81boolSearch(constKx)const //搜索

{returnSearch(x,root)!=NULL;}

BST<E,K>&operator=(constBST<E,K>&R); //重載：賦值

voidMakeEmpty()

//置空

{MakeEmpty(root);root=NULL;}voidPrintTree()const{PrintTree(root);}//輸出

EMin(){returnMin(root)->data;} //求最小

EMax(){returnMax(root)->data;} //求最大

boolInsert(constE&e1)

//插入新元素

{returnInsert(e1,root);}82boolRemove(constKx){returnRemove(x,root);} //刪除含x的結(jié)點(diǎn)private:

BSTNode<E,K>*root; //根指針

KRefValue; //輸入停止標(biāo)志

BSTNode<E,K>* //遞歸：搜索

Search(constKx,BSTNode<E,K>*ptr);voidmakeEmpty(BSTNode<E,K>*&ptr); //遞歸：置空

voidPrintTree(BSTNode<E,K>*ptr)const; //遞歸：打印

BSTNode<E,K>* //遞歸：復(fù)制

Copy(constBSTNode<E,K>*ptr); 83BSTNode<E,K>*Min(BSTNode<E,K>*ptr);

//遞歸：求最小

BSTNode<E,K>*Max(BSTNode<E,K>*ptr);

//遞歸：求最大

boolInsert(constE&e1,BSTNode<E,K>*&ptr);

//遞歸：插入

boolRemove(constKx,BSTNode<E,K>*&ptr);

//遞歸：刪除};二叉搜索樹的類定義用二叉鏈表作為它的存儲(chǔ)表示，許多操作的實(shí)現(xiàn)與二叉樹類似。84二叉搜索樹的搜索算法在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x

的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值

x

與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則搜索成功，返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。85若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子樹。搜索45搜索成功搜索28搜索失敗35154550402510203086搜索過程是從根結(jié)點(diǎn)開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個(gè)結(jié)點(diǎn)；搜索不成功，搜索指針將走到樹上某個(gè)結(jié)點(diǎn)的空子樹。設(shè)樹的高度為h，最多比較次數(shù)不超過h。87二叉搜索樹的插入算法為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。8835154550402510203028插入新結(jié)點(diǎn)28二叉搜索樹的插入每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。89輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091