软件基础习题答案 第三章习题 1.试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。 解答: 具有3个结点的树只有两种不同形态:(1)和(2);具有3个结点的二叉树有下列 五种形态:(a)、(b)、(c)、(d)、(e)。 (a) (b) (c) (d) (e) 2.若一棵树有n个度为1的结点,n2个度为2的结点,…,n个度为m的结点,则这棵 树中的叶子结点有多少个? 解答: 这棵树中的叶子结点个数no=1+∑(1-1)n;=1+n2+(m-1)nm 3.给出题图3.1中所示的二叉树的先序、中序和后序遍历序列,并画出其顺序和链式存储 结构 题图3.1 解答: 先序: ABDGHCEIFJ中序: GDHBAEICFJ后序: GHDBIEJFCA 顺序存储结构: 巴凹" 链式存储结构:软件基础习题答案 第三章习题 1．试分别画出具有 3 个结点的树和具有 3 个结点的二叉树的所有不同形态。 解答： 具有 3 个结点的树只有两种不同形态：（1）和（2）；具有 3 个结点的二叉树有下列 五种形态：（a）、（b）、（c）、（d）、（e）。 A B C （a） A B C A B C A B C A B C (1) (2) （b） （c） （d） （e） 2．若一棵树有 n1 个度为 1 的结点，n2 个度为 2 的结点，…，nm个度为 m 的结点，则这棵 树中的叶子结点有多少个？ 解答： 这棵树中的叶子结点个数  = = + − m i 1 i n0 1 (i 1)n =1 + n2+（m - 1）nm 3．给出题图 3.1 中所示的二叉树的先序、中序和后序遍历序列，并画出其顺序和链式存储 结构。 题图 3.1 解答： 先序：ABDGHCEIFJ 中序：GDHBAEICFJ 后序：GHDBIEJFCA 顺序存储结构： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J 链式存储结构： B C D D B E H F B J B A G B I B