第6章树与森林 6-16请画出右图所示的树所对应的二叉树。 【解答】 对应二叉树 6-17在森林的二叉树表示中,用link存储指向结点第一个子女的指针,用 rlink存储指向结点下一个兄 弟的指针,用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示,同时按森林的先根 次序依次安放森林的所有结点,则可以在它们的结点中用只有一个二进位的标志tag代替link,用rtag 代替 rlink。并设定若ltag=0,则该结点没有子女,若tag≠0,则该结点有子女;若rag=0,则该结点 有下一个兄弟,若rtag≠0,则该结点有下一个兄弟。试给出这种表示的结构定义,并设计一个算法, 将用这种表示存储的森林转换成用link-rink表示的森林 【解答】 对应二叉树 234567 森林的左子女-右兄弟 rinks 3-1-17-1-110-1 表示的静态二叉链表 2345678910 BCDE GH 森林的双标记表示 (1)结构定义 template <class Type> class LchRsibNode i ∥左子女一右兄弟链表结点类的定义 protecte Type data ∥结点数据第 6 章 树与森林 75 6-16 请画出右图所示的树所对应的二叉树。 【解答】 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; //结点数据 5 2 8 3 4 5 2 8 3 4 6 5 2 8 3 4 6 10 5 2 8 3 4 6 10 14 1 对应二叉树 1 2 2 3 3 4 4 5 5 6 7 6 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 森林的双标记表示