习题6

6.1 已知一棵树如图6.11所示，请回答以下问题：

（1）树中哪个结点为根结点？哪些结点为叶子结点？

（2）结点B的双亲为哪个结点？其子女为哪些结点？

（3）哪些结点为结点I的祖先？哪些结点为结点B的子孙？

（4）哪些结点为结点D的兄弟？哪些结点为结点K的兄弟？

（5）结点J的层次为多少？树的高度为多少？

（6）结点A、C的度分别为多少？树的度为多少？

（7）以结点B为根的子树的高度为多少？

（8）试给出该树的括号表示及层号表示形式。

6.2 试写出图6.11所示树的前序遍历、后序遍历和层次遍历的结果。

6.3 试给出图6.11中树的双亲表示法和数组方式孩子表示法的表示。

6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……nm个度为m的结点，问该树中有多少个叶子结点？

6.5 一棵含有n个结点的k度树，可能达到的最大深度和最小深度分别为多少？

6.6 试编写一个递归算法，将一棵树的双亲表示法转换成树的孩子兄弟表示法。

6.7 假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的前序遍历算法。

6.8 假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的后序遍历算法。

6.9 假设树采用指针方式的孩子表示法表示，试编写一个函数，判断两棵给定的树是否等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。