int ltag, rtag; ∥结点的左子女、右兄弟标记 lyTag Node ( ltag(o), rtag(0) Doubly Tag Node( Type x): ltag(o), rtag(o), data(x)U template <class Type> class staticlinkList 静态链表类定义 public LchRsibNode<type, public Doubly Tag Node <Type private ∥存储左子女右兄弟链表的向量 Doubly Tag Node <Type>*U; ∥储双标记表的向量 int MaxIe, Currentsice: ∥向量中最大元素个数和当前元素个数 dstaticlinkList( int Maxs= ) MaxSie( Maxsz ) CurrentSize(0)t V=new LchRsibNode <Type>[Maxs:] U=new Doubly Tag Node <Type> [Maxs:]: (2)森林的双标记先根次序表示向左子女-右兄弟链表先根次序表示的转换 void staticlinkLisK<Type>: DtagF-tchRsibFOi Stacking> >st: int k: for int i=0; i<CurrentSize; i++)i switch(U(lag)& case0: switch(U0rtag )( if (st IsEmpty(=0) ik=st GetTop(: st Pop(: Mk]. rlink=i+ 1;) case 1: vO llink =-I: i rlink =i+ I; break; case 1: switch(U[rtag )( case0: VO llink =i+ 1: v. rlink=-1; break case 1: v. llink =i+ 1; st Push(i); 6-18二叉树的双序遍历( Double -order traversa)是指:对于二叉树的每一个结点来说,先访问这个结点 再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树。试写出执行这种 双序遍历的算法。int ltag, rtag; //结点的左子女、右兄弟标记 public: DoublyTagNode ( ) : ltag(0), rtag(0) { } DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) { } } template <class Type> class staticlinkList //静态链表类定义 : public LchRsibNode<Type>, public DoublyTagNode <Type>{ private: LchRsibNode<Type> *V; //存储左子女-右兄弟链表的向量 DoublyTagNode <Type> *U; //存储双标记表的向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 public: dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) { V = new LchRsibNode <Type> [Maxsz]; U = new DoublyTagNode <Type> [Maxsz]; } } (2) 森林的双标记先根次序表示向左子女-右兄弟链表先根次序表示的转换 void staticlinkList<Type> :: DtagF-LchRsibF ( ) { Stack<int> 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-18 二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点， 再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种 双序遍历的算法