第6章树与森林 6-1写出用广义表表示法表示的树的类声明,并给出如下成员函数的实现 (1) operator>()接收用广义表表示的树作为输入,建立广义表的存储表示; (2)复制构造函数用另一棵表示为广义表的树初始化一棵树 (3) operator=()测试用广义表表示的两棵树是否相等 (4) operator #define max Sub TreeNum 20 最大子树(子表)个数 class EntRee: ∥ Gen tree类的前视声明 class GenTreeNode i ∥广义树结点类的声明 friend class EntRee: private int uty pe, ∥结点标志:=0,数据;=1,子女 Gen TreeNode nextsibl /dtpe=0,指向第一个子女 /dtpe=0,根结点数据 har Childdata: /type=1,子女结点数据 Gen TreeNode *firstchild type=2,指向第一个子女的指针 Gen TreeNode( int tp, char item ) utype(tp), nextSibling (NULL) d if tp==0)RootData=item; else ChildData=item;) ∥构造函数:构造广义表表示的树的数据结点 GenTreeNode( GenTreeNode *son= NULL ) utype(2), nextSibling(NULL), firstChild( son) ∥构造函数:构造广义表表示的树的子树结点 t nodetype ()( return utype; ∥返回结点的数据类型 ∥返回数据结点的值 Gen TreeNode *Get Child (return firstChild; j 历返回子树结点的地址 Gen TreeNode 'GetNsibling(( return nextsibling 返回下一个兄弟结点的地址 void setInfo( char item )i data=item; I /将结点中的值修改为item void set Child( Gen TreeNode *ptr)( firstChild=ptr; 1 将结点中的子树指针修改为pr void setNsinbilg( Gen TreeNode*ptr )inextsibling= ptr; 3 class EntRee i ∥广义树类定义 private Gen TreeNode "first; ∥根指针 char ret value; 建树时的停止输入标志 Gen TreeNode* Copy( Gen TreeNode* ptr ) ∥复制一个p指示的子树 void Traverse( GenListNode"ptr ) /对p为根的子树遍历并输出
第 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章树与森林 void Remove( Gen"ptr ) ∥将以p为根的广义树结构释放 friend int Equal( Gen TreeNode*s, GenTreeNodet ) ∥比较以s和t为根的树是否相等 en Tree ( 构造函数 GenTree( GenTree& t ) ∥复制构造函数 EntRee(; ∥析构函数 Gen Tree& tl, Gen Tree&t2); ∥判两棵树tl与口是否相等 friend istream& operator >> istream& in, Gen Tree& t ); friend ostream& operator ()接收用广义表表示的树作为输入,建立广义表的存储表示 istream& operator >> istream& in, Gen Tree& t)( ∥友元函数,从输入流对象i接受用广义表表示的树,建立广义表的存储表示t。 t. ConstructTree( in, ret Value ) return in: void Gen Tree: ConstructTree( istream& in, char& value )i ∥从输入流对象n接受用广义表表示的非空树,建立广义表的存储表示te Stack st(maxSubTreeNum): ∥用于建表时记忆回退地址 Gen TreeNode" p, a ,r cin > value: ∥广义树停止输入标志数据 cin > ch; first=q=new Gen TreeNode(0, ch ) ∥建立整个树的根结点 if( ch=="()st Push (q); ∥接着应是(,进栈 while( ch I= value )i ∥逐个结点加入 switch( ch) caseC: p=new Gen TreeNode (q); ∥建立子树,p-> firstchild=q r=st GetTop(: st Pop(; ∥从栈中退出前一结点 r->nextSibling=p; 插在前一结点r之后 ush(p ) st Push( q): ∥子树结点及子树根结点进栈 case): q->nextSibling= NULL; st pop(; ∥子树建成,封闭链,退到上层 if( st Is Empty (==0)q=st GetTop(); ∥栈不空,取上层链子树结点 else return 0: ∥栈空,无上层链,算法结東 break break: default p=q; ir( isupper(ch)q= new Gen TreeNode(0,ch);∥大写字母,建根结点 de( 1, ch )i ∥非大写字母,建数据结点 p->nextsibling=q: ∥链接
第 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章树与森林 (2)复制构造函数用另一棵表示为广义表的树初始化一棵树; GenTree: GenTree( const GenTree& t)i ∥共有函数 first=Copy( tfirst ) GenTreeNode* Gen Tree Copy( Gen TreeNode"ptr)t ∥私有函数,复制一个pt指示的用广义表表示的子树 GenTreeNode *q=NULL; f( ptr I=NULL)( q= new Gen TreeNode( ptr->utype, NULL ) switch( ptr->utype )i ∥根据结点类型 utype传送值域 case0: q->RootData= ptr->RootData; break ∥传送根结点数据 case 1: q->ChildData= ptr->ChildData; break; ∥传送子女结点数据 case 2: q->firstChild =Copy( ptr->first Child ) break ∥递归传送子树信息 q->nextsibling= Copy( ptr->nextS ibling ) ∥复制同一层下一结点为头的表 return q; (3) operator=()测试用广义表表示的两棵树是否相等 int operator ==( Gen Tree& tl, Gen Tree& 22) ∥友元函数:判两棵树t与口是否相等,若两表完全相等,函数返回1,否则返回0。 return Equal( tl. first, t2. first ) int Equal( GenTreeNode * tl, Gen TreeNode *2)t ∥是 Gen TreeNode的友元函数 if( tI ==NULL &&t2=NULL)return 1: ∥表t与表t2都是空树,相等 f(t=NUL&&t2l=NULL&&tl->upe=口2->utpe){W两子树都非空且结点类型相同 switch( tl->utype ∥比较对应数据 case0: x=(tl-> RootData==t2-> RootData)?1: 0; ∥根数据结点 case 1: x=(tI->Child Data ChildData)? 1: 0; ∥女数据结点 Ae2: x= Equal( tI->firstChild, t2->first Child ) ∥递归比较其子树 if(x)return Equal(tI-nextsibling, t2->nextSibling
第 6 章 树与森林 45 cin >> ch; } } (2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树； GenTree :: GenTree ( const GenTree& t ) { //共有函数 first = Copy ( t.first ); } GenTreeNode* 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; //传送根结点数据 case 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 == ( GenTree& t1, GenTree& t2 ) { //友元函数 : 判两棵树 t1 与 t2 是否相等, 若两表完全相等, 函数返回 1, 否则返回 0。 return Equal ( t1.first, t2.first ); } int Equal ( GenTreeNode *t1, GenTreeNode *t2 ) { //是 GenTreeNode 的友元函数 int x; if ( t1 == NULL && t2 == NULL ) return 1; //表 t1 与表 t2 都是空树, 相等 if ( t1 != NULL && t2 != NULL && t1->utype == t2->utype ) { //两子树都非空且结点类型相同 switch ( t1->utype ) { //比较对应数据 case 0 : x = ( t1->RootData == t2->RootData ) ? 1 : 0; //根数据结点 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章树与森林 ∥相等,递归比较同一层的下一个结点;不等,不再递归比较 (4) operatorutype ==0)out RootData ChildDat ∥子树结点 traverse( ptr->firstChild ) m向子树方向搜索 if( ptr->nextSibling I= NULL )out nextSibling ) 向同一层下一兄弟搜索 (5)析构函数清除一棵用广义表表示的树 GenTree: :-GenTree(i m用广义表表示的树的析构函数,假定frst≠NULL Gen Tree Node p: if( p-> 2)Remove( p->firstChild ) 在子树中删除 ptr->nextsibling=p->nextsibling: delete(p); 释放结点p
第 6 章 树与森林 46 //相等, 递归比较同一层的下一个结点; 不等, 不再递归比较 } return 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; delete ( p ); //释放结点 p } }
第6章树与森林 6-2列出右图所示二叉树的叶结点、分支结点和每个结点的层次 【解答】 二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为0:结点②、③的层次为1:结点④、⑤、⑥的层次 为2:结点⑦、⑧的层次为3:结点⑨的层次为 6-3使用(1)顺序表示和(2)二叉链表表示法,分别画出右图所示二叉树的存储表示。 ②③④ ⑥ a 101112131415 Al△ E△ 顺序表示 回人 叉链表表示 6-3用嵌套类写出用链表表示的二叉树的类声明 【解答】 #include template class Binary Tree i private plate class BinTreeNode i public: BinTreeNode *leftchild, *right Child; Type RevAlue; BinTreeNode*root; BinTreeNode"Parent( BinTreeNode * start, BinTreeNode"current )i int Insert( BinTreeNode current, const Type& item ) int Find( BinTreeNode *current, const Type& item )const void destroy( BinTreeNode*current )i void Traverse( Bin TreeNode *current, ostream& out)const Binary Tree(: root(NULL)0 Binary Tree( Type value ) RefValue( value ) root( NULL Binary Tree()i destroy(root);j BinTreeNode(): leftChild( NULL ) right Child(NULL)J BinTreeNode( Type item ) data( item ) leftChild NULL ) right Child NULL)0 BinTreeNode* GetLeft (const( return leftChild; j Right const( return right Child; 3 oid SetData( const Type& item )i data=item; 3 id SetLeft( BinTreeNode"L)leftChild =L;)
第 6 章 树与森林 47 6-2 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】 二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为 0；结点②、③的层次为 1；结点④、⑤、⑥的层次 为 2；结点⑦、⑧的层次为 3；结点⑨的层次为 4。 6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。 6-3 用嵌套类写出用链表表示的二叉树的类声明。 【解答】 #include template class BinaryTree { private: template class BinTreeNode { public: BinTreeNode *leftChild, *rightChild; Type data; } Type RefValue; BinTreeNode * root; BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode *current, const Type& item ); int Find ( BinTreeNode *current, const Type& item ) const; void destroy ( BinTreeNode *current ); void Traverse ( BinTreeNode *current, ostream& out ) const; public: 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& GetData ( ) const { return data; } BinTreeNode* GetLeft ( ) const { return leftChild; } BinTreeNode* GetRight ( ) const{ return rightChild; } void SetData ( const Type& item ){ data = item; } void SetLeft ( BinTreeNode *L ) { leftChild = L; } ① ② ③ ④ ⑤ ⑥ ⑦ ⑨ ⑧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 顺序表示 二叉链表表示
第6章树与森林 void SetRight( BinTreeNode*R RightChild =R; 1 int Is Empty (return root==NULL ?1: 0;1 BinTreeNode "Parent( BinTreeNode 'current i return root=NULL I root=current? NULL Parent( root, current );) BinTreeNode*LeftChild( BinTreeNode*current n current I= NULL current-> leftChild: NULL; 1 i return current != NULL current->right Child NULL t Insert( const Type& item ) BinTreeNode. GetRoot ()const( return root; 3 friend istream& operator>>( istream&in, Binary Treee&Tre;输入二叉树 friend ostream& operator & Tree ) 出二叉树 6-4在结点个数为n(n>1)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多少个分支结 点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点? 【解答】结点个数为n时,高度最小的树的高度为1,有2层;它有n-1个叶结点,1个分支结点:高度 最大的树的高度为n-1,有n层;它有1个叶结点,n-1个分支结点 6-5如果一棵树有n个度为1的结点,有n2个度为2的结点,…,mm个度为m的结点,试问有多少个度 为0的结点?试推导之 【解答】总结点数n=no+n+n+…+n 总分支数e=n-1=no+n1+n+…+nm-1 m*nm+(m-1)*nm1+…+2*n2+nn 则有n2=(∑(-1m|+1 6-6试分别找出满足以下条件的所有二叉树 (1)二叉树的前序序列与中序序列相同 (2)二叉树的中序序列与后序序列相同; (3)二叉树的前序序列与后序序列相同 【解答】 (1)二叉树的前序序列与中序序列相同:空树或缺左子树的单支树 (2)二叉树的中序序列与后序序列相同:空树或缺右子树的单支树 (3)二叉树的前序序列与后序序列相同:空树或只有根结点的二叉树 6-7若用二叉链表作为二叉树的存储表示,试针对以下问题编写递归算法: (1)统计二叉树中叶结点的个数。 (2)以二叉树为参数,交换每个结点的左子女和右子女 【解答】 (1)统计二叉树中叶结点个数 int Binary Tree: leaf( BinTreeNode*ptr)i
第 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 ) {
第6章树与森林 if( ptr ==NULL )return 0; else if( ptr->left Child == NULL & ptr->rightChild ==NULL )return else return leaf ptr->leftChild ) leaf( ptr->rightChild ) (2)交换每个结点的左子女和右子女 oid Binary Tree: exchange( BinTreeNode*ptr )i if(ptr->leftChild= NULL II ptr->rightChild I=NULL)( p= ptr->left child ptr->leftChild=ptr->righto ptr->rightChild =temp; exchange( ptr->leftChild ) 6-8一棵高度为h的满k叉树有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有k棵 非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进行编号,试问 (1)各层的结点个数是多少? (2)编号为i的结点的父结点(若存在)的编号是多少? (3)编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4)编号为i的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少? (5)若结点个数为n,则高度h是n的什么函数关系? 【解答】 (1) i+k-2 k (3)(i-1)*k+m+1 (4)(-1)%k≠0或;i+k-2|+k时有右兄弟,右兄弟为i+1 (5)h=log(n*(k-1)+1)-1(n=0时h=-1) 6-9试用判定树的方法给出在中序线索化二叉树上 【解答】 (1)搜索指定结点的在中序下的后继 设指针q指示中序线索化二叉树中的指定结点,指针p指示其后继结点。 >rightThread=1? q->righr Child== NULL? q的后继为q的右子树中 中序下的第一个结点 q无后继 a的后继为a-> 找q的右子树中在中序下的第一个结点的程序为: p=q->rightChild
第 6 章 树与森林 49 if ( ptr == NULL ) return 0; else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1; else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild ); } (2) 交换每个结点的左子女和右子女 void BinaryTree :: exchange ( BinTreeNode * ptr ) { BinTreeNode * temp; if ( ptr->leftChild != NULL || ptr->rightChild != NULL ) { temp = ptr->leftChild; ptr->leftChild = ptr->rightChild; ptr->rightChild = temp; exchange ( ptr->leftChild ); exchange ( ptr->rightChild ); } } 6-8 一棵高度为 h 的满 k 叉树有如下性质: 第 h 层上的结点都是叶结点, 其余各层上每个结点都有 k 棵 非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从 1 开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为 i 的结点的父结点(若存在)的编号是多少? (3) 编号为 i 的结点的第 m 个孩子结点(若存在)的编号是多少? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度 h 是 n 的什么函数关系? 【解答】 (1) k i ( i = 0, 1, ……, h ) (2) + − k i k 2 (3) ( i-1)*k + m + 1 (4) ( i-1 ) % k 0 或 * k k i k 2 i + − 时有右兄弟，右兄弟为 i + 1。 (5) h = logk (n*(k-1)+1)-1 (n = 0 时 h = -1 ) 6-9 试用判定树的方法给出在中序线索化二叉树上： 【解答】 (1) 搜索指定结点的在中序下的后继。 设指针 q 指示中序线索化二叉树中的指定结点，指针 p 指示其后继结点。 找 q 的右子树中在中序下的第一个结点的程序为： p = q->rightChild; q->rightThread == 1? = ≠ q->rightChild == NULL ? = q 无后继 ≠ q 的后继为 q->rightChild q 的后继为 q 的右子树中 中序下的第一个结点
第6章树与森林 while(p-> leftThread=1)p=p-> leftchild;∥p即为q的后继 (2)搜索指定结点的在前序下的后继 g->leftThread ==0? 的后继为q-> lefichild q的后继为q-> righIchild while(p->rightThread==l&& o->righ/Child I=NULL)P=p->righrChild; f(p-> righIChild==NUL)q无后继: (3)搜索指定结点的在后序下的后继。 (p=parent(q ))=NULL? q无后继 >rightChild q的后继为p q的后继为p的右子树中后序下的第一个结点 可用一段遍历程序来实现寻找p的右子树中后序下的第一个结点:即该子树第一个找到的叶结点。 找到后立即返回它的地址 6-10已知一棵完全二叉树存放于一个一维数组Tn中,Tm中存放的是各结点的值。试设计一个算法, 从T0开始顺序读出各结点的值,建立该二叉树的二叉链表表示。 【解答】 template ∥建立二叉树 istream& operator >> istream& in, Binary Tree& t) cout >A[: t. ConstructTree( T, n, 0, ptr ∥以数组建立一棵二叉树 return in: void Binary Tree: ConstructTree( Type TI int n, int 1, BinTreeNode*& ptr )i ∥有函数:将用Tn]顺序存储的完全二叉树,以i为根的子树转换成为用二叉链表表示的 ∥以p为根的完全二叉树。利用引用型参数pt将形参的值带回实参。 >=n)ptr =NULL; ptr=new BinTreeNode(To); ∥建立根结点 ConstructTree(T, n, 2*i+1, ptr->leftChild i ConstructTree(T, n, 2*i+2, ptr->rightChild )
第 6 章 树与森林 50 while ( p->leftThread == 1 ) p = p->leftChild; // p 即为 q 的后继 (2) 搜索指定结点的在前序下的后继。 (3) 搜索指定结点的在后序下的后继。 可用一段遍历程序来实现寻找 p 的右子树中后序下的第一个结点：即该子树第一个找到的叶结点。 找到后立即返回它的地址。 6-10 已知一棵完全二叉树存放于一个一维数组 T[n]中，T[n]中存放的是各结点的值。试设计一个算法， 从 T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 【解答】 template //建立二叉树 istream& operator >> ( istream& in, BinaryTree& t ) { int n; cout > n; Type *A = new Type[n+1]; for ( int i = 0; i > A[i]; t. ConstructTree( T, n, 0, ptr ); //以数组建立一棵二叉树 delete [ ] A; return in; } template void BinaryTree :: ConstructTree ( Type T[ ], int n, int i, BinTreeNode *& ptr ) { //私有函数 : 将用 T[n]顺序存储的完全二叉树, 以 i 为根的子树转换成为用二叉链表表示的 //以 ptr 为根的完全二叉树。利用引用型参数 ptr 将形参的值带回实参。 if ( i >= n ) ptr = NULL; else { ptr = new BinTreeNode ( T[i] ); //建立根结点 ConstructTree ( T, n, 2*i+1, ptr->leftChild ); ConstructTree ( T, n, 2*i+2, ptr->rightChild ); } } q->leftThread == 0 ? = q的后继为 q->leftChild ≠ q->rightThread == 0 ? = q 的后继为 q->rightChild ≠ p = q; while ( p->rightThread == 1 && p->rightChild != NULL ) p = p->rightChild; if ( p->rightChild ==NULL ) q 无后继; else 的后继为 p->rightChild ( p = parent (q ) ) == NULL ? = q 的后继为 p ≠ p->rightThread == 1 || p->rightChild == q ?= ≠ q 的后继为 p 的右子树中后序下的第一个结点 q 无后继
第6章树与森林 6-11请画出右图所示的树所对应的二叉树。 【解答】 对应二叉树 6-12在森林的二叉树表示中,用link存储指向结点第一个子女的指针,用rink存储指向结点下一个兄 弟的指针,用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示,同时按森林的先根 次序依次安放森林的所有结点,则可以在它们的结点中用只有一个二进位的标志tag代替link,用rag 代替 rlink。并设定若Itag=0,则该结点没有子女,若ltag≠0,则该结点有子女;若tag=0,则该结点 没有下一个兄弟,若rtag≠0,则该结点有下一个兄弟。试给出这种表示的结构定义,并设计一个算法 将用这种表示存储的森林转换成用link-rink表示的森林。 【解答】 对应二叉树 2345678910 data ABCdE K 森林的左子女-右兄弟 表示的静态二叉链表 2345678910 data ABCdE GH K 森林的双标记表示 00 (1)结构定义 template class LchRsibNode i ∥左子女-右兄弟链表结点类的定义 Type data ∥结点数据 int llink, rlink; ∥结点的左子女、右兄弟指针 public: LchRsibNode ( llink(NUL), rlink(NULL) LchRsibNode( Type x ) llink(NULL), rlink(NULL), data(x)U template class Doubly TagNode{W双标记表结点类的定义
第 6 章 树与森林 51 6-11 请画出右图所示的树所对应的二叉树。 【解答】 6-12 在森林的二叉树表示中，用 llink 存储指向结点第一个子女的指针，用 rlink 存储指向结点下一个兄 弟的指针，用 data 存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根 次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志 ltag 代替 llink，用 rtag 代替 rlink。并设定若 ltag = 0，则该结点没有子女，若 ltag 0，则该结点有子女；若 rtag = 0，则该结点 没有下一个兄弟，若 rtag 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法， 将用这种表示存储的森林转换成用 llink - rlink 表示的森林。 【解答】 (1) 结构定义 template class LchRsibNode { //左子女-右兄弟链表结点类的定义 protected: Type data; //结点数据 int llink, rlink; //结点的左子女、右兄弟指针 public: LchRsibNode ( ) : llink(NULL), rlink(NULL) { } LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) { } } template class DoublyTagNode { //双标记表结点类的定义 1 对应二叉树 1 2 2 3 3 4 4 5 5 6 7 6 8 8 7 A B C D E F G H K I J A B C D E F G H I K J 对应二叉树 llink data rlink 0 1 2 3 4 5 6 7 8 9 10 1 -1 -1 4 -1 6 -1 8 9 -1 -1 A B C D E F G H I K J 5 2 3 -1 -1 7 -1 -1 10 -1 -1 森林的左子女-右兄弟 表示的静态二叉链表 ltag data rtag 0 1 2 3 4 5 6 7 8 9 10 1 0 0 1 0 1 0 1 1 0 0 A B C D E F G H I K J 1 1 1 0 0 1 0 0 1 0 0 森林的双标记表示
第6章树与森林 protected Type data 吉点数据 int ltag, rtag 点的左子女、右兄弟标记 Doubly Tag Node () Itag(0), rtag(0)0 Doubly TagNode( Type x ) Itag(O), rtag(0), data(x) template class staticlinkList 静态链表类定义 public LchRsibNode, public Doubly Tag Node *V; ∥储左子女右兄弟链表的向量 Doubly Tag Node *U: ∥储双标记表的向量 int MaxSize, Current 向量中最大元素个数和当前元素个数 dstaticlinkList int Maxsz ) MaxSize( Maxsz ) CurrentSize(0)i V= new LchRsibNode [Maxsz U=new Doubly Tag Node [Maxsz]: (2)森林的双标记先根次序表示向左子女右兄弟链表先根次序表示的转换 Stack st: int k; switch(UoItag )i case0: switch(UO rtag)i case0: VO. Ilink =Vo rlink=-1; if( st IsEmpty (=0) ik=st GetTop(: st Pop (: V[k]. rlink=1+1; 1 case 1: VO.link=-li Vo rlink=i+ 1: break; case 1: switch(U[rtag)i illink=i+1; VO rlink =-1: break case 1: VO.ink=1+I; st Push(1); 6-13二叉树的双序遍历( Double- order traversal)是指:对于二叉树的每一个结点来说,先访问这个结点
第 6 章 树与森林 52 protected: Type data; //结点数据 int ltag, rtag; //结点的左子女、右兄弟标记 public: DoublyTagNode ( ) : ltag(0), rtag(0) { } DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) { } } template class staticlinkList //静态链表类定义 : public LchRsibNode, public DoublyTagNode { private: LchRsibNode *V; //存储左子女-右兄弟链表的向量 DoublyTagNode *U; //存储双标记表的向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 public: dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) { V = new LchRsibNode [Maxsz]; U = new DoublyTagNode [Maxsz]; } } (2) 森林的双标记先根次序表示向左子女-右兄弟链表先根次序表示的转换 void staticlinkList :: DtagF-LchRsibF ( ) { Stack st; int k; for ( int i = 0; i < CurrentSize; i++ ) { switch ( U[i].ltag ) { case 0 : switch ( U[i].rtag ) { case 0 : V[i].llink = V[i].rlink = -1; if ( st.IsEmpty ( ) == 0 ) { k = st.GetTop ( ); st.Pop ( ); V[k].rlink = i + 1; } break; case 1 : V[i].llink = -1; V[i].rlink = i + 1; break; } break; case 1 : switch ( U[i].rtag ) { case 0 : V[i].llink = i + 1; V[i].rlink = -1; break; case 1 : V[i].llink = i + 1; st.Push ( i ); } } } } 6-13 二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点
