第-5章-樹-數(shù)據(jù)結(jié)構(gòu)課件

樹和森林的概念二叉樹二叉樹的表示二叉樹遍歷及其應(yīng)用線索化二叉樹樹與森林堆

Huffman樹

第5章樹樹和森林的概念第5章樹樹和森林的概念兩種樹：自由樹與有根樹。

自由樹：一棵自由樹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ū)Φ募?，稱為邊集合，E

中的元素(vi,vj）稱為邊或分支。樹和森林的概念兩種樹：自由樹與有根樹。自由樹自由樹

r是一個(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è)直接后繼。有根樹： 一棵有根樹T，簡(jiǎn)稱為樹，它是n(n≥0)

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

是非空樹，記作r是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它只有直接后繼，樹的示意圖（P.187）樹的示意圖（P.187）樹的特點(diǎn)每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。0層1層3層2層height=3ACGBDEFKLHMIJ樹的特點(diǎn)每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或0層1層3層2層height=3ACGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度分支結(jié)點(diǎn)葉結(jié)點(diǎn)子女雙親兄弟祖先子孫結(jié)點(diǎn)層次樹的度樹高度森林術(shù)語(yǔ)0層1層3層2層heightACGBDEFKLHMIJ結(jié)點(diǎn)子template<classType>classTree{public:Tree();

~Tree();

positionRoot();BuildRoot(constType&value);positionFirstChild

(positionp);positionNextSibling(positionp);positionParent(positionp);

TypeGetData(positionp);

intInsertChild(constpositionp,

constType&value);

int

DeleteChild(positionp,inti);}樹的抽象數(shù)據(jù)類型template<classType>classTr一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。5.2二叉樹(BinaryTree)

二叉樹的定義一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)二叉樹的五種不同形態(tài)LLRR二叉樹的五種不同形態(tài)LLRR性質(zhì)1

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

≥1)

性質(zhì)2

深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)。k

≥0二叉樹的性質(zhì)

性質(zhì)1若二叉樹的層次從1開始,則在二叉樹的第i層性質(zhì)3

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

n0＝n2＋1證明：若設(shè)度為1的結(jié)點(diǎn)有n1

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

n=n0+n1+n2

e=n

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

-1

n2=n0

-1n0=n2+1性質(zhì)3對(duì)任何一棵二叉樹,如果其葉結(jié)點(diǎn)有n0個(gè),度定義1

滿二叉樹(FullBinaryTree)

如果二叉樹中所有分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。定義2

完全二叉樹(CompleteBinaryTree)如果一棵具有n個(gè)結(jié)點(diǎn)的高度為k的二叉樹，它的每一個(gè)結(jié)點(diǎn)都與高度為k的滿二叉樹中編號(hào)為1-n結(jié)點(diǎn)一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。（從上到下從左到右編號(hào)）定義1滿二叉樹(FullBinaryTree)定滿二叉樹完全二叉樹層次h，葉結(jié)點(diǎn)僅在兩層出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右子樹的高度為k，則其左子樹的高度是

h和h-1

kork+1滿二叉樹

性質(zhì)4

具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的高度為

log2(n+1)

23-124-1性質(zhì)4具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的高性質(zhì)5

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

為根，無(wú)雙親若i>1,則i的雙親為i/2(2)若n>=2*i,則結(jié)點(diǎn)i的左子女為2*i;

(3)若n>=2*i+1,則結(jié)點(diǎn)i的右子女為2*i+112348567910性質(zhì)5如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左（4）若結(jié)點(diǎn)編號(hào)i為奇數(shù)，且i!=1,則它的左兄弟為結(jié)點(diǎn)i-1。（5）若結(jié)點(diǎn)編號(hào)i為偶數(shù)，且i!=n,則它的右兄弟為結(jié)點(diǎn)i+1。（6）結(jié)點(diǎn)i所在層次為log2i+112348567910（4）若結(jié)點(diǎn)編號(hào)i為奇數(shù)，且i!=1,則它的左兄弟為結(jié)點(diǎn)i-template<classType>classBinaryTree

{public:BinaryTree();

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

BinaryTree(BinTreeNode<Type>*lch,BinTreeNode<Type>*rch,Typeitem);

//構(gòu)造以item為根，lch和rch為左、右

//子樹的二叉樹

intIsEmpty();

//判二叉樹空否？

BinTreeNode<Type>*Parent();

//雙親

二叉樹的抽象數(shù)據(jù)類型template<classType>classBi

BinTreeNode<Type>*LeftChild();

//取左子女結(jié)點(diǎn)地址

BinTreeNode<Type>*RightChild();

//取右子女結(jié)點(diǎn)地址

intInsert(constType&item);//插入

intFind(constType&item)const;//搜索

TypeGetData()const;//取得結(jié)點(diǎn)數(shù)據(jù)

BinTreeNode<Type>*GetRoot()const;

//取根結(jié)點(diǎn)地址}BinTreeNode<Type>*LeftCh0123456789完全二叉樹01378945625.3二叉樹的存儲(chǔ)表示順序表示0123456789完全二叉樹013780123567891113一般二叉樹的順序表示13026537811101235678911130261430極端情形:只有右單支的二叉樹02614300261430極端情形:只有右單支的二叉樹0261430leftChilddatarightChilddataleftChildrightChild二叉鏈表二叉樹的鏈表表示

leftChilddatarightChilddleftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表leftChilddataparentri二叉樹鏈表表示的示例ABCDFErootAABBCCDDFFEErootroot

二叉鏈表三叉鏈表二叉樹鏈表表示的示例ABCDFEroot二叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdataparentleftChildrightChild012345A-11-1B023C1

-1-1D145E3-1-1F3-1-1二叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdataparentemplate<classType>classBinaryTree;

template<classType>ClassBinTreeNode{friendclassBinaryTree<Type>;private:Type

data;

BinTreeNode<Type>*leftChild;

BinTreeNode<Type>*rightChild;

public:BinTreeNode():leftChild(NULL),rightChild(NULL){}二叉樹的類定義template<classType>classBi

BinTreeNode(Typeitem,BinTreeNode<Type>*left=NULL, BinTreeNode<Type>*right=NULL):data(item),leftChild(left),rightChild(right){}TypeGetData

()const{returndata;

}BinTreeNode<Type>*GetLeft()const{returnleftChild;

}

BinTreeNode<Type>*GetRight()const{returnrightChild;

}

voidSetData(constType&item)

{data=item;

}

BinTreeNode(Typeitem,

voidSetLeft(BinTreeNode<Type>*L)

{leftChild=L;

}voidSetRight(BinTreeNode<Type>*R)

{rightChild=R;

}};template<classType>class

BinaryTree{

private:

BinTreeNode<Type>*root;

Type

RefValue;

void

CreateBinTree(ifstream&in,

BinTreeNode<Type>*¤t);

voidSetLeft(BinTreeNode

BinTreeNode<Type>*Parent(BinTreeNode<Type>*subTree,BinTreeNode<Type>*current);

int

Insert(BinTreeNode<Type>*&subTree,

constType

&item);

//插入

voidTraverse(BinTreeNode<Type>*subTree,

ostream&out)const

//遍歷

int

Find(BinTreeNode<Type>*subTree,

constType&item)const

//搜索

voiddestroy(BinTreeNode<Type>*subTree);

//刪除…}BinTreeNode<Type>*Parent

樹的遍歷:按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作V，遍歷根的左子樹記作L，遍歷根的右子樹記作R

5.4二叉樹遍歷

樹的遍歷:按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)則可能的遍歷次序有:

VLRVRLLVRRVLLRV

RLV

前序

鏡像中序

鏡像

后序

鏡像則可能的遍歷次序有:前序中序遍歷(InorderTraversal)--/+*abcdef遍歷結(jié)果:

a+b*c

-

d

-

e/fLVR中序遍歷(InorderTraversal)--/+*a中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(diǎn)(V)；中序遍歷右子樹(R)。中序遍歷二叉樹算法的框架是：二叉樹遞歸的中序遍歷算法template<classType>voidBinaryTree<Type>::InOrder(BinTreeNode<Type>*subTree){

if(subTree!=NULL){

InOrder(subTree->leftChild);

cout<<subTree->data;InOrder(subTree->rightChild

);

}}二叉樹遞歸的中序遍歷算法前序遍歷(PreorderTraversal)--/+*abcdef遍歷結(jié)果:

-+a*b

-

cd/efVLR前序遍歷(PreorderTraversal)--/+*前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。前序遍歷二叉樹算法的框架是：二叉樹遞歸的前序遍歷算法template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*subTree){

if(subTree!=NULL){

cout<<subTree->data;PreOrder(subTree->leftChild);PreOrder(subTree->rightChild);

}}二叉樹遞歸的前序遍歷算法后序遍歷(PostorderTraversal)--/+*abcdef遍歷結(jié)果:

abcd

-*+ef/-

LRV后序遍歷(PostorderTraversal)--/+后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(diǎn)(V)。后序遍歷二叉樹算法的框架是：二叉樹遞歸的后序遍歷算法template<classType>voidBinaryTree<Type>::PostOrder(BinTreeNode<Type>*subTree){

if(subTree!=NULL){

PostOrder(subTree->leftChild);PostOrder(subTree->rightChild);

cout<<subTree->data;

}}二叉樹遞歸的后序遍歷算法template<classType>voidBinaryTree<Type>::InOrder(){InOrder(root);}template<classType>voidBinaryTree<Type>::PreOrder(){PreOrder(root);}template<classType>voidBinaryTree<Type>::PostOrder(){PostOrder(root);}template<classType>關(guān)于樹的性質(zhì)：1.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為：

2.假定一棵三叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為，最大高度為。3.在一棵二叉樹中，假定度為2的結(jié)點(diǎn)有5個(gè)，度為1的結(jié)點(diǎn)有6個(gè)，則葉子結(jié)點(diǎn)數(shù)有個(gè)n-14496關(guān)于樹的性質(zhì)：n-144961.利用二叉樹后序遍歷計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)template<classType>intBinaryTree<Type>::Count(BinTreeNode<Type>*t)const{

if(t==NULL)return0;

else

return

1+Count(t->leftChild)+Count(t->rightChild);}應(yīng)用二叉樹遍歷的實(shí)例

1.利用二叉樹后序遍歷計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)template以遞歸方式建立二叉樹。輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。2.利用二叉樹前序遍歷建立二叉樹以遞歸方式建立二叉樹。2.利用二叉樹前序遍歷建立二叉樹如圖所示的二叉樹的前序遍歷順序?yàn)?ABC@@DE@G@@F@@@ABCDEGF@@@@@@@@如圖所示的二叉樹的前序遍歷順序?yàn)?ABCDEGF@@@@@@

template<classType>voidBinaryTree<Type>::CreateBinTree(ifstream&in,BinTreeNode<Type>*&

subTree){//私有函數(shù):以遞歸方式建立二叉樹。//輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹結(jié)點(diǎn)前//序遍歷的順序。并約定以輸入序列中不可//能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,//此值在RefValue中。例如用“@”或用“-1”//表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。

Typeitem;

if(!in.eof()){template<classType>

in>>item;

//讀入根結(jié)點(diǎn)的值

if(item!=RefValue){

subTree=newBinTreeNode<Type>

(item);

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

if(subTree==NULL)

{

cerr<<“存儲(chǔ)分配錯(cuò)!”<<endl;exit(1);}CreateBinTree(in,subTree->leftChild);CreateBinTree(in,subTree->rightChild);

}elsesubTree=NULL;//封閉葉結(jié)點(diǎn)

}}in>>item; //讀入根結(jié)點(diǎn)的二叉樹遍歷的非遞歸算法1）后序遍歷的非遞歸算法structSTKNode

{

BinTreeNode<Type>*ptr;}senuntag{L,R};//tag=L,表示從左子樹退回還要遍歷右子樹;//tag=R，表示從右子樹退回要訪問根結(jié)點(diǎn)。

二叉樹遍歷的非遞歸算法1）后序遍歷的非遞歸算法struct算法思想：將棧s初始化，然后令指針p指向二叉樹的根結(jié)點(diǎn)，即p=T.

如果指向根結(jié)點(diǎn)的指針不為空，先將tag置L；再將tag和根結(jié)點(diǎn)一起送入棧中；然后將指針指向該結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)；繼續(xù)遍歷。如果指向根結(jié)點(diǎn)的指針為空，則將棧頂存放的數(shù)據(jù)項(xiàng)出棧，有兩種情況：若tag=L,則改變tag的值，將tag置R；再把tag和彈出的結(jié)點(diǎn)重新入棧；然后將指針指向該結(jié)點(diǎn)的右子樹根結(jié)點(diǎn)，繼續(xù)遍歷。若tag=R，則訪問彈出的結(jié)點(diǎn)，并將彈出的指針置為空直到棧為空并且指針為空時(shí)，遍歷結(jié)束。算法思想：template<classT>voidBinaryTree<T>::PostOrder(void(*visit)(BinTreeNode<T>*p){Stack<stkNode<T>>S;stkNode<T>w;BinTreeNode<T>*p=root;//p是遍歷指針

do{ while(p!=NULL){ w.ptr=p;w.tag=L;S.Push(w); p=p->leftChild;} } intcontinue1=1; //繼續(xù)循環(huán)標(biāo)記,用于Rwhile(continue1&&!S.IsEmpty()){ S.Pop(w);p=w.ptr; switch(w.tag){ //判斷棧頂?shù)膖ag標(biāo)記

caseL:w.tag=R;S.Push(w); continue1=0; p=p->rightChild;break; caseR:visit(p);break; } }}while(!S.IsEmpty()); //繼續(xù)遍歷其他結(jié)點(diǎn)

cout<<endl;};template<classT>另一版本實(shí)現(xiàn):voidpostorder(BinTreeNode<Type>*T){stack<STKNode<Type>>s(10);

STKNode<Type>Cnode;

BinTreeNode<Type>*p=T;do{while(p!=NULL){Cnode.ptr=p;Cnode.tag=L;s.push(Cnode);

p=p->leftchild;}

Cnode=s.pop();p=Cnode.ptr;

第-5章-樹--數(shù)據(jù)結(jié)構(gòu)課件while(Cnode.tag==R){cout<<p->data;if(!s.IsEmpty()){Cnode=s.pop();p=Cnode.ptr;}elsereturn;}

Cnode.tag=R;s.push(Cnode);

p=p->rightchild;}while(p!=NULL||!s.IsEmpty())}while(Cnode.tag==R)aLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaRabcdeaLbLbRdLdRbRaLaReLeRcLcRaRabcdpostorder算法分析

時(shí)間復(fù)雜性入、出棧：O(n)訪問結(jié)點(diǎn)：O(n)總的時(shí)間復(fù)雜度：O(n)空間復(fù)雜性O(shè)(k),k為樹的高度postorder算法分析時(shí)間復(fù)雜性O(shè)(n)訪問結(jié)點(diǎn)：O(二叉樹遍歷的非遞歸算法(cont.)2）中序遍歷的非遞歸算法棧中：用以存放待訪問的根結(jié)點(diǎn)指針,以備在訪問該結(jié)點(diǎn)的左子樹之后再訪問該結(jié)點(diǎn)及其右子樹。二叉樹遍歷的非遞歸算法(cont.)2）中序遍歷的非遞歸算法算法思想

將棧s初始化，令指針p指向二叉樹的根結(jié)點(diǎn)，即p=T.如果指向根結(jié)點(diǎn)的指針不為空或棧非空，則：(1)如果指向根結(jié)點(diǎn)的指針非空，則將根結(jié)點(diǎn)指針進(jìn)棧，然后將指針指向該結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)，繼續(xù)遍歷

(2)如果指向根結(jié)點(diǎn)的指針為空，則將棧頂存放的數(shù)據(jù)項(xiàng)出棧，有兩種情況：若從左子樹返回，則應(yīng)該訪問當(dāng)前層根結(jié)點(diǎn)，然后將指針指向該結(jié)點(diǎn)的右子樹根結(jié)點(diǎn)，繼續(xù)遍歷；若從右子樹返回，則表明當(dāng)前層遍歷結(jié)束，應(yīng)該繼續(xù)退棧。(3)當(dāng)指針為空并且棧為空時(shí)，遍歷結(jié)束。算法思想將棧s初始化，令指針p指向二叉樹的根結(jié)點(diǎn)，即p=Tvoidinorder(BinTreeNode<Type>*T){stack<BinTreeNode<Type>*>s(10);

BinTreeNode<Type>*p=T;while(p||!s.IsEmpty()){while(p!=NULL){s.push(p);

p=p->leftchild;}if(!s.IsEmpty()){p=s.pop();cout<<p->data;

p=p->rightchild;

}elsereturn;}}voidinorder(BinTreeNode<Typacdebaadaa左空退棧訪問左空退棧訪問退棧訪問左空ec退棧訪問cc右空退棧訪問?？战Y(jié)束abcde利用棧的中序遍歷非遞歸算法acdebada左空退棧左空退棧退棧左空e退棧訪問cc右空退inorder算法分析

時(shí)間復(fù)雜性入、出棧：訪問結(jié)點(diǎn)：總的時(shí)間復(fù)雜度：O(n)O(n)O(n)空間復(fù)雜性O(shè)(k),k為樹的高度inorder算法分析時(shí)間復(fù)雜性O(shè)(n)O(n)O(n)空二叉樹遍歷的非遞歸算法(cont.)3）前序遍歷的非遞歸算法需要棧嗎？棧中結(jié)點(diǎn)的pop和push二叉樹遍歷的非遞歸算法(cont.)3）前序遍歷的非遞歸算法訪問p->data后，將p入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素p出棧，再先序遍歷p的右子樹。訪問p->data后，將p->rchild入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素p->rchild出棧，遍歷以該指針為根的子樹。

算法思想兩種方法：假設(shè)p是要遍歷樹的根指針，若p

!=

NULL訪問p->data后，將p入棧，遍歷左子樹；遍歷完左子樹返回template<classT>voidBinaryTree<T>::PreOrder(void(*visit)(BinTreeNode<T>*t)){stack<BinTreeNode<T>*>S;BinTreeNode<T>*p=root;S.Push(NULL); while(p!=NULL){ visit(p); //訪問結(jié)點(diǎn)

if(p->rightChild!=NULL)S.Push(p->rightChild);//預(yù)留右指針在棧中

if(p->leftChild!=NULL)p=p->leftChild; //進(jìn)左子樹

elseS.Pop(p); //左子樹為空

}};template<classT>cabcdedcc訪問a進(jìn)棧c左進(jìn)b訪問b進(jìn)棧d左進(jìn)空退棧d訪問d左進(jìn)空退棧c訪問c左進(jìn)e訪問e左進(jìn)空?？战Y(jié)束利用棧的前序遍歷非遞歸算法cabcdedc訪問訪問退棧退棧訪問利用棧的前序遍歷非遞歸算遍歷順序abcdef--+/*層次序遍歷二叉樹的算法層次序遍歷二叉樹就是從根結(jié)點(diǎn)開始，按層次逐層遍歷遍歷順序abcdef--+/*層次序遍歷二叉樹的算法層次序遍這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一層的結(jié)點(diǎn)直接進(jìn)到隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)訪問它們。算法是非遞歸的。這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一abcdeQa訪問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ì)abcdeQa訪問a,進(jìn)隊(duì)Qa出隊(duì)bcQb出隊(duì)cdQc出隊(duì)層次序遍歷的（非遞歸）算法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){visit(p->leftChild);Q.EnQueue(p->leftChild);}if(p->rightChild!=NULL){visit(p->rightChild);Q.EnQueue(p->rightChild);}}};

層次序遍歷的（非遞歸）算法template<classT二叉樹的建立通過(guò)算法遞歸地實(shí)現(xiàn)——已知一棵二叉樹的前序序列和中序序列，可以唯一地確定一棵二叉樹；——已知一棵二叉樹的中序序列和后序序列，可以唯一地確定一棵二叉樹；由廣義表建立二叉樹的建立通過(guò)算法遞歸地實(shí)現(xiàn)由前序序列和中序序列，建立二叉樹的遞歸算法private:BinTreeNode<Type>*CreateBT(stringpres,ins){intInpos;

string

Prestemp,Instemp;if(pres.length()==0)T=NULL;else{

temp=new

BinTreeNode;

temp->data=pres.ch[0];Inspos=0;

while

(Ins.ch[Inpos]!=T->data)Inpos++;

由前序序列和中序序列，建立二叉樹的遞歸算法private:

prestemp=pres(1,Inpos);

Instemp=ins(0,Inpos-1);

temp->leftchild=CreateBT(prestemp,Instemp);prestemp=pres(Inpos+1,pres.length()-Inpos-1);

Instemp=Ins(Inpos+1,pres.length()-Inpos-1);

temp->rightchild=CreateBT(prestemp,Instemp);returntemp;}}prestemp=pres(1,Inpos);由廣義表建立二叉樹HADBFCEFA(B(C,F(H)),D(E(,F)))廣義表由廣義表建立二叉樹HADBFCEFA(B(C,F(H)),D二叉樹對(duì)應(yīng)的廣義表有如下規(guī)定：每棵樹的根結(jié)點(diǎn)作為由子樹構(gòu)成的表的名字而放在表的前面；每一個(gè)結(jié)點(diǎn)的左右子樹用“,”分開，若只有右子樹而沒有左子樹，則逗號(hào)不能省略；在廣義表后面加一特殊符號(hào)‘@’作為結(jié)束標(biāo)志。A(B(C,F(H)),D(E(,F)))@二叉樹對(duì)應(yīng)的廣義表有如下規(guī)定：A(B(C,F(H)),D(E算法思想：遇到字母，則表明是結(jié)點(diǎn)的值，為它建立新結(jié)點(diǎn)；若該結(jié)點(diǎn)不是整個(gè)樹的根，還應(yīng)該作為左子女（k=1）或右子女（k=2）鏈接到其雙親結(jié)點(diǎn)；遇到“(”,則表明子表開始，把剛剛建立的結(jié)點(diǎn)的指針進(jìn)棧（為了括號(hào)內(nèi)孩子結(jié)點(diǎn)指向雙親結(jié)點(diǎn)用，并置k=1）遇到“)”,則表明子表結(jié)束，應(yīng)退棧遇到“,”,表示以左孩子為根的子樹已處理完畢，應(yīng)接著處理以右孩子為根的子樹，k=2A(B(C,F(H)),D(E(,F)))@算法思想：A(B(C,F(H)),D(E(,F)))@voidCreateBT(BTreeNode*BT,char*a)//a為廣義表表示{BinTreeNode*s[10];//作為存儲(chǔ)二叉樹中根結(jié)點(diǎn)指針的棧使用

inttop=-1;BT=NULL;BinTreeNode*p;intk;//k=1,處理左子樹；k=2，處理右子樹

istrstreamins(a);//把字符串a(chǎn)定義為輸入字符串流對(duì)象inscharch;ins>>ch;while(ch!=‘@’)具體算法:voidCreateBT(BTreeNode*BT,c{switch(ch){case’(’:top++;s[top]=p;k=1;break;case‘)’:top--;break;case‘,’:k=2;break;default:p=newBinTreeNode;p->data=ch;p->leftchild=p->rightchild=NULL;if(BT==NULL)BT=p;else{if(k==1)s[top]->leftchild=p;elses[top]->rightchild=p;}}//switchendins>>ch;}//whileend}A(B(C,F(H)),D(E(,F)))@{switch(ch)A(B(C,F(H)),D(E(,二叉樹的計(jì)數(shù)由前知：由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。有n個(gè)結(jié)點(diǎn)的不同的二叉樹有多少種？二叉樹的計(jì)數(shù)由前知：由二叉樹的前序序列和中序序列可唯一地確定612345789前序排列：123456789中序排列：325416879612375849前序排列：123456789中序排列：435217689612345789前序排列：12345678問題：固定前序排列,選擇所有可能的中序排列,可能構(gòu)造多少種不同的二叉樹？如果我們能夠做到結(jié)點(diǎn)編號(hào)的前序排列正好是1,2,3,…,n,那么，這棵二叉樹有多少中序排列，就能確定多少棵不同的二叉樹。當(dāng)二叉樹的前序排列為1,2,3,…,n時(shí)，可能有多少種中序排列？問題：固定前序排列,選擇所有可能的中序排列,可能構(gòu)造多少可得5種不同的二叉樹。它們的前序排列均為

123，中序序列可能是123，132，213，231，321。123123123123123若用表示進(jìn)棧表示出棧例如,有3個(gè)數(shù)據(jù){1,2,3}可得5種不同的二叉樹。它們的前序排列均為123，中序序

有0個(gè),1個(gè),2個(gè),3個(gè)結(jié)點(diǎn)的不同二叉樹如下：b0=1b1=1b2=2b3=5求解不同的二叉樹棵數(shù)設(shè)bn表示有n個(gè)結(jié)點(diǎn)的不同的二叉樹棵數(shù)。當(dāng)n很小時(shí)，有0個(gè),1個(gè),2個(gè),3個(gè)結(jié)點(diǎn)的不同二叉樹如下：計(jì)算具有n個(gè)結(jié)點(diǎn)的不同二叉樹的棵數(shù)Catalan函數(shù)bibn-i-11計(jì)算具有n個(gè)結(jié)點(diǎn)的不同二叉樹的棵數(shù)Catalan函數(shù)bi5.5線索二叉樹5.5線索二叉樹線索(Thread)：指示前驅(qū)和后繼的指針線索化二叉樹（ThreadedBinaryTree）:加了線索的二叉樹線索(Thread)：指示前驅(qū)和后繼的指針線索化二叉樹（T兩種方法：1）原有二叉樹的結(jié)構(gòu)中，增加兩個(gè)鏈域；2）利用空鏈域

如果結(jié)點(diǎn)有左孩子，則其leftchild指示其左孩子；否則指示其前驅(qū)如果結(jié)點(diǎn)有右孩子，則其rightchild指示其右孩子；否則指示其后繼設(shè)置兩個(gè)標(biāo)志：LeftThreadRightThread兩種方法：如果結(jié)點(diǎn)有左孩子，則其leftchild指示其左線索化二叉樹及其二叉鏈表表示LeftThread=0,LeftChild為左子女指針LeftThread=1,LeftChild為前驅(qū)線索RightThread=0,RightChild為右子女指針RightThread=1,RightChild為后繼指針LeftChildRightChilddataLeftThreadRightThread線索化二叉樹及其二叉鏈表表示LeftThread=0,中序線索化二叉樹的例子中序線索化二叉樹的例子帶表頭結(jié)點(diǎn)的中序穿線鏈表原來(lái)的線索化二叉樹成為表頭結(jié)點(diǎn)的左子樹帶表頭結(jié)點(diǎn)的中序穿線鏈表原來(lái)的線索化二叉樹成為表頭結(jié)點(diǎn)的左子template<classType>classThreadNode

{

friendclassThreadTree<Type>; private:

intleftThread,rightThread;ThreadNode<Type>*leftChild,*rightChild;

Typedata; public:

ThreadNode(constTypeitem)

:data(item),leftChild(NULL),rightChild(NULL),leftThread(0),rightThread(0){}};中序線索化二叉樹的類定義template<classType>classThreadTree;

template<classType>classThtemplate<classType>classThreadTree{

private:ThreadNode<Type>*root;//根

InThread(ThreadNode<Type>*current,

ThreadNode<Type>*&pre

);//建樹public:ThreadTree():root(NULL){};//構(gòu)造函數(shù)

ThreadNode<Type>*

First(ThreadNode<Type>*current);

ThreadNode<Type>*

Last(ThreadNode<Type>*current);

template<classType>classTh

ThreadNode<Type>*Next(ThreadNode<Type>*current);ThreadNode<Type>*Prior(ThreadNode<Type>*current);…………}ThreadNode<Type>*if(current->rightThread==1)

后繼為current->rightChildelse

//current->rightThread!=1

后繼為當(dāng)前結(jié)點(diǎn)右子樹的中序下的第一個(gè)結(jié)點(diǎn)（最左下）

尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼ABDECFHIKGJif(current->rightThread==1)if(current->leftThread==1)

前驅(qū)為current->leftChildelse

//current->leftThread==0

前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹

中序下的最后一個(gè)結(jié)點(diǎn)（最右下）

尋找當(dāng)前結(jié)點(diǎn)在中序下的前驅(qū)ABDECFHIKGJLif(current->leftThread==1通過(guò)中序遍歷建立中序線索化二叉樹template<classType>voidThreadTree<Type>::InThread(ThreadNode<Type>*current,ThreadNode<Type>*&pre){if(current!=NULL){ InThread(current->leftChild,pre);

//遞歸,左子樹線索化

if(current->leftChild==NULL){

current->leftChild=pre;

current->leftThread=1;

}//建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索

通過(guò)中序遍歷建立中序線索化二叉樹template<clasif(pre!=NULL&&pre->rightChild==NULL){

pre->rightChild=current;

pre->rightThread=1;}//建立前驅(qū)結(jié)點(diǎn)的后繼線索

pre=current; //前驅(qū)跟上當(dāng)前指針

InThread(current->rightChild,pre);

//遞歸,右子樹線索化

}}if(pre!=NULL&&template<classT>voidThreadTree<T>::createInThread(ThreadNode<T>*current,ThreadNode<T>*&pre){//通過(guò)中序遍歷,對(duì)二叉樹進(jìn)行線索化

if(current==NULL)return;createInThread(current->leftChild,pre);

//遞歸,左子樹線索化

if(current->leftChild==NULL){ //建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索

current->leftChild=pre;current->ltag=1;}template<classT>if(pre!=NULL&&pre->rightChild==NULL) //建立前驅(qū)結(jié)點(diǎn)的后繼線索

{pre->rightChild=current;pre->rtag=1;} pre=current; //前驅(qū)跟上,當(dāng)前指針向前遍歷

createInThread(current->rightChild,pre); //遞歸,右子樹線索化};if(pre!=NULL&&pre->r0A00B00C00D00E0rootpre==NULLcurrent0A00B00A0

1B00C00D00E0rootpre==NULLcurrent0A01B00A0

1B00C0

1D00E0rootprecurrent0A01B00A0

1B00C0

1D1

0E0rootprecurrent0A01B00A0

1B00C0

1D1

1E0rootprecurrent0A01B00A0

1B00C0

1D1

1E1

rootprecurrent0A01B00A0

1B00C1

1D1

1E1

rootpre后處理0A01B0在中序線索化二叉樹中部分成員函數(shù)的實(shí)現(xiàn)template<classType>

ThreadNode<Type>*

ThreadTree<Type>::First(ThreadNode<Type>*current){//函數(shù)返回以*current為根在線索化二叉樹中//的中序序列下的第一個(gè)結(jié)點(diǎn)

ThreadNode<Type>*p=current;

while(p->leftThread==0)p=p->leftChild;

//最左下的結(jié)點(diǎn)

returnp;}在中序線索化二叉樹中部分成員函數(shù)的實(shí)現(xiàn)template<classType>ThreadNode<Type>*ThreadTree<Type>::Next(ThreadNode<Type>*current){//函數(shù)返回在線索化二叉樹中結(jié)點(diǎn)*current在//中序下的后繼結(jié)點(diǎn)

ThreadNode<Type>*p=current->rightChild;

if(current->rightThread==0)returnFirst(p);

//rightThread==0,表示有右子女

else

returnp; //rightThread==1,直接返回后繼線索}

template<classType>template<classType>voidThreadTree<Type>::Inorder(){//線索化二叉樹的中序遍歷

ThreadNode<Type>*p;for(p=First();p!=NULL;p=Next())

cout<<p->data<<endl;}template<classType>void前序線索化二叉樹前序序列

ABDCE前序線索化二叉樹前序序列在前序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼在前序線索化二叉樹中在前序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的前驅(qū)在前序線索化二叉樹中后序線索化二叉樹后序序列

DBECA在后序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼后序線索化二叉樹后序序列在后序線索化二叉樹中遍歷二叉樹,并將其中序線索化遍歷二叉樹,并將其中序線索化template<classType>voidThreadTree<Type>::CreateInThread

(){

ThreadNode<Type>*pre;

root=newThreadNode<Type>;//創(chuàng)建根結(jié)點(diǎn)

root→leftThread=1;root→rightThread=0;if(this==NULL){//空二叉樹

root→leftChild=root;

root→rightChild=root;}else{

current=root→leftChild=this;

root→leftThread=0;

pre=root;

InThread(current,pre);

pre→rightChild=root;pre→rightThread=1;}}template<classType>voidtemplate<classType>voidThreadTree<Type>::InThread(ThreadNode<Type>*current,ThreadNode<Type>*&pre){if(current!=NULL){ InThread(current->leftChild,pre);

//遞歸,左子樹線索化

if(current->leftChild==NULL){

current->leftChild=pre;

current->leftThread=1;

}//建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索

if(pre!=NULL&&pre->rightChild==NULL){

pre->rightChild=current;

pre->rightThread=1;}//建立前驅(qū)結(jié)點(diǎn)的后繼線索

pre=current; //前驅(qū)跟上當(dāng)前指針

InThread(current->rightChild,pre);//遞歸,右子樹線索化

}}template<classType>中序線索化二叉樹的操作插入刪除中序線索化二叉樹的操作插入插入將值為r的新結(jié)點(diǎn)插入到中序線索二叉樹中作為右子女插入作為左子女插入原則:必須修改原有的前驅(qū),后繼線索,使整個(gè)原有的中序序列不但能夠保留,而且新結(jié)點(diǎn)插入后也能正確地排入這個(gè)序列sr插入將值為r的新結(jié)點(diǎn)插入到中序線索二叉樹中原則:必須修改原有srs無(wú)右子女s有右子女以該右子女為根的子樹成為r的右子樹作為右子女插入srs無(wú)右子女以該右子女為根的子樹成為r的右子樹作為右子女插作為左子女插入srs無(wú)左子女s有左子女作為左子女插入srs無(wú)左子女前序線索化二叉樹前序序列

ABDCE前序線索化二叉樹前序序列在前序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼在前序線索化二叉樹中在前序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的前驅(qū)在前序線索化二叉樹中后序線索化二叉樹后序序列

DBECA在后序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼后序線索化二叉樹后序序列在后序線索化二叉樹中樹的存儲(chǔ)表示樹的廣義表表示5.6樹與森林ABCDEFG葉結(jié)點(diǎn)分支結(jié)點(diǎn)根結(jié)點(diǎn)廣義表原子結(jié)點(diǎn)子表結(jié)點(diǎn)表頭結(jié)點(diǎn)樹的存儲(chǔ)表示樹的廣義表表示5.6樹與森林ABCDEFG葉結(jié)父指針表示法ABCDEFGdataparentABCDEFG-10001130123456父指針表示法ABCDEFGdataparentABABCDEFG適用于：等數(shù)量的鏈域ABCDEFG每個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)相等，等于樹的度（degree）子女指針表示法

datachild1child2child3childdABCDEFG適用于：等數(shù)量的鏈域ABCDEFG子女鏈表表示無(wú)序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個(gè)子女結(jié)點(diǎn)。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG012345