Tim的资源站

一、二叉树的定义

与树结构定义类似，二叉树的定义也以递归形式给出：二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（当n=0），或者由一个称为根（root）的结点及两棵不相交的左子树和右子树组成。

二叉树的特点如下：

1. 每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于 2 的结点。

2. 二叉树是有序树而树是无序树，其子树的顺序不能颠倒。因此，二叉树有 5 种不同的形态，如下图所示：

   

二、二叉树的性质

性质1

若二叉树的层数从 1 开始，则二叉树的第k层结点数最多为个 2^k-1（k＞0）。

性质2

深度（高度）为k的二叉树最大结点数为 2^k-1（k＞0）。

证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质 1 可知，最大结点数应为每一层最大结点数之和，即 2⁰+2¹+…+2^k-1=2^k-1。

性质3

对任意一棵二叉树，如果叶子结点个数为n₀，度为 2 的结点个数为n₂，则有n₀=n₂+1。

证明：设二叉树中度为 1 的结点个数为n₁，根据二叉树的定义（二叉树中所有结点的度均小于或等于 2）可知，该二叉树的结点总数为

n = n₀ + n₁ + n₂

再看二叉树中的分支数。除根结点外，其余结点都有一个分支进入。设 B 为分支总数，则n=B+1，由于这些分支是由度为 1 或 2 的结点发出的，所以又有 B=n₁+2*n₂于是得

n = n₁ + 2n₂ + 1

综合上述n的两种计算公式，可得

n₀ = n₂ + 1

满二叉树

如果一个深度为 K 的二叉树拥有 2^K-1 个结点，则将它称为满二叉树。

或者说：如果一棵二叉树中任何结点，或者是叶结点，或者是有两棵非空子树，且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。即在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。从定义可知：必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。

满二叉树示意图：

完全二叉树

有一棵深度为 h、具有 n 个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下、从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为 1～n 的结点位置一一对应，则称这棵二叉树为完全二叉树。

从满二叉树及完全二叉树的定义可以得出如下结论：

• 满二叉树一定是一棵完全二叉树。
• 完全二叉树不一定是一棵满二叉树。

满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层（最下层和次下层），且最下层的叶子结点集中在树的左部。深度为 4 的满二叉树和完全二叉树（8 个结点）如下图所示。

性质4

具有 n 个结点的完全二叉树的深度为[log₂n]+1。其中[log₂n]的结果是不大于 log₂n 的最大整数。

证明：假设具有 n 个结点的完全二叉树的深度为 K，则根据性质 2 可以得出

2^K-1-1<n≤2^K-1

将不等式两端加 1 得到

2^K-1≤n<2^K

将不等式中的 3 项同取以 2 为底的对数，并经过化简后得到

K-1≤log₂n<K

由此可以得到

[log₂n]=K-1

整理后得到

K=[log₂n]＋1

性质5

对于有 n 个结点的完全二叉树中的所有结点按从上到下、从左到右的顺序进行编号，则对任意一个结点 i（1≤i≤n），都有

1. 如果 i=1，则结点 i 是这棵完全二叉树的根，没有双亲；否则，其双亲结点的编号为 [i/2]。

2. 如果 2i>n，则结点 i 没有左孩子；否则，其左孩子结点的编号为 2i。

3. 如果 2i+1>n，则结点 i 没有右孩子；否则，其右孩子结点的编号为 2i+1。

下面利用数学归纳法证明这个性质。

证明：首先证明 2 和 3。

当 i=1 时，若 n≥3，则根的左、右孩子的编号分别是 2、3。若 n<3，则根没有右孩子；若 n<2，则根将没有左、右孩子。以上对于 ② 和 ③ 均成立。

假设对于所有的 1≤j≤i，结论成立，即结点 j 的左孩子编号为 2j，右孩子编号为 2j+1。

由完全二叉树的结构（上图）可以看出，结点 i+1 或者与结点 i 同层且紧邻 i 结点的右侧，或者 i 位于某层的最右端，i+1 位于下一层的最左端。

可以看出，i+1 的左、右孩子紧邻在结点 i 的孩子后面。由于结点 i 的左、右孩子编号分别为 2i 和 2i+1，所以，结点 i+1 的左、右孩子编号分别为 2i+2 和 2i+3。提取公因式后可以得到：2(i+1)和 2(i+1)+1，即结点 i+1 的左孩子编号为 2(i+1)，右孩子编号为 2(i+1)+1。

又因为二叉树由 n 个结点组成，所以，当 2(i+1)+1>n 且 2(i+1)=n 时，结点 i+1 只有左孩子，而没有右孩子；当 2(i+1)>n 时，结点 i+1 既没有左孩子也没有右孩子。

以上证明得到 2 和 3 成立。

下面利用上面的结论证明 1。

对于任意一个结点 i，若 2i≤n，则左孩子的编号为 2i；反过来，结点 2i 的双亲就是 i，而[2i/2]=i。若 2i+1≤n，则右孩子的编号为 2i+1；反过来，结点 2i+1 的双亲就是 i，而[(2i+1)/2]=i。由此可以得出 1 成立。