第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 << ostream& out, Gen Tree& t ); (1) 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 <Gen TreeNode*>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 <Type>(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 << ( ostream& out, GenTree& t ); //输出 } (1) 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 <GenTreeNode* > 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 <Type> ( 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; //链接 }