数据结构习题课第8、7、6章(网上的答案有些有问题的)

系 ） 的存储。

6.3 对于一棵具有n 个结点的树，该树中所有结点的度数之和为（ n-1 ）。 6.4 已知一棵树如图6.11 所示，试回答以下问题：

（1）树中哪个结点为根结点？哪些结点为叶子结点？ 答：A 是根结点；E，G，H，I，C，J，K，L 为叶结点。 （2）结点B 的双亲为哪个结点？其子女为哪些结点？ 答：B 的双亲结点是A，其子女结点为E 和F。

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

答：F，B，A 是结点I 的祖先结点；E，F，G，H，I 是B 的子孙结点。 （4）哪些结点为结点D 的兄弟？哪些结点为结点K 的兄弟？ 答：B，C，L 是结点D 的兄弟结点，J 是结点K 的兄弟结点。 （5）结点J 的层次为多少？树的高度为多少？ 答：结点J 的层次为3，树的高度为4。

（6）结点A、C 的度分别为多少？树的度为多少？ 答：结点A 的度为4，结点C 的度是0，树的度是4。

（7）以结点B 为根的子树的高度为多少？ 答：以结点B 为根的子树的高度是3。 （8）试给出该树的括号表示及层号表示形式。

答：该树的括号表示为：A（B（E，F（G，H，I）），C，D（J，K），L），该树的层号

表示为：10A，20B，30E，30F，40G，40H，40I，20C，20D，25J，25K，20L 6.5 试写出图6.11 所示树的前序遍历、后序遍历和层次遍历的结果。

答： 前序遍历：ABEFGHICDJKL 后序遍历：EGHIFBCJKDLA 层次遍历：ABCDLEFJKGHI

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

#include \

int PostOrderByStack (TreeNode *root) {

TreeNode *temp;

TreeNode *stack[MAXLEN];

// childSeq 表示当前打印到了此树第几个孩子，

int top,childSeq[MAXLEN]; int i;

top = -1; //初始化空栈

temp = root; while (1) {

while (temp != NULL)

{

for (i = 0;i < MAXN;i++) { if (temp->child[i] != NULL) { childSeq[++top] = i + 1; stack[top] = temp; temp = temp->child[i]; break; } }

// 如果此节点是叶子节点，则输出该结点 if (i == MAXN)

{ printf (\

temp = NULL; break; } }

while (top != -1 ) {

for (i = childSeq[top];i < MAXN;i++) {

if (stack[top]->child[i] != NULL) {

temp = stack[top]->child[i]; childSeq[top] = i + 1; break; } }

if (i == MAXN) {

printf (\ top--; }

if (temp != NULL) {

break; } }

if (top == -1) { return 1;

} } } int main ()

{ char string[MAXLEN]; TreeNode *root = NULL;

printf (\请用树的括号表示法输入一棵树:\\n\ scanf (\

root = CreateTree (root,string); PostOrderByStack (root); return 0; }