《数据结构习题解答》习题6解答

6-1写出用广义表表示法表示的树的类声明,并给出如下成员函数的实现: (1)operator>>()接收用广义表表示的树作为输入,建立广义表的存储表示 (2)复制构造函数用另一棵表示为广义表的树初始化一棵树; (3)operator=()测试用广义表表示的两棵树是否相等

团购合买资源类别：文库，文档格式：DOC，文档页数：13，文件大小：255KB

第 6 章树与森林 43 6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现： (1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示； (2) 复制构造函数用另一棵表示为广义表的树初始化一棵树； (3) operator == ( ) 测试用广义表表示的两棵树是否相等； (4) operator #define maxSubTreeNum 20; //最大子树(子表)个数 class GenTree; //GenTree 类的前视声明 class GenTreeNode { //广义树结点类的声明 friend class GenTree; private: int utype; //结点标志：=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 = 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; } //返回子树结点的地址 GenTreeNode * GetNsibling ( ) { return nextSibling; } //返回下一个兄弟结点的地址 void setInfo ( char item ) { data = item; } //将结点中的值修改为 item void setFchild ( GenTreeNode * ptr ) { firstChild = ptr; } //将结点中的子树指针修改为 ptr void setNsinbilg ( GenTreeNode * ptr ) { nextSibling = ptr; } }; class GenTree { //广义树类定义 private: GenTreeNode *first; //根指针 char retValue; //建树时的停止输入标志 GenTreeNode *Copy ( GenTreeNode * ptr ); //复制一个 ptr 指示的子树 void Traverse ( GenListNode * ptr ); //对 ptr 为根的子树遍历并输出

第 6 章树与森林 44 void Remove ( GenTreeNode *ptr ); //将以 ptr 为根的广义树结构释放 friend int Equal ( GenTreeNode *s, GenTreeNode *t ); //比较以 s 和 t 为根的树是否相等 public: GenTree ( ); //构造函数 GenTree ( GenTree& t ); //复制构造函数 ~GenTree ( ); //析构函数 friend int operator == ( GenTree& t1, GenTree& t2 ); //判两棵树 t1 与 t2 是否相等 friend istream& operator >> ( istream& in, GenTree& t ); //输入 friend ostream& operator > ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示 istream& operator >> ( istream& in, GenTree& t ) { //友元函数, 从输入流对象 in 接受用广义表表示的树，建立广义表的存储表示 t。 t.ConstructTree ( in, retValue ); return in; } void GenTree :: ConstructTree ( istream& in, char& value ) { //从输入流对象 in 接受用广义表表示的非空树，建立广义表的存储表示 t。 Stack st (maxSubTreeNum); //用于建表时记忆回退地址 GenTreeNode * p, q, r; Type ch; cin >> value; //广义树停止输入标志数据 cin >> ch; first = q = new GenTreeNode ( 0, ch ); //建立整个树的根结点 cin >> ch; if ( ch == ‘(’ ) st.Push ( q ); //接着应是‘(’, 进栈 cin >> ch; while ( ch != value ) { //逐个结点加入 switch ( ch ) { case ‘(’ : p = new GenTreeNode ( q ); //建立子树, p->firstChild = q r = 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( ); //栈不空, 取上层链子树结点 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 章树与森林 48 void SetRight ( BinTreeNode *R ){ RightChild =R; } int IsEmpty ( ) { return root == NULL ? 1 : 0; } BinTreeNode *Parent ( BinTreeNode *current ) { return root == NULL|| root == current ? NULL : Parent ( root, current ); } BinTreeNode * LeftChild ( BinTreeNode *current ) { return current != NULL ? current->leftChild : NULL; } BinTreeNode * RighttChild ( BinTreeNode *current ) { return current != NULL? current->rightChild : NULL; } int Insert ( const Type& item ); BinTreeNode * Find ( const Type& item ); BinTreeNode * GetRoot ( ) const { return root; } friend istream& operator >> ( istream& in, BinaryTree& Tree ); //输入二叉树 friend ostream& operator & Tree ); //输出二叉树 } 6-4 在结点个数为 n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【解答】结点个数为 n 时，高度最小的树的高度为 1，有 2 层；它有 n-1 个叶结点，1 个分支结点；高度最大的树的高度为 n-1，有 n 层；它有 1 个叶结点，n-1 个分支结点。 6-5 如果一棵树有 n1 个度为 1 的结点, 有 n2 个度为 2 的结点, … , nm个度为 m 的结点, 试问有多少个度为 0 的结点? 试推导之。【解答】总结点数 n = n0 + n1 + n2 + … + nm 总分支数 e = n-1 = n0 + n1 + n2 + … + nm-1 = m*nm + (m-1)*nm-1 + … + 2*n2 + n1 则有 ( 1) 1 2 0  +      =  − = m i ni n i 6-6 试分别找出满足以下条件的所有二叉树: (1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。【解答】 (1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 6-7 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点的个数。 (2) 以二叉树为参数，交换每个结点的左子女和右子女。【解答】 (1) 统计二叉树中叶结点个数 int BinaryTree :: leaf ( BinTreeNode * ptr ) {

点击进入文档下载页（DOC格式）

共13页，试读已结束，阅读完整版请下载

点击下载（DOC格式）

浏览记录

《数据结构习题解答》习题6解答