二叉树性质

二叉树性质1
性质1：在二叉树的第i层上至多有2**i-1**个结点（i≥1）
在二叉树的第i层上至少有1个结点（没有就没有这一层了)
通过数据归纳法的论证，
二叉树性质2
性质2：深度为k的二叉树至多有2**k**-1个结点（k≥1）。
深度为K的二叉树至少有个k结点（斜树）
不是(2**k-1**+1)，这是完全二叉树的

二叉树性质3
性质3：对任何一棵二叉树T，如果其终端结点数为n 0 ，度为2的结点数为n 2 ，则n 0 =n 2+1。
二叉树性质4
性质4：具有n个结点的完全二叉树的深度为|log 2 n+1|（|x|表示不大于x的最大整数）。

• 由满二叉树的定义我们可以知道，深度为k的满二叉树的结点数n一定是2 k -1。因为这是最多的结点个数。
• 那么对于n=2 k -1倒推得到满二叉树的深度为k=log 2 (n＋1)，比如结点数为15的满二叉树，深度为4。

完全二叉树我们前面已经提到，它是一棵具有n个结点的二叉树，若按层序编号后其编号与同样深度的满二叉树中编号结点在二叉树中位置完全相同，那它就是完全二叉树。

• 也就是说，它的叶子结点只会出现在最下面的两层。

它的结点数一定少于等于同样深度的满二叉树的结点数2k-1，但一定多于2k-1 -1。
即满足2k-1-1由于结点数n是整数，
n≤2k-1意味着n<2k ，
n>2k-1-1，意味着n≥2k-1，
所以2k-1≤n<2k ，不等式两边取对数，得到k-1≤log 2 n<k，而k作为深度也是整数，因此k=|log 2 n|+1。

二叉树性质5
性质5：如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：

• 如果i=1，则结点i是二叉树的根，无双亲；
• 如果i>1，则其双亲是结点【i/2】
• 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
• 我们以图6-6-2为例，来理解这个性质。这是一个完全二叉树，深度为4结点总数是10。

图6-6-2
对于第一条来说是很显然的，i=1时就是根结点。i>1时，比如结点7，它的双亲就是，结点9，它的双亲就是。
第二条，比如结点6，因为2×6=12超过了结点总数10，所以结点6无左孩子，它是叶子结点。同样，而结点5，因为2×5=10正好是结点总数10，所以它的左孩子是结点10。
第三条，比如结点5，因为2×5+1=11，大于结点总数10，所以它无右孩子。而结点3，因为2×3+1=7小于10，所以它的右孩子是结点7。