二叉树性质总结

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

性质1：二叉树第i(i>=1)层上的节点数最多为2^(i-1)

证明：

归纳基础：第一层有一个节点，第二层最多有两个节点，第三层最多有四个节点，以此类推，数学归纳法证明如下：

i=1时，2^(i-1)=2^0=1，因为第一层上为根节点，所以命题成立。

归纳假设：假设对所有的j(1<=j<i)命题成立，即第j层上至多有2^(j-1)个节点，需要证明j=i时命题依然成立。

归纳步骤：根据归纳假设，第i-1层上至多有2(i-2)个节点，由于二叉树每个节点至多有两个孩子节点，所以第i层上的最多节点数是第i-1层上最多节点数的2倍，即j=i时，该层上最多有2^(i-2)*2=2^(i-1)个节点，因此命题成立。

性质2：高度为k的二叉树最多有2^k – 1个节点。

性质2可以根据性质1证明，即SUM(2^(i-1))(1<=i<=k)  =  2^k – 1(等比数列求和)

性质3：对于任何二叉树T，n0、n1、 n2分别代表度数为0、1、2的节点个数，则n0=n2+1

证明：因为二叉树所有节点的度数均不大于2，所以节点总数（记为n）应该等于0度节点数、1度节点数、2度节点数之和，即n0+n1+n2=n；

1度节点有一个儿子，2度节点有两个儿子，所以二叉树中所有儿子节点的个数是n1+n2，二叉树中只有根节点不是任何节点的儿子节点，因此二叉树中节点总数可以表示为n=n1+2n2+1

有上述两个公式n0+n1+n2=n、n=n1+2n2+1可得：n0=n2+1

性质4：具有n个节点的完全二叉树（包括满二叉树）的高度为[logn]+1（不做特殊说明这里的log都是以2为底的）

证明：设所求完全二叉树的深度为k，有完全二叉树的定义可知，其前k-1层是深度为k-1的满二叉树，一共有2^(k-1)-1个节点，由于完全二叉树深度为k，故第k蹭上还有若干节点，因此该完全二叉树的节点个数n>2^(k-1)-1。由性质2可知n<=2^k – 1，所以

2^(k-1) – 1< n <= 2^k-1

由此推导可得2^(k-1) <= n < 2^k，取对数后有

k-1 <= logn < k

因为k为整数，所以有k-1=logn,即可得k=[logn]+1

二叉树还具有其他性质，读者有兴趣可以自己推导得出，对以上四种性质比较常用，并且对于性质4在研究二叉树时间复杂度的时候可能会有所帮助理解nlogn这种时间复杂度的来源。