【解答】 对应二叉树 6-17在森林的二叉树表示中,用lmk存储指向结点第一个子女的指针,用rink存储指向结点下一个兄 弟的指针,用daa存储结点的值。如果我们采用静态二叉链表作为森林的存储表示,同时按森林的先根 次序依次安放森林的所有结点,则可以在它们的结点中用只有一个二进位的标志lag代替link,用nag 代替rink。并设定若lag=0,则该结点没有子女,若lag≠0,则该结点有子女;若rg=0,则该结点 没有下一个兄弟,若nag≠0,则该结点有下一个兄弟。试给出这种表示的结构定义,并设计一个算法 将用这种表示存储的森林转换成用link- rlink表示的森林 【解答】 对应二叉树 2345678910 G 森林的左子女-右兄弟 rlink[ 2 表示的静态二叉链表 0123 5678910 ataABCdE 森林的双标记表示 (1)结构定义 template< class Type> class LchRsibNode{∥左子女-右兄弟链表结点类的定义 protected Type da ∥结点数据 ∥结点的左子女、右兄弟指针 LchRsibNode (: llinkNULL), rlink(NULL) LchRsibNode( type x ): link(NULL), rlink(NULl), data(x)3 template< lass Type> class Doubly Tag Node{W双标记表结点类的定义 protecte Type data ∥结点数据【解答】 6-17 在森林的二叉树表示中，用 llink 存储指向结点第一个子女的指针，用 rlink 存储指向结点下一个兄 弟的指针，用 data 存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根 次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志 ltag 代替 llink，用 rtag 代替 rlink。并设定若 ltag = 0，则该结点没有子女，若 ltag  0，则该结点有子女；若 rtag = 0，则该结点 没有下一个兄弟，若 rtag  0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法， 将用这种表示存储的森林转换成用 llink - rlink 表示的森林。 【解答】 (1) 结构定义 template <class Type> class LchRsibNode { //左子女-右兄弟链表结点类的定义 protected: Type data; //结点数据 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; //结点数据 1 对应二叉树 1 2 2 3 3 4 4 5 5 6 6 7 8 8 7 A B C D E F G H K I J A B C D E F G H I K J 对应二叉树 llink data rlink 0 1 2 3 4 5 6 7 8 9 10 1 -1 -1 4 -1 6 -1 8 9 -1 -1 A B C D E F G H I K J 5 2 3 -1 -1 7 -1 -1 10 -1 -1 森林的左子女-右兄弟 表示的静态二叉链表 ltag data rtag 0 1 2 3 4 5 6 7 8 9 10 1 0 0 1 0 1 0 1 1 0 0 A B C D E F G H I K J 1 1 1 0 0 1 0 0 1 0 0 森林的双标记表示