大家好，又见面了，我是你们的朋友全栈君。
二叉树（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
