《写出用广义表表示法表示的树的类声明》由会员分享，可在线阅读，更多相关《写出用广义表表示法表示的树的类声明（12页珍藏版）》请在金锄头文库上搜索。
1、第 6 章 树与森林436-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现： (1) operator ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示；(2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树；(3) operator = ( ) 测试用广义表表示的两棵树是否相等；(4) operator #define maxSubTreeNum 20;/最大子树(子表)个数class GenTree;/GenTree 类的前视声明class GenTreeNode /广义树结点类的声明friend class GenTree;private:int utyp
2、e;/结点标志：=0, 数据; =1, 子女GenTreeNode * nextSibling;/utype=0, 指向第一个子女;/utype=1 或 2, 指向同一层下一兄弟union /联合char RootData;/utype=0, 根结点数据char Childdata;/utype=1, 子女结点数据GenTreeNode *firstChild;/utype=2, 指向第一个子女的指针 public:GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL) if ( tp = 0 ) RootData
3、= item; else ChildData = item; /构造函数：构造广义表表示的树的数据结点GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL), firstChild ( son ) /构造函数：构造广义表表示的树的子树结点int nodetype ( ) return utype; /返回结点的数据类型char GetData ( ) return data; /返回数据结点的值GenTreeNode * GetFchild ( ) return firstChild; /返回子树结点的地址
4、GenTreeNode * GetNsibling ( ) return nextSibling; /返回下一个兄弟结点的地址void setInfo ( char item ) data = item; /将结点中的值修改为 itemvoid setFchild ( GenTreeNode * ptr ) firstChild = ptr; /将结点中的子树指针修改为 ptrvoid setNsinbilg ( GenTreeNode * ptr ) nextSibling = ptr; ;class GenTree /广义树类定义 private:GenTreeNode *first;/根
5、指针char retValue;/建树时的停止输入标志GenTreeNode *Copy ( GenTreeNode * ptr );/复制一个 ptr 指示的子树void Traverse ( GenListNode * ptr );/对 ptr 为根的子树遍历并输出第 6 章 树与森林44void Remove ( GenTreeNode *ptr );/将以 ptr 为根的广义树结构释放friend int Equal ( GenTreeNode *s, GenTreeNode *t );/比较以 s 和 t 为根的树是否相等public:GenTree ( ); /构造函数GenTre
6、e ( GenTree/复制构造函数 GenTree ( );/析构函数 friend int operator = ( GenTree/判两棵树 t1 与 t2 是否相等friend istream/输入friend ostream return in;void GenTree : ConstructTree ( istream /用于建表时记忆回退地址GenTreeNode * p, q, r; Type ch; cin value;/广义树停止输入标志数据 cin ch; first = q = new GenTreeNode ( 0, ch ); /建立整个树的根结点cin ch; i
7、f ( ch = ( ) st.Push ( q );/接着应是(, 进栈cin ch;while ( ch != value ) /逐个结点加入switch ( ch ) case ( : p = new GenTreeNode ( 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( );/
8、子树建成, 封闭链, 退到上层if ( st.IsEmpty ( ) = 0 ) q = st.GetTop( );/栈不空, 取上层链子树结点else return 0;/栈空, 无上层链, 算法结束break;case , : break;default : p = q; if ( isupper (ch) ) q = new GenTreeNode ( 0, ch );/大写字母, 建根结点else q = new GenTreeNode ( 1, ch );/非大写字母, 建数据结点p-nextSibling = q;/链接第 6 章 树与森林45cin ch; (2) 复制构造函数
9、用另一棵表示为广义表的树初始化一棵树；GenTree : GenTree ( const GenTreeGenTreeNode* GenTree : Copy ( GenTreeNode *ptr ) /私有函数，复制一个 ptr 指示的用广义表表示的子树GenTreeNode *q = NULL;if ( ptr != NULL ) q = new GenTreeNode ( ptr-utype, NULL );switch ( ptr-utype ) /根据结点类型 utype 传送值域case 0 : q-RootData = ptr-RootData; break;/传送根结点数据ca
10、se 1 : q-ChildData = ptr-ChildData; break;/传送子女结点数据case 2 : q-firstChild = Copy ( ptr-firstChild ); break;/递归传送子树信息q-nextSibling = Copy ( ptr-nextSibling );/复制同一层下一结点为头的表return q;(3) operator = ( ) 测试用广义表表示的两棵树是否相等int operator = ( GenTreeint Equal ( GenTreeNode *t1, GenTreeNode *t2 ) /是 GenTreeNode
11、的友元函数int x;if ( t1 = NULL /表 t1 与表 t2 都是空树, 相等if ( t1 != NULL /根数据结点break;case 1 : x = ( t1-ChildData = t2-ChildData ) ? 1 : 0;/子女数据结点break;case 2 : x = Equal ( t1-firstChild, t2-firstChild );/递归比较其子树if ( x ) return Equal ( t1-nextSibling, t2-nextSibling );第 6 章 树与森林46/相等, 递归比较同一层的下一个结点; 不等, 不再递归比较r
12、eturn 0;(4) operator utype = 0 ) out RootData utype = 1 ) /子女数据结点out ChildData;if ( ptr-nextSibling != NULL ) out firstChild );/向子树方向搜索if ( ptr-nextSibling != NULL ) out nextSibling );/向同一层下一兄弟搜索else out nextSibling;if ( p-utype = 2 ) Remove ( p-firstChild );/在子树中删除ptr-nextSibling = p-nextSibling; d
13、elete ( p );/释放结点 p第 6 章 树与森林476-2 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】二叉树的叶结点有、。分支结点有、。结点的层次为 0；结点、的层次为 1；结点、的层次为 2；结点、的层次为 3；结点的层次为4。6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。6-3 用嵌套类写出用链表表示的二叉树的类声明。 【解答】#include template class BinaryTree private:template class BinTreeNode public:BinTreeNode *left
14、Child, *rightChild;Type data;Type RefValue;BinTreeNode * root; BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current );int Insert ( BinTreeNode *current, const Typeint Find ( BinTreeNode *current, const Typevoid destroy ( BinTreeNode *current );void Traverse ( BinTreeNode *current, ostreamp
15、ublic:BinaryTree ( ) : root ( NULL ) BinaryTree ( Type value ) : RefValue ( value ), root ( NULL ) BinaryTree ( ) destroy (root); BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) Type BinTreeNode* GetLeft ( ) const return leftChild; BinTreeNode* GetRight ( ) const return rightChild; void SetData ( const Type 0 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18
