第6章树与森林 ∥结点的左子女、右兄弟指针 LchRsibNode ( ink(NULL), rlink(NULL)& LchRsibNode( Type x ) Ilink(NULL), rlink(NULL), data(x)J template< lass Type> class Doubly TagNode{∥双标记表结点类的定义 protected: Type data; 点数据 int itag, rtag: 点的左子女、右兄弟标记 Doubly Tag Node(): Itag(O), rtag(0) Doubly TagNode( Type x): Itag(O), rtag(0), data(x)0 template <class Type> class staticlinkList 态链表类定义 public LchRsibNode<Type>, public Doubly TagNode <Type>t ∥储左子女右兄弟链表的向量 Doubly Tag Node <Type>*U: ∥存储双标记表的向量 ∥向量中最大元素个数和当前元素个数 dstaticlinkList int Maxsz ) MaxSize( Maxsz ) CurrentSize(0)i U =new Doubly Tag Node <Type>[Maxszl 森林的双标记先根次序表示向左子女右兄弟链表先根次序表示的转换 taticlinkList<Type>:: Dtag F-LchRsibF O t for int i=0; i<CurrentSize; i++)i switch(U0 Itag)t case0: switch(UO]. rtag)i case0: vI.ink=Vo rlink=-1; if(st IsEmpty (=0) ik=st GetTop(: st Pop(: Vik]. rlink=i+l; case 1: VO Ilink=-I; Vo rlink =i+I; break case 1: switch(UO]. rtag)i se0: Vo. Il 1: VO. rlink=-l; break case 1: Vo Ilink =1+1: st Push(1);第 6 章 树与森林 76 int llink, rlink; //结点的左子女、右兄弟指针 public: LchRsibNode ( ) : llink(NULL), rlink(NULL) { } LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) { } } template <class Type> class DoublyTagNode { //双标记表结点类的定义 protected: Type data; //结点数据 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 );