一、二叉树的定义
与树结构定义类似,二叉树的定义也以递归形式给出:二叉树是n(n≥0)个结点的有限集合,该集合或者为空集(当n=0),或者由一个称为根(root)的结点及两棵不相交的左子树和右子树组成。
二叉树的特点如下:
-
每个结点最多有两个孩子,或者说,在二叉树中,不存在度大于 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),都有
-
如果
i=1
,则结点 i 是这棵完全二叉树的根,没有双亲;否则,其双亲结点的编号为[i/2]
。 -
如果
2i>n
,则结点 i 没有左孩子;否则,其左孩子结点的编号为 2i。 -
如果
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 成立。