第6章树与森林 建树时的停止输入标志 ∥复制一个pt指示的子树 void Traverse( GenListNode*ptr ) ∥对p为根的子树遍历并输出 /将以p为根的广义树结构释放 friend int Equal( Gen TreeNode*s, GenTreeNodet ) ∥比较以s和t为根的树是否相等 ublic 构造函数 EntRee(; ∥析构函数 ∥判两棵树t与是否相等 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 ∥友元函数,从输入流对象i接受用广义表表示的树,建立广义表的存储表示t。 t. ConstructTree( in, ret Value ) return in: void Gen Tree: ConstructTree( istream& in, char& value )i ∥从输入流对象n接受用广义表表示的非空树,建立广义表的存储表示te Stack <GenTreeNode*>st(max SubTreeNum); 用于建表时记忆回退地址 Gen TreeNode*p, q, r; Type ch cin > value ∥广义树停止输入标志数据 first=q= new GenTreeNode(0, ch ) ∥建立整个树的根结点 if( ch==()st Push(q) ∥接着应是`(,进栈 switch( ch)& case( new GenTreeNode <Type>(q); ∥建立子树,p-> firstchild=q r=st GetTop(: st Pop(; ∥从栈中退出前一结点 r->nextsibling ∥插在前一结点r之后 stPush(p ) st Push( q ) ∥子树结点及子树根结点进栈 case): q->nextSibling= NULL; st pop(; ∥子树建成,封闭链,退到上层 if( st Is Empty (==0)q=st GetTop(); ∥栈不空,取上层链子树结点 else return 0: ∥栈空,无上层链,算法结東 ir( isupper(ch)q= new Gen TreeNode(0,ch);∥大写字母,建根结点第 6 章 树与森林 67 char retValue; //建树时的停止输入标志 GenTreeNode *Copy ( GenTreeNode * ptr ); //复制一个 ptr 指示的子树 void Traverse ( GenListNode * ptr ); //对 ptr 为根的子树遍历并输出 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 ); //大写字母, 建根结点