二叉树

一、二叉树的定义

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

二叉树的特点如下:

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

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

    二叉树的五种形态

二、二叉树的性质

性质1

若二叉树的层数从 1 开始,则二叉树的第k层结点数最多为个 2k-1(k>0)。

性质2

深度(高度)为k的二叉树最大结点数为 2k-1(k>0)。

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

性质3

对任意一棵二叉树,如果叶子结点个数为n0,度为 2 的结点个数为n2,则有n0=n2+1。

证明:设二叉树中度为 1 的结点个数为n1,根据二叉树的定义(二叉树中所有结点的度均小于或等于 2)可知,该二叉树的结点总数为

n = n0 + n1 + n2

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

n = n1 + 2n2 + 1

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

n0 = n2 + 1

满二叉树

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

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

满二叉树示意图:
满二叉树

完全二叉树

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

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

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

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

满二叉树与完全二叉树

性质4

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

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

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

将不等式两端加 1 得到

2K-1≤n<2K

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

K-1≤log2n<K

由此可以得到

[log2n]=K-1

整理后得到

K=[log2n]+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 的左、右孩子编号分别为 2i2i+1,所以,结点 i+1 的左、右孩子编号分别为 2i+22i+3。提取公因式后可以得到:2(i+1)2(i+1)+1,即结点 i+1 的左孩子编号为 2(i+1),右孩子编号为 2(i+1)+1

又因为二叉树由 n 个结点组成,所以,当 2(i+1)+1>n2(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 成立。

用户头像
登录后发表评论