第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 );