数据结构第六章作业提示

第6章树与森林66第6章树与森林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,指向第一个子女的指针}public: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;//根指针第6章树与森林67charretValue;//建树时的停止输入标志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);//接着应是‘(’,进栈cinch;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);//大写字母,建根结点第6章树与森林68elseq=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);}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;第6章树与森林69case2:x=Equal(t1-firstChild,t2-firstChild);//递归比较其子树}if(x)returnEqual(t1-nextSibling,t2-nextSibling);//相等,递归比较同一层的下一个结点;不等,不再递归比较}return0;}(4)operator()用广义表的形式输出一棵树ostream&operator(ostream&out,GenTree&t){//友元函数,将树t输出到输出流对象out。t.traverse(out,t.first);returnout;}voidGenTree::traverse(ostream&out,GenTreeNode*ptr){//私有函数,广义树的遍历算法if(ptr!=NULL){if(ptr-utype==0)outptr-RootData‘(’;//根数据结点elseif(ptr-utype==1){//子女数据结点outptr-ChildData;if(ptr-nextSibling!=NULL)out‘,’;}else{//子树结点traverse(ptr-firstChild);//向子树方向搜索if(ptr-nextSibling!=NULL)out‘,’;}traverse(ptr-nextSibling);//向同一层下一兄弟搜索}elseout‘)’;}(5)析构函数清除一棵用广义表表示的树GenTree::~GenTree(){//用广义表表示的树的析构函数,假定first≠NULLRemove(first);}voidGenTree::Remove(GenTreeNode*ptr){GenTreeNode*p;while(ptr!=NULL){p=ptr-nextSibling;if(p-utype==2)Remove(p-firstChild);//在子树中删除第6章树与森林70ptr-nextSibling=p-nextSibling;delete(p);//释放结点p}}6-2列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。6-3使用(1)顺序表示和(2)二叉链表表示法，分别画出右图所示二叉树的存储表示。【解答】6-4用嵌套类写出用链表表示的二叉树的类声明。【解答】#includeiostream.htemplateclassTypeclassBinaryTree{private:templateclassTypeclassBinTreeNode{public:BinTreeNodeType*leftChild,*rightChild;Typedata;}TypeRefValue;BinTreeNodeType*root;BinTreeNodeType*Parent(BinTreeNodeType*start,BinTreeNodeType*current);intInsert(BinTreeNodeType*current,constType&item);intFind(BinTreeNodeType*current,constType&item)const;voiddestroy(BinTreeNodeType*current);voidTravers