第六章 树和二叉树习题1

一、判断正误 （ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （ ）2.二叉树中每个结点的两棵子树的高度差等于1。 （ ）3.二叉树中每个结点的两棵子树是有序的。 （ ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （ ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。 （ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （ ）10.具有12个结点的完全二叉树有5个度为2的结点。 二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。本题涉及的知识点广泛，包括二叉树的基本性质、存储结构、形态多样性、完全二叉树以及相关计算。 1. 在二叉树的二叉链表存储结构中，每个节点有两个指针域，分别指向左子树和右子树。因此，如果有n个节点，会有n-1个非空指针域，因为除了根节点之外，每个节点都有一个父节点指向它。 2. 二叉树中，节点的两棵子树高度差不一定等于1，这个说法不正确。例如，完全平衡的二叉树中，高度差才等于1，但二叉树可以是任意形状的。 3. 二叉树的子树顺序性取决于特定的二叉树类型，如二叉排序树（BST），其中左子树的所有节点值小于父节点，右子树的所有节点值大于父节点，但对于一般的二叉树，没有这样的顺序规定。 4. 二叉树的节点可以有两棵非空子树，两棵空子树，或者一棵非空一棵空的子树，但并不是说必须满足这种情况。 5. 描述的是二叉排序树（BST）的特性，而不是所有二叉树的特性。在BST中，节点的关键字值确实在其左子树所有节点值之上，右子树之下。 6. 二叉树的节点个数与深度的关系并不总是2k-1-1。例如，高度为1的二叉树只有一个节点，不是2k-1-1。 7. 二叉树中，不存在非空左子树并不意味着不存在非空右子树，反之亦然。比如，单支二叉树只有一个子节点，可以是左也可以是右。 8. 非空二叉树的第i层最多能有2i-1个节点，这是正确的，这是完全二叉树的性质。 9. 用二叉链表法存储n个节点的二叉树，确实有n+1个空指针，因为除了根节点，每个节点都只连接一个子节点。 10. 具有12个节点的完全二叉树，度为2的节点数是5，这是正确的。完全二叉树在最后一个层级之前都是满的，12个节点的完全二叉树会是这样的形态：1个度为1的节点，5个度为2的节点，6个叶子节点。 二叉树的形态非常多样，由几个节点构建的二叉树形态数量可以通过排列组合来计算。例如，3个节点可以构建出5种不同的形态。深度为6的满二叉树有31个分支节点（度为2的节点）和32个叶子节点。具有257个节点的完全二叉树的深度可以通过对数计算得出，大约是8，具体的计算涉及到二进制转换和向上取整。 完全二叉树的叶子节点和总节点数的关系可以用公式2^(k-1) <= n < 2^k来推算，其中k是深度，n是节点数。例如，700个节点的完全二叉树有350个叶子节点。325个节点的完全二叉树，同样通过公式可得，叶子节点数为162，度为2的节点数为161，只有非空左子树的节点数为1，只有非空右子树的节点数为0。 对于n叉树的深度和宽度，最大深度是n，最小深度是1。至于前序、中序和后序遍历，它们可以唯一确定一棵二叉树，而给定这些序列可以推导出后序序列。例如，前序是BEFCGDH，中序是FEBGCHD，那么后序是FEGHBCD。哈夫曼树是用于数据压缩的，构造出的树形结构使得路径权值最小，5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度可以通过构建过程计算得出。 空树既是一棵树也是一棵二叉树，二叉树可以使用顺序和链式存储，完全二叉树的深度与节点数的关系是2^(k-1) <= n < 2^k，把树转换成二叉树形态不是唯一的，但是二叉排序树的特性是有一定的规律。 通过这些解释，我们可以看到二叉树的概念、性质、存储和应用在计算机科学中的重要性，尤其是在数据结构和算法中。