Question

数据结构随笔——二叉树和五个重要性质

Answer 1

二叉树的定义不用多说，很多书本上都有明确的定义，但有些细节是笔者过去所没有注意的，先给出殷人昆教授对于二叉树的基本定义——

可以看出二叉树的定义是递归的，根结点的子树仍然是二叉树，到达空子树时递归定义结束。
一般来说，关于树的术语对于二叉树都是适用的，但应该明确的是二叉树不是树，理由如下：

那么，这就出现一个问题——二叉树的叶结点无子女，是否可称它为无子树？
根据定义，应该是不能的，因为可认为叶子点的左右子树为空子树。
虽然认识这一区别的目的并非应试，但笔者还是提一句：个人认为在一般的测试中未必会考察到这么细致，所以遇到忽略这一细致区别的出题人时请不要过于惊讶。

接下来的描述中有必要用到一些数学符号，在Markdown中不好画出，因此我们再次规定一些符号——

二叉树具有以下五个性质：

可以看出性质4和5是针对重要的特殊二叉树——完全二叉树的，在此先给出特殊二叉树的定义。

深度k的满二叉树是有2^k－1个结点的二叉树，在满二叉树中，每一层结点都达到了最大个数，除最底层结点的度为0外，其他各层结点的度都为2。

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与高度为k的满二叉树中编号为1 ~ n－1的结点一一对应，则称这棵二叉树为完全二叉树。
其特点是：上面从第1层到第k－1层的所有各层的结点数都是满的，仅最下面的第k层是满的，或从右往左连续缺少若干结点。

证明 ——
由之前的结论可知，k层结点数为n－（2＾（k－1）－1）；
由于仅最下面的第k层是满的，或从右往左连续缺少若干结点；
k层结点依次从左到右位于k－1层结点的下方，且中间不留空子树；
故表达式（n－（2＾（k－1）－1））／2的商为k－1层中度为2的结点，余数为度为1的结点。
故当n为奇数时，n1＝0；
　当n为偶数时，n1＝1；
由于k－1层以及以上的结点都是满的，即一共2＾（k－2）－1个结点；
n2＝ int_DOWN（（n－（2＾（k－1）－1））／2）＋2＾（k－2）－1
＝ int_DOWN（（n＋1）／2）－1
故当n为奇数时，n2＝ int_DOWN（n／2）＋1－1＝ int_DOWN（n／2），n0＝n2＋1；
　当n为偶数时，n2＝ n／2－1，n0＝n／2－1＋1＝n／2。
证毕。

如果结点编号从0开始，则有以下结论：
（1）结点i（1＜＝i＜＝n－1）的父结点为结点int_DOWN（（i－1）／2），结点0无父结点；
（2）分支结点中编号最大的是结点int_DOWN（（n－2）／2）或结点int_DOWN（n／2）－1；
（3）若i＜＝int_DOWN（（n－2）／2），则结点i的左子女为2＊i＋1；若i＜＝int_DOWN（（n－3）／2），则结点i的右子女为2＊i＋2；
（4）若i为偶数且大于0，则结点i有左兄弟结点i－1；若i为奇数且i＜＝n－2，则结点i有右兄弟结点i＋1；
（5）结点i（0＜＝i＜＝n－1）在第int_DOWN（log（2，i＋1））＋1。