6.2.2　二叉树的性质

性质1 一棵非空二叉树的第i层上最多有2i－1个结点（i≥1）。

该性质可由数学归纳法证明。证明略。

性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。

证明 设第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为M，xi最多为2i－1，则有

性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有

证明 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有

在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设B为二叉树中的分支数，那么有

这些分支是由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有

综合式（6－1）、式（6－2）、式（6－3）可以得到

性质4 具有n个结点的完全二叉树的深度k为［log2n］＋1。

证明 根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有

即

对不等式取对数，有

由于k是整数，所以有k＝［log2n］＋1。

性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有

（1）如果i＞1，则序号为i的结点的双亲结点的序号为i／2（“／”表示整除）；如果i＝1，则序号为i的结点是根结点，无双亲结点。

（2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i＞n，则序号为i的结点无左孩子。

（3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1＞n，则序号为i的结点无右孩子。

此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）／2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。

此性质可采用数学归纳法证明。证明略。