c,a是g的祖先； j,k是g的孩子； imn是e的子孙；
d是e的兄弟；g,h是f的兄弟； b的层次是2；n的层次是5； 树的深度是5；
以c为根的子树深度是3； 树的度数是3；
关闭6.2 一棵度为2的有序树与一棵二叉树有何区别? 答：
一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。 关闭
6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 答：
三个结点的树如下：只有两种形态 ○ ○ / \\ | ○ ○ ○ | ○
三个结点的二叉树如下所示：有五种形态： (1) (2) (3) (4) (5) ○ ○ ○ ○ ○ / \\ / / \\ \\
○ ○ ○ ○ ○ ○ / \\ / \\
○ ○ ○ ○
6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子? 解：
设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+…+nm (1) 又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为：
n-1=0*n0+1*n1+2*n2+…+m*nm (2) 联立(1)(2)方程组可得：
叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm 关闭
6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其
余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：
(1)各层的结点数目是多少?
(2)编号为i的结点的双亲结点(若存在)的编号是多少?
(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?
(4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 解：
(1) 层号为h的结点数目为kh-1
(2) 编号为i的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k的最大整数。也就是(i-2)与k整除的结果.以下/表示整除。 (3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j; (4) 编号为i的结点有右兄弟的条件是(i-1)能被k整除 右兄弟的编号是i+1.
关闭6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点? 解：
高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。 关闭
6.7 在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针? 解：
n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1; 关闭
6.8 假设二叉树包含的结点数据为1，3，7，12。 (1)画出两棵高度最大的二叉树；
(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。 解：
(1)高度最大的两棵二叉树如图： ○1 ○1 / \\ ○3 ○3 / \\ ○7 ○7 / \\
○2 ○2 / \\
○12 ○12
(2)两棵完全二叉树如下：
○12 ○12 / \\ / \\ ○7 ○3 ○7 ○3
/ \\ / \\ ○1 ○2 ○2 ○1 关闭
6.9试找出分别满足下面条件的所有二叉树：
(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；
(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。 答：
(1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。
(2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。
(3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。 (4) 前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。 关闭
6.10 试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。 解：
(1)顺序存储方法： 二叉树(a):
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
__________________________________________________________________ bt | |1 |2 |∮|∮|3 |∮|∮|∮|∮|4 |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮| 5| __________________________________________________________________ 二叉树(b):
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
__________________________________________________________________________________
bt| |1 |∮|2 |∮|∮|3 |∮|∮|∮|∮|∮|∮|4 |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|5 |
__________________________________________________________________________________ 二叉树?:
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 _______________________________________________________________________________
bt | |1 |∮|2 |∮|∮|3 |4 |∮|∮|∮|∮|5 |6 |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|7 |8 |
_______________________________________________________________________________ 二叉树(d):
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
┌—┬—┬—┬—┬—┬—┬—┬—┬—┬—┬—┬—┬—┬—┬—┬—┐
bt│ │1 │2 │3 │4 │∮│5 │6 │∮│7 │∮│∮│∮│∮│ 8│9 │ └—┴—┴—┴—┴—┴—┴—┴—┴—┴—┴—┴—┴—┴—┴—┴—┘
(2)链式存储结构： 二叉树(a): ↓root
┌—┬—┬—┐ │ │1 │∧│ └┼┴—┴—┘ ↓
┌—┬—┬—┐ │∧│2 │ │ └—┴—┴┼┘ ↓
┌—┬—┬—┐ │ │3 │∧│ └┼┴—┴—┘ ↓
┌—┬—┬—┐ │∧│4 │ │ └—┴—┴┼┘ ↓
┌—┬—┬—┐ │∧│5 │∧│ └—┴—┴—┘ 二叉树(b): ↓root
┌—┬—┬—┐ │∧│1 │ │ └—┴—┴┼┘ ↓
┌—┬—┬—┐ │ │2 │∧│ └┼┴—┴—┘ ↓
┌—┬—┬—┐ │∧│3 │ │ └—┴—┴┼┘ ↓
┌—┬—┬—┐ │ │4 │∧│ └┼┴—┴—┘ ↓
┌—┬—┬—┐
│∧│5 │∧│ └—┴—┴—┘ 二叉树?: ↓root
┌—┬—┬—┐ │∧│1 │ │ └—┴—┴┼┘ ↓
┌—┬—┬—┐ │ │2 │ │ └┼┴—┴┼┘ ↓ ↓
┌—┬—┬—┐┌—┬—┬—┐ │ │3 │ ││∧│4 │∧│ └┼┴—┴┼┘└—┴—┴—┘ ↓ ↓
┌—┬—┬—┐ ┌—┬—┬—┐ │ │5 │ │ │∧│6 │∧│
解：各二叉树所对应森林如下：
(a) ○A (b) ○A / ○B / ○C
? ○A ○B ○C (d) ○A ○C | ○B
(e) ○A ○C ○F ○I / \\ |
○B ○E ○L / | \\
○D○H○K | |
○G ○J 关闭
6.18高度为h的严格二叉树至少有多少个结点?至多有多少个结点? 答：
所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。