习题六分析和总结.docx

⑴ 假设在树中， 结点 x 是结点 y 的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为 { (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题： ① 哪个是根结点? 哪些是叶子结点? 哪个是 g 的双亲? 哪些是 g 的祖先? 哪些是 g 的孩子? 那些是 e 的子孙? 哪些是 e 的兄弟? 哪些是 f 的兄弟? ② b 的层次各是多少? 树的深度是多少? 以结点 c 为根的子树的深度是多少? 根节点：a 叶子节点：i ,d , j, f , l g 的双亲节点:c g 的 祖 先 ：c , a g 的 孩 子：j e 的子孙：i e 的兄弟：d f 的兄弟：g , h b 的层次：2 树的深度：4 以结点 c 为根的子树的深度：3 ⑵ 一棵深度为 h 的满 k 叉树有如下性质： 第 h 层上的结点都是叶子结点， 其余各层上每个结点都有 k 棵非空子树。 如果按层次顺序(同层自左至右)从 1 开始对全部结点编号，问： ① 各层的结点数是多少? ② 编号为 i 的结点的双亲结点(若存在)的编号是多少? ③ 编号为 i 的结点的第 j 个孩子结点(若存在)的编号是多少? ④ 编号为 i 的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 设层号为 i 的结点数目为 m=k^(i-1) 编号为 i 的结点的双亲结点的编号是：[(i+k-2)/k](不大于(i+k-2)/k 的最大整数。也就是(i+k-2)与 k 整除的结果.以下/表示整除。 编号为 i 的结点的第 j 个孩子结点编号是：k*(i-1)+1+j; 编号为i 的结点有右兄弟的条件是(i-1)能被k 整除 右兄弟的编号是i+1. ⑶ 设有如图 6-27 所示的二叉树。 ① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。 a b c d e f g 0 0 h k 0 0 m n顺序存储结构： 链式存储结构 a b c d e f g 0 0 h k 0 0 m n a a b c ? d ? e ? f ? g ? h ? ? k ? ? m ? ? n ? 先序：abdehkcfgmn 中序：dbhekafcmgn 后序：dhkebfmngca ⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为 ABDGHCEFI 和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。 A A B C D E F G H I 后序：GHDBEIFCA AB A B F C G D E H 先序遍历：ABCDEFGH ⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为 dgbaekchif 和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。 二叉树： 中序线索树： abc a b c d e f g k h i NULL a NULL b c NULL d e f g k h i ⑺ 以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法 叶子节点数： #define MAX_NODE 50 int search_leaves( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T; int top=0, num=0; if (T!=NULL) { stack[++top]=p ; while (top>0) { p=stack[top--] ; if (p->Lchild==NULL&&p->Rchild==NULL) num++ ; if (p->Rchild!=NULL ) stack[++top]=p->Rchild; if (p->Lchild!=NULL ) stack[++top]=p->Lchild; } } return(num) ; } ⑻ 设图 6-27 所示的二叉树是森林 F 所对应的二叉树，请画出森林 F。 森林 F： abek a b e k d h c f g m n ⑼ 设有一棵树，如图 6-28 所示。 ① 请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。 ② 请给出该树的先序遍历序列和后序遍历序列。 ③ 请将这棵树转换成二叉树 双亲表示法： 0 a -1 1 b 0 2 c 0 3 m 0 4 d 1 5 e 1 6 h 2 7 k 2 8 g 2 9 f 3 10 n 3 孩子表示法： a1 a 1 2 3 ? b 4 5 ? c 6 7 8 ? m 9 10 ? d e h k g f n ? ? ? ? ? ? ? 1 2 3 4 5 6