计算机专业课讲义数据结构-ds06树和森林

树和森林的概二叉树(Binary二叉树的表二叉树遍(BinaryTreeTraversal)线索化二叉(ThreadedBinaryTree)堆(Heap)树与森林(Tree&二叉树的计(Huffman树和森林的概树的定树是由n(n0)个结点组成的有限集合。如果0，称为空树；如果n0，mm0个互不0,1,…,-1，每个集合又是一(subee)。每棵子树0个或多个直接后继。(child)

子孙(descendant)

森林树的抽象数据类template<classType>classTree{Tree(~Tree(positionRoot(BuildRoot(constType&valuepositionFirstChild(positionppositionNextSibling(positionp,positionvpositionParent(positionp);TypeRetrieve(positionp);positionInsertChild(constpositionconstType&valuepositionDeleteChild(positionp,inti);voidDeleteSubTree(positiont);intIsEmpty(}(Binary二叉树的五种不同形性质1若二叉树的层次从0开始则在二叉树的i层最多有2i个结点。(i0)[证明用数学归纳法性质2高度为k的二叉树最多有2k+1-1个结点。(k-1)[证明用求等比级数前k项和的公式性质3对任何一棵二叉树如果其叶结点个数n0,度为2的非叶结点个数为n2则数为n，总边数为en=n0+n1+ e=2n2+n1=n-因此2n2n1n0n1n2-n2=n0- n0=n2+定义1满二叉树(FullBinary定义2完全二叉树(CompleteBinary性质4具有nlog2(n+1)-2h1n2h+112hn+12h+1取对h<log2(n+1)h+1性质5如果将一棵有n个结点的完全二叉树自顶 0,1,2,…, 放于一个一维数组中,并简称 点i(0in-1。则有以下关系：若i0i无双若i0i的双亲为(i-若2*i+1<n,则i的左 若2*i+2<n,则i的 为i为偶数,且i!=0,则其左兄弟为i-1i为奇数且in-1则其右兄弟为i+1i所在层次为log2二叉树的抽象数据类BinaryTree(BinTreeNode<Type>*lch,BinTreeNode<Type>*rch,Typeitem);intIsEmpty();BinTreeNode<Type>*Parent();BinTreeNode<Type>*LeftChild();BinTreeNode<Type>*RightChild();intInsert(constType&item);intFind(constType&item)const;TypeGetData()const;BinTreeNode<Type>*GetRoot()const;}二叉树的表数组表完全二叉树的数组表 一般二叉树的数组表全二叉树那样，可能会浪费很多空间，单支树就是一个情况。链表表

单支二叉树链表表示的示二叉链表的静二叉树的类定template<classType>classtemplate<classType>ClassBinTreeNode{friendclassBinaryTree;BinTreeNode():leftChildrightChild(NULL){BinTreeNode(Typeitem,BinTreeNode<Type>*left=NULL,BinTreeNode<Type>*right=NULL):data(item),leftChild(left),rightChild(right){}Type&GetData()const{returndata;{returnleftChild;{returnrightChild;}voidSetData(constType&item){data=item;voidSetLeft(BinTreeNode<Type>*L{leftChild=L;voidSetRight(BinTreeNode<Type>*R{rightChild=R;BinTreeNode<Type>*leftChild,*rightChild;Typedata;template<classType>classBinaryTree{BinaryTree():root(NULL){BinaryTree(Typevalue):RefValueroot(NULL){virtual~BinaryTree(){destroy(root);}virtualintIsEmpty(){returnroot==NULL?1:0;}virtualBinTreeNode<Type>*Parent({returnroot==NULL||root==current？NULL:Parent(root,current);}{returnroot!=NULLcurrent→leftChild:NULL;{returnroot!=NULLcurrent→rightChild:NULL;}virtualintInsert(constType&item);virtualintFind(constType&item)BinTreeNode<Type>*GetRoot(){returnroot;friendistream&operator>>(istream&in,BinaryTree<Type>&Tree)friendostream&operator<<(ostream&out,BinaryTree<Type>&Tree)TypeRefValue;BinTreeNode<Type>*Parent(BinTreeNode<Type>*start,intInsert(BinTreeNode<Type>*¤t,constType&item)ostream&out)constType&item)voiddestroy(BinTreeNode<Type>二叉二叉树部分成员函数的实destroy(BinTreeNode<Type>*current){if(current!=NULL)destroy(current→leftChild);destroy(current→rightChild);deletecurrent;}}*start,BinTreeNode<Type>*cuurent){if(start==NULL)returnNULL;if(start→leftChild==current||==current)returnstart;BinTreeNode<Type>*p;if((p=Parent(start→leftChild,current)!=NULL)returnelsereturnParent(start→rightChild,current}Traverse(BinTreeNode<Type>*current,ostream&out)const{if(current!=NULL)out<<current→data<<‘’;Traverse(current→leftChild,out);Traverse(current→rightChild,out);}}Template<classType>istream&operator>>(istream&in,BinaryTree<Type>&Tree){cout构造二叉树:\ncout输入数(Tree.RefValue<<"结束):";in>>while(item!=Tree.RefValue)Tree.Insert(itemcout输入数(Tree.RefValue<<"结束):";in>>}return}Template<classType>ostream&operator<<(ostream&out,BinaryTree<Type>&Tree){out二叉树的前序遍历out<<endl;returnout;} 根结点记作遍历根的左子树记作遍历根的右子树记作则可能的遍历次序前序VLR镜像VRL中序LVR镜像RVL后序LRV镜像RLV(Inorder中序遍历左子(L)；根结(V)；中序遍历右子树(R)遍历结a+b*c-d-e/

表达式语法二叉树递归的二叉树递归的中序遍历算InOrder(root}InOrder(BinTreeNode<Type>*current){if(current!=NULL){InOrder(current→leftChild);cout<<current→data;InOrder(current→rightChild}}中序遍历二叉树的递归过程图(Preorder前序遍历左子树(L)；(R)-+a*b-cd/e二叉树递归的二叉树递归的前序遍历算PreOrder(root}PreOrder(BinTreeNode<Type>*current){if(current!=NULL){cout<<current→data;PreOrder(current→leftChild);}}(Postorder后序遍历左子树(L)；(R)；根结点(V)。abcd-*+ef/二叉树递归的后序遍历算template<classType>voidBinaryTree<Type>::PostOrder(){PostOrder(root);}PostOrder(BinTreeNode<Type>*current){if(current!=NULL)PostOrder(current→leftChild);PostOrder(current→rightChild);cout<<current→data;}}利用二叉树后序遍历计算二叉树结点个数及二叉树的高度Size(constBinTreeNode<Type>*t)const{if(t==NULL)returnelsereturn1+Size(t→leftChild+Size(t→rightChild}Depth(constBinTreeNode<Type>*t)const{if(t==NULL)return-elsereturn1+Max(Depth(t→leftChildDepth(t→rightChild)}template<classType>classTreeIterator{TreeIterator(constBinaryTree<Type>&BT)T(BT),current(NULL){}virtual~TreeIterator(){}virtualvoidFirst()=virtualvoidoperator++()=intoperator+()const{returncurrent!=NULL;}constType&operator()()const;constBinTreeNode<Type>*current;TreeIterator(constTreeIterator&){}constTreeIterator&operator=(constTreeIterator&template<classType>constType<Type>::operator()()const{if(current==NULL){cout<<" "<<endl;exit(1);}returncurrent→GetData();} 走过的结点，设置一个工作栈退退栈次结点PopTim0,1或2，表示第几次退栈，用以 后序遍历游标类的定template<classType>structstkNodeconstBinTreeNode<Type>*Node; int //退栈次stkNode(constBinTreeNode<Type>*NNULLNode(NPopTim(0) //构造}template<classType>classPostOrder:publicTreeIterator<Type>{PostOrder(constBinaryTree<Type>&BT~PostOrder(){voidFirst(); voidoperator++();//定位到后序次序下的下一个结StackStkNode<Type //工作}后序游标类成员函数的PostOrder(constBinaryTree<Type>&BT)st.Push(StkNode<Type>(BT.GetRoot())}template<classType>voidPostOrderFirst()st.MakeEmpty(if(BT.GetRoot()!=NULLst.Push(StkNode<Type>(BT.GetRoot()));operator++();}template<classType>voidPostOrder<Type>::operator++(){if(st.IsEmpty())if(current==NULL)cout已经遍历结束endl;exit}currentNULL; //遍历}for(;;) //循环,找后序下的下一个结Cnode=st.Pop(if ode.PopTim3//从右子树退{current=Cnode.Node;return;st.Push(Cnode); //否则加一进栈if(Cnode.PopTim==1){ //=1,左 if(Cnode.Node→GetLeft()!=NULLst.Push(StkNode<Type>Cnode.Node→GetLeft())}else //=2, 进if(Cnode.Node→GetRight()!=NULLst.Push(StkNode<Type>Cnode.Node→GetRight())}}} 中序遍历也要使用一个递归工作栈st中序游标类的template<classType>classInOrder:publicPostOrder<Type>{InOrder(BinaryTree<Type>&BT)PostOrder<Type>(BT){}voidFirst();voidoperator++(中序游标类operator++()操作的实现template<classTypevoidInOrder<Type>::operator++(){if(st.IsEmpty())if(current==NULLcout已经遍历完成endl;exit(1)current=NULL;}StkNode<Type>for(;; //循环,找中序下的下一个结Cnodest.Pop //退if(ode.TimPop==2){//从左子树退出current=Cnode.Node; if(Cnode.Node→GetRight()!=NULL)st.PushStkNode<Type(//右node.Node→GetRight())}st.Push(Cnode); if(Cnode.Node→GetLeft()!=NULL)st.Push(StkNode<Type> // 进Cnode.Node→GetLeft())}}从根开始逐 用FIFO队列实现遍历顺层次序游标类的定template<classType>classLevelOrder:publicTreeIterator<Type>{LevelOrder(constBinaryTree<Type>&BT~LevelOrder(){}voidFirst();voidoperator++();Queue<constBinTreeNode<Type>*>层次序游标类的operator操template<classType>LevelOrderLevelOrder(constBinaryTree<Type>&BT)TreeIterator<Type>(BT{qu.EnQueue(BT.GetRoot());template<classType>viodLevelOrder<Type>::First(){//初始化：只有根结点在qu.MakeEmpty(if(BT.GetRoot())qu.EnQueue(BT.GetRoot());operator++();}template<classType>LevelOrder<Type>::operator++(){if(qu.IsEmpty()){if(current==NULL)cout已经遍历完成endl;exit}current=NULL;}current=qu.DeQueue();//当前结点是退队结点if(current→GetLeft()!=NULL) qu.EnQueue(current→GetLeft());//进队列if(current→GetRight()!=NULL) qu.EnQueuecurrent→GetRight//进队}(ThreadedBinary线索增加Pred指针和Succ指针的二叉线索化二叉树及其二叉链表表LeftThread=0, LeftThread=1, RightThread=0, RightThread=1, 中序线索化二叉树的类定template<class中序线索化二叉树的类定friendclassThreadInorderIterator;intleftThread,rightThread;ThreadNode<Type>*leftChild,*rightChild;Typedata;ThreadNode(constTypeitem):data(item),leftChild(NULL),rightChild(NULL),leftThread(0),rightThread(0){}template<classType>classThreadTree{friendclassThreadInorderIterator;ThreadNode<Type>template<classType>classThreadInorderIterator{&Tree):T(Tree){current=T.root;}ThreadNode<Type>*First(ThreadNode<Type>*Last(ThreadNode<Type>*Next(ThreadNode<Type>*Prior();ThreadTree<Type>ThreadNode<Type> 带表头结点的中序穿线链在中序下的后A

if(currentrightChild后继为else无后 else//currentrightThreadif(currentrightChild

的中序下的第一个结else出错情 LAGCHGCHL

if(currentleftChild前驱为else无前if(currentleftChild!=T.root) else出错情 在中序线索化二叉树中的部分成员函数的实template<classType>*ThreadInorderIterator<Type>::First(){while(current→leftThread==0)current=current→leftChild;returncurrent;}template<classType>*ThreadInorderIterator<Type>::Next(){ThreadNode<Type>*p=current→rightChild;if(current→rightThread==0)while(p→leftThread==0)p=current=if(current==T.root)returnNULL;elsereturncurrent;}template<classType>ThreadNode<Type>*p;for(p=First();p!=NULL;p=Next()cout<<p→data<<}通过中序遍历建立中序线索化二叉InThread(ThreadNode<Type>*current,ThreadNode<Type>*pre){if(current!=NULL){InThread(current→leftChild,pre);if(current→leftChild==NULL){current→leftChild=pre;current→leftThread=1;}if(pre→rightChild==NULL){pre→rightChild=current;pre→rightThread=1;}pre=InThread(current→rightChild,pre}}template<classType>ThreadNode<Type>root=newThreadNode<Type>;root→leftThread=1;root→rightThread=0;if(this==NULL){root→leftChild=root;root→rightChild=root;}elsecurrent=root→leftChild=pre=InThread(current,prepre→rightChild= }}前序线索化二前序序ABDC

DBEC在后序线索化二叉树寻找当前结点的后堆堆Heaptemplate<classType>classMinPQ{VirtualvoidInsert(constType&)=0;VirtualType*RemoveMin(Type&)=0;}最小优先级队列类堆的定完全二叉树的数组表Ki Ki

完全二叉树的数组表Ki Ki最小堆的类定template<classType>classMinHeap:publicMinPQ<Type>{MinHeap(intmaxSize)MinHeap(Typearr[],intn~MinHeap(){delete[]heap;}constMinHeap<Type>&operator=(constMinHeap&R);intInsert(constType&x);intRemoveMin(Type&xintIsEmpty()const{returnCurrentSize==0;intIsFull(){returnCurrentSize==MaxHeapSize;}voidMakeEmpty(){CurrentSize=0;}enum{DefaultSize=10};Type*heap;intCurrentSize;intMaxHeapSize;voidFilterDown(inti,intm);voidFilterUp(inti);}堆的建template<classType>堆的建MinHeap(intmaxSize)//根据给定大小maxSize,MaxHeapSize=DefaultSize<maxSizemaxSize:DefaultSize; heap=newType[MaxHeapSize];//创建堆空间CurrentSize=0; }template<classType>MinHeapMinHeap(Typearr[],intn)//根据给定数组中的数据和大小,建立堆对MaxHeapSize=DefaultSize<n?n:DefaultSize;heap=newType[MaxHeapSize];heap //数组传CurrentSize //当前堆intcurrentPos=(CurrentSize-2)/2; while(currentPos>=0){//从下到上逐步扩大,形成FilterDown(currentPos,CurrentSize//从currentPos开始,到CurrentSize为止,调currentPos--}}将将一组用数组存放的任意数据自下向上逐步调整为最小最小堆的向下调整算template<classType>voidMinHeap<Type>::FilterDown(constintstart,constintEndOfHeap){inti j ji的Typetemp=while(j<=EndOfHeap)if(j<EndOfHeap&&heap[j].keyheap[j+1].key) // 中选小if(temp.key<=heap[j].key)else{heap[i]=heap[j];i= j=2*j+1;}heap[i]=}堆template<classType>intMinHeap<Type>::Insert(constType&x){//在堆 新元素ifCurrentSizeMaxHeapSize //堆{cout<<"堆已满"<<endl;return0;}heap[CurrentSize]=x; FilterUp(CurrentSize); return1;}template<classType>voidMinHeap<Type>::FilterUp(intstart){//从start开始,向上直到0,调整intjstart,ij- ij的双Typetemp=heap[j];while(j>0){if(heap[i].key<=temp.key)else{heap[j]=heap[i];j=i;i=(i-1)/2;}heap[j]=}template<classType>intMinHeapRemoveMin(Type&x)if(!CurrentSize{cout<<“堆已空"<<endl;return0;}x=heap[0]; heap[0]=heap[CurrentSize-1]; FilterDown(0,CurrentSize-1);return1;}树 表树的广义表表(结点的utype域没有画出双双亲表 -右兄弟表示第一种解决方d第二种解决方树的 -右兄弟表用 -右兄弟表示实现的树的类定template<classType>classtemplate<classType>classTreeNode{friendclassTree<Type>;TreeNode(Typevalue=0,TreeNode<Type>*fc=NULL,TreeNode<Type>*ns=NULL):data(value),firstChild(fc),nextSibling(ns){}template<classType>classTree{Tree(){root=current=NULL;voidPreOrder(ostream&out,intFind(TypeNode<Type>*p,Type voidRemovesubTree(TreeNode<Type>*p);intFindParent(TreeNode<Type>*t,*p);}用 -右兄弟表示实现的树的部分操template<classType>voidTree//建立树的根结点,并使之成为树的当前结template<classType>intTreeNodeRoot()if(root==NULL){current=NULL;return0;}else{current=root;return1;}}//在树中寻找当前结点的双亲,使之成为当前结TreeNode<Type>*p=current,if(current==NULL||current==root{current=NULL;return0;t=root; intk=FindParent(t,p);returnk;}template<classType>intTreeFirstChild()//在树中寻找当前结点的长子,使之成为当前结if(current!=NULL&&!=NULL{current=current→firstChild;return1;current=NULL;return}NextSibling()//在树中寻找当前结点的兄弟,使之成为当前结点(current!=NULL&¤t→nextSiblingNULL{current=current→nextSibling;return1;current=NULL;return}FindParent(TreeNode<Type>*t,*p){//在根t的树中寻找p的双亲,使之成为当前结while(q!=NULL&&q!=p)//循根的长子的兄弟链,递归在子树中搜if((inti=FindParent!=0)returni;q=q→nextSibling;}if(q!=NULL&&q==p{current=t;return1;elsereturn //未找到双亲,当前结}Find(Type ){if(IsEmpty())return0;returnFind(root, }template<classType>intTreeFind(TreeNode<Type>*p, )//在根为p的树中寻找值 的结点,找到//该结点成为当前结点,否则当前结点不变。函//返回成功标志：=1,搜索成功;=0,搜索intresult=if(p→data ){result=1;current=p;elseTreeNode<Type>*q=p→firstChild;while(q!=NULL&&!(result=Find( ))q=}return}森林与二叉树的对应关森林转化成二叉树的规若F为空，即n0，对应的二叉树B为空二叉树若F不空，对应二叉树B的根root(B)是F中第一棵树的根root其左子树为B(T11T12T1m)，其中T12T1m是root(T1)的子树其右子树为B(T2T3Tn)，其中，T2,T3,…,Tn是除T1外其它树构成的森林。二叉树转换为森林的规如果B为空，对应的森林F也为空如果B非空，F中第一棵树T1的根为T1的根的子树森林{T11T12,…,T1m}是由root的左子树LB转换而来，F中除了T1之外其余的树组成的森林{T2,T3,…,Tn}是由root的右子树RB转换而成的森林。深度优先遍树的二叉树表树的先根次序遍历的递归算PreOrder(){if(!IsEmpty())visit(); TreeNode<Type>*p=current;//暂存当前结点inti=FirstChild(); while(i){PreOrder();i=NextSibling();}//递归先根遍历各current //递归完恢复当前结}}树的后根次序遍历的递归算PostOrder(){if(!IsEmpty())TreeNode<Type>*p=current;//暂存当前结点inti=FirstChild(); while(i){PostOrder();i=NextSibling();}//递归后根遍历各棵子current //递归完恢复当visit 根结}}按先根次序遍历树的迭代算NorecPreOrder(){do{while(!IsEmpty()){//从根沿长子链向下visit;st.Pushcurrent)//边边进栈FirstChild();}while(IsEmpty()&&!st.IsEmpty())current=st.Pop();NextSibling( // 或无兄弟,退栈,转向下一兄whileIsEmpty //栈空,退出循current=}(4)(4)按后根次序遍历树的迭代算PostOrder1(){do{whileIsEmpty //从根沿长子链向st.Pushcurrent);FirstChild //进}while(IsEmpty()&&!st.IsEmpty()){current=st.Pop();visit();NextSibling();// 或无兄弟,退栈 ,转向兄}while(!IsEmpty()current=}广度优先遍按层次次序遍历树的算LevelOrder(){Queue<TreeNode<Type>*>Qu(DefaultSize);if(!IsEmpty()){TreeNode<Type>*p=current;Qu.EnQueue(current); while(!Qu.IsEmpty()) //队列不current=Qu.DeQueue();visit(//退出FirstChild(); //转向长子while(!IsEmpty()) {Qu.EnQueue(current);NextSibling();}}current=}先