數據結構：第六章 樹與森林

《數據結構：第六章 樹與森林》由會員分享，可在線閱讀，更多相關《數據結構：第六章 樹與森林（119頁珍藏版）》請在裝配圖網上搜索。

1、template class Tree public:Tree();Tree();position Root();BuildRoot(const Type&value);position FirstChild(position p);position NextSibling(position p,position v);position Parent(position p);Type Retrieve(position p);position InsertChild(const position p,const Type&value);position DeleteChild(position

2、 p,int i);void DeleteSubTree(position t);int IsEmpty();template class BinaryTree public:BinaryTree();BinaryTree(BinTreeNode*lch,BinTreeNode*rch,Type item);int IsEmpty();BinTreeNode*Parent();BinTreeNode*LeftChild();BinTreeNode*RightChild();int Insert(const Type&item);int Find(const Type&item)const;Ty

3、pe GetData()const;BinTreeNode*GetRoot()const;完全二叉樹的數組表示完全二叉樹的數組表示 一般二叉樹的數組表示一般二叉樹的數組表示 單支樹單支樹二叉樹鏈表表示的示例二叉樹鏈表表示的示例二叉鏈表的靜態結構二叉鏈表的靜態結構template class BinaryTree;template Class BinTreeNode friend class BinaryTree;public:BinTreeNode():leftChild(NULL),rightChild(NULL)BinTreeNode(Type item,BinTreeNode*left=

4、NULL,BinTreeNode*right=NULL):data(item),leftChild(left),rightChild (right)Type&GetData()const return data;BinTreeNode*GetLeft()const return leftChild;BinTreeNode*GetRight()const return rightChild;void SetData(const Type&item)data=item;void SetLeft(BinTreeNode *L)leftChild=L;void SetRight(BinTreeNode

5、 *R)rightChild=R;private:BinTreeNode*leftChild,*rightChild;Type data;template class BinaryTree public:BinaryTree():root(NULL)BinaryTree(Type value):RefValue(value),root(NULL)virtual BinaryTree()destroy(root);virtual int IsEmpty()return root=NULL?1:0;virtual BinTreeNode *Parent(BinTreeNode *current)r

6、eturn root=NULL|root=current？NULL:Parent(root,current);virtual BinTreeNode *LeftChild(BinTreeNode *current)return root!=NULL?currentleftChild:NULL;virtual BinTreeNode *RightChild(BinTreeNode *current)return root!=NULL?currentrightChild:NULL;virtual int Insert(const Type&item);virtual int Find(const

7、Type&item)const;BinTreeNode *GetRoot()const return root;friend istream&operator (istream&in,BinaryTree&Tree)friend ostream&operator (ostream&out,BinaryTree&Tree)private:BinTreeNode *root;Type RefValue;BinTreeNode *Parent(BinTreeNode *start,BinTreeNode *current);int Insert(BinTreeNode*¤t,const

8、Type&item)void Traverse(BinTreeNode*current,ostream&out)const int Find(BinTreeNode*current,const Type&item)const void destroy(BinTreeNode*current);template void BinaryTree:destroy(BinTreeNode*current)if(current!=NULL)destroy(currentleftChild);destroy(currentrightChild);delete current;Template BinTre

9、eNode *BinaryTree:Parent(BinTreeNode*start,BinTreeNode *cuurent)if(start=NULL)return NULL;if(startleftChild=current|startrightChild =current)return start;BinTreeNode *p;if(p=Parent(startleftChild,current)!=NULL)return p;else return Parent(startrightChild,current);Template void BinaryTree:Traverse(Bi

10、nTreeNode *current,ostream&out)const if(current!=NULL)out currentdata ;Traverse(currentleftChild,out);Traverse(currentrightChild,out);Template istream&operator (istream&in,BinaryTree&Tree)Type item;cout 構造二叉樹構造二叉樹:n;cout 輸入數據輸入數據(用用 Tree.RefValue item;while(item!=Tree.RefValue)Tree.Insert(item);cout

11、 輸入數據輸入數據(用用 Tree.RefValue item;return in;Template ostream&operator (ostream&out,BinaryTree&Tree)out “二叉樹的前序遍歷二叉樹的前序遍歷.n;Tree.Traverse(Tree.root,out);out endl;return out;emplate void BinaryTree:InOrder()InOrder(root);template void BinaryTree:InOrder(BinTreeNode *current)if(current!=NULL)InOrder(curr

12、entleftChild);cout currentdata;InOrder(currentrightChild);template void BinaryTree:PreOrder()PreOrder(root);template void BinaryTree:PreOrder(BinTreeNode *current)if(current!=NULL)cout currentdata;PreOrder(currentleftChild);PreOrder(currentrightChild);二叉樹遞歸的后序遍歷算法二叉樹遞歸的后序遍歷算法template void BinaryTree

13、:PostOrder()PostOrder(root);template void BinaryTree:PostOrder(BinTreeNode *current)if(current!=NULL)PostOrder(currentleftChild);PostOrder(currentrightChild);cout currentdata;利用二叉樹利用二叉樹后序遍歷后序遍歷計算二叉樹結點個數及計算二叉樹結點個數及二叉樹的高度二叉樹的高度template int BinaryTree:Size(const BinTreeNode *t)const if(t=NULL)return 0;

14、else return 1+Size(tleftChild)+Size(trightChild);template int BinaryTree:Depth(const BinTreeNode *t)const if(t=NULL)return-1;else return 1+Max(Depth(tleftChild),Depth(trightChild);(Tree Iterator)template class TreeIterator public:TreeIterator(const BinaryTree&BT):T(BT),current(NULL)virtual TreeItera

15、tor()virtual void First()=0;virtual void operator+()=0;int operator+()const return current!=NULL;const Type&operator()()const;protected:const BinaryTree&T;const BinTreeNode *current;private:TreeIterator(const TreeIterator&)const TreeIterator&operator=(const TreeIterator&);template const Type&TreeIte

16、rator:operator()()const if(current=NULL)cout 非法訪問非法訪問 endl;exit(1);return currentGetData();PopTim=0,12，結點地址結點地址*Node 退棧次數退棧次數 PopTimtemplate struct stkNode const BinTreeNode *Node;/結點指針結點指針 int PopTim;/退棧次數退棧次數 stkNode(const BinTreeNode *N=NULL):Node(N),PopTim(0)/構造函數構造函數template class PostOrder:pub

17、lic TreeIterator public:PostOrder(const BinaryTree&BT);PostOrder()void First();/定位到后序次序下第一個結點定位到后序次序下第一個結點 void operator+();/定位到后序次序下的下一個結點定位到后序次序下的下一個結點protected:Stack StkNode st;/工作棧工作棧template PostOrder:PostOrder(const BinaryTree&BT):TreeIterator (BT)st.Push(StkNode (BT.GetRoot();template void Po

18、stOrder:First()st.MakeEmpty();if(BT.GetRoot()!=NULL)st.Push(StkNode (BT.GetRoot();operator+();template void PostOrder:operator+()if(st.IsEmpty()if(current=NULL)cout 已經遍歷結束已經遍歷結束 endl;exit(1);current=NULL;return;/遍歷完成遍歷完成 StkNode Cnode;for(;)/循環循環,找后序下的下一個結點找后序下的下一個結點 Cnode=st.Pop();if(+Cnode.PopTim=

19、3)/從右子樹退出從右子樹退出 current=Cnode.Node;return;st.Push(Cnode);/否則加一進棧否則加一進棧 if(Cnode.PopTim=1)/=1,左子女進棧左子女進棧 if(Cnode.NodeGetLeft()!=NULL)st.Push(StkNode (Cnode.NodeGetLeft();else /=2,右子女進棧右子女進棧 if(Cnode.NodeGetRight()!=NULL)st.Push(StkNode (Cnode.NodeGetRight();template class InOrder:public PostOrder pu

20、blic:InOrder(BinaryTree&BT):PostOrder (BT)void First();void operator+();template void InOrder:operator+()if(st.IsEmpty()if(current=NULL)cout 已經遍歷完成已經遍歷完成 endl;exit(1);current=NULL;return;StkNode Cnode;for(;)/循環循環,找中序下的下一個結點找中序下的下一個結點 Cnode=st.Pop();/退棧退棧 if(+Cnode.TimPop=2)/從左子樹退出從左子樹退出 current=Cnod

21、e.Node;/成為當前結點成為當前結點 if(Cnode.NodeGetRight()!=NULL)st.Push(StkNode (/右子女進棧右子女進棧 node.NodeGetRight();return;st.Push(Cnode);/否則加一進棧否則加一進棧 if(Cnode.NodeGetLeft()!=NULL)st.Push(StkNode (/左子女進棧左子女進棧 Cnode.NodeGetLeft();template class LevelOrder:public TreeIterator public:LevelOrder(const BinaryTree&BT);L

22、evelOrder()void First();void operator+();protected:Queue const BinTreeNode *qu;template LevelOrder:LevelOrder(const BinaryTree&BT):TreeIterator (BT)qu.EnQueue(BT.GetRoot();template viod LevelOrder:First()/初始化：只有根結點在隊列中初始化：只有根結點在隊列中 qu.MakeEmpty();if(BT.GetRoot()qu.EnQueue(BT.GetRoot();operator+();te

23、mplate void LevelOrder:operator+()if(qu.IsEmpty()if(current=NULL)cout 已經遍歷完成已經遍歷完成 endl;exit(1);current=NULL;return;current=qu.DeQueue();/當前結點是退隊結點當前結點是退隊結點 if(currentGetLeft()!=NULL)/其左子女其左子女 qu.EnQueue(currentGetLeft();/進隊列進隊列 if(currentGetRight()!=NULL)/其右子女其右子女 qu.EnQueue(currentGetRight();/進隊列進

24、隊列template class ThreadNode friend class ThreadTree;friend class ThreadInorderIterator;private:int leftThread,rightThread;ThreadNode*leftChild,*rightChild;Type data;public:ThreadNode(const Type item):data(item),leftChild(NULL),rightChild(NULL),leftThread(0),rightThread(0);template class ThreadTree f

25、riend class ThreadInorderIterator;public:private:ThreadNode*root;template class ThreadInorderIterator public:ThreadInorderIterator(ThreadTree&Tree):T(Tree)current=T.root;ThreadNode*First();ThreadNode*Last();ThreadNode*Next();ThreadNode*Prior();private:ThreadTree&T;ThreadNode*current;帶表頭結點的中序穿線鏈表帶表頭結

26、點的中序穿線鏈表if(currentrightThread=1)if(currentrightChild!=T.root)后繼為后繼為 currentrightChild else 無后繼無后繼else /currentrightThread!=1 if(currentrightChild!=T.root)后繼為當前結點右子樹后繼為當前結點右子樹 的中序下的第一個結點的中序下的第一個結點 else 出錯情況出錯情況ABDECFHIKGJLif(currentleftThread=1)if(currentleftChild!=T.root)前驅為前驅為currentleftChild else

27、無前驅無前驅else/currentleftThread=0 if(currentleftChild!=T.root)前驅為當前結點左子樹的前驅為當前結點左子樹的 中序下的最后一個結點中序下的最后一個結點 else 出錯情況出錯情況ABDECFHIKGJLtemplate ThreadNode*ThreadInorderIterator:First()while(currentleftThread=0)current=currentleftChild;return current;template ThreadNode*ThreadInorderIterator:Next()ThreadNod

28、e*p=currentrightChild;if(currentrightThread=0)while(pleftThread=0)p=pleftChild;current=p;if(current=T.root)return NULL;else return current;template void ThreadInorderIterator:Inorder()/線索化二叉樹的中序遍歷線索化二叉樹的中序遍歷 ThreadNode*p;for(p=First();p!=NULL;p=Next()cout pdata endl;template void ThreadTree:InThread

29、(ThreadNode*current,ThreadNode*pre)if(current!=NULL)InThread(currentleftChild,pre);if(currentleftChild=NULL)currentleftChild=pre;currentleftThread=1;if(prerightChild=NULL)prerightChild=current;prerightThread=1;pre=current;InThread(currentrightChild,pre);template void ThreadTree:CreateInThread()Threa

30、dNode*pre;root=new ThreadNode;rootleftThread=1;rootrightThread=0;if(this=NULL)rootleftChild=root;rootrightChild=root;else current=rootleftChild=this;rootleftThread=0;pre=root;InThread(current,pre);prerightChild=root;prerightThread=1;template class MinPQ public:Virtual void Insert(const Type&)=0;Virt

31、ual Type*RemoveMin(Type&)=0;最小優先級隊列類的定義最小優先級隊列類的定義&template class MinHeap:public MinPQ public:MinHeap(int maxSize)const;MinHeap(Type arr,int n);MinHeap()delete heap;const MinHeap&operator=(const MinHeap&R);int Insert(const Type&x);int RemoveMin(Type&x);int IsEmpty()const return CurrentSize=0;int IsF

32、ull()const return CurrentSize=MaxHeapSize;void MakeEmpty()CurrentSize=0;private:enum DefaultSize=10;Type*heap;int CurrentSize;int MaxHeapSize;void FilterDown(int i,int m);void FilterUp(int i);template MinHeap:MinHeap(int maxSize)/根據給定大小根據給定大小maxSize,建立堆對象建立堆對象 MaxHeapSize=DefaultSize maxSize?maxSize

33、:DefaultSize;/確定堆大小確定堆大小 heap=new Type MaxHeapSize;/創建堆空間創建堆空間 CurrentSize=0;/初始化初始化template MinHeap:MinHeap(Type arr,int n)/根據給定數組中的數據和大小根據給定數組中的數據和大小,建立堆對象建立堆對象 MaxHeapSize=DefaultSize=0)/從下到上逐步擴大從下到上逐步擴大,形成堆形成堆 FilterDown(currentPos,CurrentSize);/從從currentPos開始開始,到到CurrentSize為止為止,調整調整 currentPos

34、-;自下向上逐步調整為最小堆自下向上逐步調整為最小堆template void MinHeap:FilterDown(const int start,const int EndOfHeap)int i=start,j=2*i+1;/j 是是 i 的左子女的左子女 Type temp=heapi;while(j=EndOfHeap)if(j heapj+1.key)j+;/兩子女中選小者兩子女中選小者 if(temp.key=heapj.key)break;else heapi=heapj;i=j;j=2*j+1;heapi=temp;template int MinHeap:Insert(co

35、nst Type&x)/在堆中插入新元素在堆中插入新元素 x if(CurrentSize=MaxHeapSize)/堆滿堆滿 cout 堆已滿堆已滿 endl;return 0;heapCurrentSize=x;/插在表尾插在表尾 FilterUp(CurrentSize);/向上調整為堆向上調整為堆 CurrentSize+;/堆元素增一堆元素增一 return 1;template void MinHeap:FilterUp(int start)/從從 start 開始開始,向上直到向上直到0,調整堆調整堆 int j=start,i=(j-1)/2;/i 是是 j 的雙親的雙親 Ty

36、pe temp=heapj;while(j 0)if(heapi.key=temp.key)break;else heapj=heapi;j=i;i=(i-1)/2;heapj=temp;template int MinHeap:RemoveMin(Type&x)if(!CurrentSize)cout “堆已空堆已空 endl;return 0;x=heap0;/最小元素出隊列最小元素出隊列 heap0=heapCurrentSize-1;CurrentSize-;/用最小元素填補用最小元素填補 FilterDown(0,CurrentSize-1);/從從0 0號位置開始自頂向下調整為堆號

37、位置開始自頂向下調整為堆 return 1;樹的廣義表表示樹的廣義表表示(結點的結點的utype域沒有畫出域沒有畫出)data child1child2child3childd datafirstChildnextSiblingtemplate class Tree;template class TreeNode friend class Tree;private:Type data;TreeNode*firstChild,*nextSibling;TreeNode(Type value=0,TreeNode*fc=NULL,TreeNode*ns=NULL):data(value),firs

38、tChild(fc),nextSibling(ns);template class Tree public:Tree()root=current=NULL;private:TreeNode*root,*current;void PreOrder(ostream&out,TreeNode*p);int Find(TypeNode*p,Type target);void RemovesubTree(TreeNode*p);int FindParent(TreeNode*t,*p);template void Tree:BuildRoot(Type rootVal)/建立樹的根結點建立樹的根結點,并

39、使之成為樹的當前結點并使之成為樹的當前結點 root=current=new TreeNode (rootVal);template int TreeNode:Root()/讓樹的根結點成為樹的當前結點讓樹的根結點成為樹的當前結點 if(root=NULL)current=NULL;return 0;else current=root;return 1;template int Tree:Parent()/在樹中尋找當前結點的雙親在樹中尋找當前結點的雙親,使之成為當前結點使之成為當前結點 TreeNode*p=current,*t;if(current=NULL|current=root)cu

40、rrent=NULL;return 0;t=root;int k=FindParent(t,p);return k;template int Tree:FirstChild()/在樹中尋找當前結點的長子在樹中尋找當前結點的長子,使之成為當前結點使之成為當前結點 if(current!=NULL¤tfirstChild !=NULL)current=currentfirstChild;return 1;current=NULL;return 0;Template int Tree:NextSibling()/在樹中尋找當前結點的兄弟在樹中尋找當前結點的兄弟,使之成為當前結點使之成為當

41、前結點if(current!=NULL¤tnextSibling!=NULL)current=currentnextSibling;return 1;current=NULL;return 0;template int Tree:FindParent(TreeNode*t,*p)/在根為在根為 t 的樹中尋找的樹中尋找 p 的雙親的雙親,使之成為當前結點使之成為當前結點 TreeNode*q=tfirstChild;while(q!=NULL&q!=p)/循根的長子的兄弟鏈循根的長子的兄弟鏈,遞歸在子樹中搜索遞歸在子樹中搜索 if(int i=FindParent(TreeNode

42、*q,*p)!=0)return i;q=qnextSibling;if(q!=NULL&q=p)current=t;return 1;else return 0;/未找到雙親未找到雙親,當前結點不變當前結點不變template int Tree:Find(Type target)if(IsEmpty()return 0;return Find(root,target);template int Tree:Find(TreeNode *p,Type target)/在根為在根為 p 的樹中尋找值為的樹中尋找值為 target 的結點的結點,找到后找到后/該結點成為當前結點該結點成為當前結點,否

43、則當前結點不變。函數否則當前結點不變。函數/返回成功標志：返回成功標志：=1,搜索成功搜索成功;=0,搜索失敗搜索失敗 int result=0;if(pdata=target)result=1;current=p;else TreeNode*q=pfirstChild;while(q!=NULL&!(result=Find(q,target)q=qnextSibling;return result;template void Tree:PreOrder()if(!IsEmpty()visit();/訪問根結點訪問根結點 TreeNode*p=current;/暫存當前結點暫存當前結點 int

44、 i=FirstChild();/當前結點轉到長子當前結點轉到長子 while(i)PreOrder();i=NextSibling();/遞歸先根遍歷各棵子樹遞歸先根遍歷各棵子樹 current=p;/遞歸完恢復當前結點遞歸完恢復當前結點 template void Tree:PostOrder()if(!IsEmpty()TreeNode*p=current;/暫存當前結點暫存當前結點 int i=FirstChild();/當前結點轉到長子當前結點轉到長子 while(i)PostOrder();i=NextSibling();/遞歸后根遍歷各棵子樹遞歸后根遍歷各棵子樹 current=

45、p;/遞歸完恢復當前結點遞歸完恢復當前結點 visit();/訪問根結點訪問根結點 template void Tree:NorecPreOrder()StackTreeNode*st(DefaultSize);TreeNode*p=current;do while(!IsEmpty()/從根沿長子鏈向下從根沿長子鏈向下 visit();st.Push(current);/邊訪問邊進棧邊訪問邊進棧 FirstChild();while(IsEmpty()&!st.IsEmpty()current=st.Pop();NextSibling();/無子女或無兄弟無子女或無兄弟,退棧退棧,轉向下一兄

46、弟轉向下一兄弟 while(!IsEmpty();/?？諚？?退出循環退出循環 current=p;template void Tree:PostOrder1()StackTreeNode*st(DefaultSize);TreeNode*p=current;do while(!IsEmpty()/從根沿長子鏈向下從根沿長子鏈向下 st.Push(current);FirstChild();/進棧進棧 while(IsEmpty()&!st.IsEmpty()current=st.Pop();visit();NextSibling();/無子女或無兄弟無子女或無兄弟,退棧退棧,訪問訪問,轉向兄

47、弟轉向兄弟 while(!IsEmpty();current=p;template void Tree:LevelOrder()QueueTreeNode*Qu(DefaultSize);if(!IsEmpty()TreeNode*p=current;Qu.EnQueue(current);/根進隊列根進隊列 while(!Qu.IsEmpty()/隊列不空隊列不空 current=Qu.DeQueue();visit();/退出隊列退出隊列,訪問訪問 FirstChild();/轉向長子轉向長子 while(!IsEmpty()/結點指針不空結點指針不空 Qu.EnQueue(current

48、);NextSibling();current=p;。123，bnnnnnnnnC111122()!1021)(logniiPL10niiilwWPL1021)(logniiPL332222110template class ExtBinTree;template class Element friend class ExtBinTree;private:Type data;Element*leftChild,*rightChild;template class ExtBinaryTree public:ExtBinTree(ExtBinTree&bt1,ExtBinTree&bt2)root

49、leftChild=bt1.root;rootrightChild=bt2.root;rootdata.key=bt1.rootdata.key+bt2.rootdata.key;protected:const int DefaultSize=20;Element *root;/擴充二叉樹的根擴充二叉樹的根 MinHeap ExtBinTree hp;/最小堆最小堆template void HuffmanTree(Type*fr,int n,ExtBinTree&newtree)ExtBinTree&first,&second;ExtBinTree NodeDafualtSize;if(n

50、DefaultSize)cout “大小大小 n”n “超出了數組邊界超出了數組邊界”endl;return;for(int i=0;i n;i+)Nodei.rootdata.key=fri;Nodei.rootleftChild=Nodei.rootrightChild=NULL;/傳送初始權值傳送初始權值 hp.MinHeap(Node,n);for(int i=0;i n-1;i+)/建立霍夫曼樹的過程，做建立霍夫曼樹的過程，做n-1趟趟 hp.DeleteMin(first);/選根權值最小的樹選根權值最小的樹 hp.DeleteMin(second);/選根權值次小的樹選根權值次小的樹 newtree=new ExtBinTree (first,second);/建新的根結點建新的根結點 hp.Insert(newtree);/形成新樹插入形成新樹插入 return hp.RemoveMin(newtree);