二叉树的五大性质及证明「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

二叉树（Binary Tree）

定义：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 特点：每个结点至多只有两棵子树（二叉树中不存在度大于2的结点） 五种形态：

1. 性质1

性质1 在二叉树的第 i 层至多有 2^(i －1)个结点。(i>=1)

[用数学归纳法证明]

证明：当i=1时，只有根结点，2^(i －1)=2^0=1。

1) 设：对所有j，i>j>=1，命题成立，即第j层上至多有2^(j-1)个结点。

2) 由归纳假设第i-1层上至多有2^(i－2)个结点。

3) 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2* 2^(i－2)= 2^(i-1)

证毕。

2. 性质2

性质2 深度为 k 的二叉树至多有 2^(k-1)个结点(k >=1)。

证明：由性质1可见，深度为k的二叉树的最大结点数为

3. 性质3

性质3 对任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为 n2,则n0＝n2＋1。

证明：若度为1的结点有 n1个，总结点个数为n，总边数为 e，则根据二叉树的定义，

n = n0 + n1 + n2

e = 2n2 + n1 = n – 1 (除了根节点，每个节点对应一条边 )

因此，有 2n2+ n1 =n0 + n1 + n2- 1

n2= n0 – 1 => n0= n2+ 1

空链域：2n0+ n1 = n0 + n2 +1+ n1 = n+1

4. 性质4

性质4 具有 n (n>=0) 个结点的完全二叉树的深度为

＋1

证明：设完全二叉树的深度为 h，则根据性质2 和完全二叉树的定义有

2^(h－1)- 1 < n <= 2^h – 1或 2^(h－1)<= n < 2^h

取对数 h－1 < log2n <= h，又h是整数，

因此有 h =

＋1

5. 性质5

性质5 如将一棵有n个结点的完全二叉树自顶向下，同层自左向右连续为结点编号0,1, …, n-1，则有：

1）若i = 0, 则 i 无双亲, 若i > 0, 则 i 的双亲为」(i -1)/2」

2）若2*i+1 < n, 则i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2

3）若结点编号i为偶数，且i != 0,则左兄弟结点i-1.

4）若结点编号i为奇数，且i != n-1,则右兄弟结点为i+1.

5）结点i 所在层次为」log2(i+1) 」

参考资料：

1. Boss的PPT

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/145002.html原文链接：https://javaforall.cn