数据结构第6章树与森林

108第6章树与森林一、复习要点本章主要介绍了树与森林、二叉树的定义、性质、操作和相关算法的实现。特别是二叉树的遍历算法，它们与许多以此为基础的递归算法都必须认真学习。因为树的先根遍历次序与对应二叉树表示的前序遍历次序一致，树的后根遍历次序与对应二叉树的中序遍历次序一致，因此可以据此得出树的遍历算法。线索化二叉树是直接利用二叉链表的空链指针记入前驱和后继线索，从而简化二叉树的遍历。堆是一种二叉树的应用，可以用它作为优先级队列的实现。它的存储表示是完全二叉树的顺序存储方式，它的定义不要求堆中的数据有序，但要求双亲结点与子女结点必须满足某种关系。本章最后讨论霍夫曼树。这种树是扩充二叉树，要求在外结点上带有权值，在构造霍夫曼树时必须注意一个新结点的左子女上所带的权值小于右子女上所带的权值，这不是霍夫曼树必须这样，而是实现算法造成这种结果。此外，作为霍夫曼树的应用，引入霍夫曼编码。通常让霍夫曼树的左分支代表编码“0”，右分支代表编码“1”，得到霍夫曼编码。这是一种不等长编码，可以有效地实现数据压缩。本章复习的要点是：1、基本知识点要求理解树和森林的定义，树的抽象数据类型，二叉树的定义，二叉树的性质，二叉树的抽象数据类型，二叉树的数组表示和链表存储表示。要求掌握二叉树的遍历，包括中序遍历、前序遍历、后序遍历方法，要求理解二叉树的计数方法及从二叉树遍历结果得到二叉树的方法。对于线索化二叉树，要求理解什么是线索，中序线索化二叉树的结构特性及寻找某结点的前驱和后继的方法。此外，需要理解堆的定义及其实现的方法，本章只考虑用完全二叉树的顺序存储来实现。还需要理解堆的建立，插入与删除过程。要求掌握树/森林与二叉树的转换，树的遍历方法。最后要求掌握霍夫曼树的实现方法及霍夫曼编码的概念。2、算法设计建立二叉树的递归算法。前序、中序、后序遍历二叉树的递归算法。使用栈的前序、中序、后序遍历的非递归算法。统计二叉树结点个数，二叉树叶结点个数，二叉树高度的递归算法。自左向右链接二叉树叶结点的递归算法。判断两棵二叉树相等和交换二叉树左、右子女指针的递归算法。通过二叉树的遍历建立前序线索化二叉树和中序线索化二叉树的算法。中序线索化二叉树上的中序遍历算法。前序线索化二叉树上的前序遍历算法。后序线索化二叉树上的后序遍历算法。利用堆实现优先级队列的操作。堆的自上向下和自下向上的调整算法。堆的插入与删除算法。树的先根、后根、层次遍历算法（基于树的二叉树表示）。二、难点与重点1、树：树的定义、树的基本运算树的分层定义是递归的109树中结点个数与高度的关系2、二叉树：二叉树定义、二叉树的基本运算二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置二叉树的前序·中序·后序遍历的递归算法和使用栈的非递归算法二叉树的层次遍历算法中序线索化二叉树、前驱与后继的查找方法、建立中序线索化二叉树的算法3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算霍夫曼树是带权路径长度最小的扩充二叉树构造霍夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树在构造过程中，新二叉树按根的权值加入到森林的最后4、树与森林树的广义表表示、树的双亲表示、树的左子女-右兄弟表示树、森林与二叉树的对应关系树的先根·后根·层次遍历算法5、堆：堆的定义、堆的插入与删除算法形成堆时用到的向下调整算法形成堆时的调整过程及比较次数的上界估计堆插入时用到的向上调整算法三、教材中习题的解析6-1写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现：(1)operator()接收用广义表表示的树作为输入，建立广义表的存储表示；(2)复制构造函数用另一棵表示为广义表的树初始化一棵树；(3)operator==()测试用广义表表示的两棵树是否相等；(4)operator()用广义表的形式输出一棵树；(5)析构函数清除一棵用广义表表示的树。【解答】#includeiostream.h#definemaxSubTreeNum20;//最大子树(子表)个数classGenTree;//GenTree类的前视声明classGenTreeNode{//广义树结点类的声明friendclassGenTree;private:intutype;//结点标志：=0,数据;=1,子女GenTreeNode*nextSibling;//utype=0,指向第一个子女;//utype=1或2,指向同一层下一兄弟union{//联合charRootData;//utype=0,根结点数据charChilddata;//utype=1,子女结点数据GenTreeNode*firstChild;//utype=2,指向第一个子女的指针}110public:GenTreeNode(inttp,charitem):utype(tp),nextSibling(NULL){if(tp==0)RootData=item;elseChildData=item;}//构造函数：构造广义表表示的树的数据结点GenTreeNode(GenTreeNode*son=NULL):utype(2),nextSibling(NULL),firstChild(son){}//构造函数：构造广义表表示的树的子树结点intnodetype(){returnutype;}//返回结点的数据类型charGetData(){returndata;}//返回数据结点的值GenTreeNode*GetFchild(){returnfirstChild;}//返回子树结点的地址GenTreeNode*GetNsibling(){returnnextSibling;}//返回下一个兄弟结点的地址voidsetInfo(charitem){data=item;}//将结点中的值修改为itemvoidsetFchild(GenTreeNode*ptr){firstChild=ptr;}//将结点中的子树指针修改为ptrvoidsetNsinbilg(GenTreeNode*ptr){nextSibling=ptr;}};classGenTree{//广义树类定义private:GenTreeNode*first;//根指针charretValue;//建树时的停止输入标志GenTreeNode*Copy(GenTreeNode*ptr);//复制一个ptr指示的子树voidTraverse(GenListNode*ptr);//对ptr为根的子树遍历并输出voidRemove(GenTreeNode*ptr);//将以ptr为根的广义树结构释放friendintEqual(GenTreeNode*s,GenTreeNode*t);//比较以s和t为根的树是否相等public:GenTree();//构造函数GenTree(GenTree&t);//复制构造函数~GenTree();//析构函数friendintoperator==(GenTree&t1,GenTree&t2);//判两棵树t1与t2是否相等friendistream&operator(istream&in,GenTree&t);//输入friendostream&operator(ostream&out,GenTree&t);//输出}(1)operator()接收用广义表表示的树作为输入，建立广义表的存储表示istream&operator(istream&in,GenTree&t){//友元函数,从输入流对象in接受用广义表表示的树，建立广义表的存储表示t。t.ConstructTree(in,retValue);returnin;}voidGenTree::ConstructTree(istream&in,char&value){//从输入流对象in接受用广义表表示的非空树，建立广义表的存储表示t。StackGenTreeNode*st(maxSubTreeNum);//用于建表时记忆回退地址GenTreeNode*p,q,r;Typech;cinvalue;//广义树停止输入标志数据cinch;first=q=newGenTreeNode(0,ch);//建立整个树的根结点cinch;if(ch==‘(’)st.Push(q);//接着应是‘(’,进栈111cinch;while(ch!=value){//逐个结点加入switch(ch){case‘(’:p=newGenTreeNodeType(q);//建立子树,p-firstChild=qr=st.GetTop();st.Pop();//从栈中退出前一结点r-nextSibling=p;//插在前一结点r之后st.Push(p);st.Push(q);//子树结点及子树根结点进栈break;case‘)’:q-nextSibling=NULL;st.pop();//子树建成,封闭链,退到上层if(st.IsEmpty()==0)q=st.GetTop();//栈不空,取上层链子树结点elsereturn0;//栈空,无上层链,算法结束break;case‘,’:break;default:p=q;if(isupper(ch))q=newGenTreeNode(0,ch);//大写字母,建根结点elseq=newGenTreeNode(1,ch);//非大写字母,建数据结点p-nextSibling=q;//链接}cinch;}}(2)复制构造函数用另一棵表示为广义表的树初始化一棵树；GenTree::GenTree(constGenTree&t){//共有函数first=Copy(t.first);}GenTreeNode*GenTree::Copy(GenTreeNode*ptr){//私有函数，复制一个ptr指示的用广义表表示的子树GenTreeNode*q=NULL;if(ptr!=NULL){q=newGenTreeNode(ptr-utype,NULL);switch(ptr-utype){//根据结点类型utype传送值域case0:q-RootData=ptr-RootData;break;//传送根结点数据case1:q-ChildData=ptr-ChildData;break;//传送子女结点数据case2:q-firstChild=Copy(ptr-firstChild);break;//递归传送子树信息}q-nextSibling=Copy(ptr-nextSibling);//复制同一层下一结点为头的表}returnq;}(3)operator==()测试用广义表表示的两棵树是否相等intoperator==(GenTree&t1,GenTree&t2){//友元函数:判两棵树t1与t2是否相等,若两表完全相等,函数返回1,否则返回0。returnEqual(t1.first,t2.first);112}intEqual(GenTreeNode*t1,GenTreeNode*t2){//是GenTreeNode的友元函数intx;if(t1==NULL&&t2==NULL)return1;//表t1与表t2都是空树,相等if(t1!=NULL&&t2!=NULL&&t1-utype==t2-utype){//两子树都非空且结点类型相同switch(t1-utype){//比较对应数据case0:x=(t1-RootData==t2-RootData)?1:0;//根数据结点break;case1:x=(t1-ChildData==t2-ChildData)?1:0;//子女数据结点break;case2:x=Equal(t1-firstChild,t2-fi