二叉树性质及习题

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

二叉树性质：
1.在二叉树的第 k层至多有 2^(k －1)个结点。(k>=1)
2.深度为 k 的二叉树至多有 2^(k-1)个结点(k >=1)。
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.具有 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.如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到最后一层，每层从左到右），对任一结点i（1<=i<=n）有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点 ⌊ i/2 ⌋ 。
如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i 。
如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1 。

完全二叉树：
定义：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（结点可为单个）
(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）
(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

性质：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则 ：
①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一 个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点
②n= 1+n1+2n2 ；由①、②两式把n2消去得：n= 2n0+n1-1，**由于完全二叉树中度为1的结点数只有两种可能0或1，**由此得到n0=n/2 或 n0=(n+1)/2。

 **简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）向下取整。可根据完全二叉树的结点总数计算出叶子结点数。**

完全二叉树通常采用数组存储

习题：
例：
设一棵完全二叉树共有699个结点，则在该二叉树中的叶子
多种方法：
1.根据 “二叉树的第 i层至多有 2^(i – 1) 个结点；深度为 k的二叉树至多有
2^k – 1 个结点（根结点的深度为 1）”这个性质：
因为 2^9-1 < 699 < 2^10-1 , 所以这个完全二叉树的深度是 10，前 9层是一个满二叉树，这样的话，前九层的结点就有 2^9-1=511 个；而第九层的结点数是 2^(9-1)=256
所以第十层的叶子结点数是 699-511=188 个；
现在来算第九层的叶子结点个数。
由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有 188个，所以应该去掉第九层中的 188/2=94个；
所以，第九层的叶子结点个数是 256-94=162，加上第十层有 188个，最后结果是 350个。
2.根据 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）向下取整。可根据完全二叉树的结点总数计算出叶子结点数得到结果
其他题目：https://wenku.baidu.com/view/988bd3b5ab00b52acfc789eb172ded630b1c98e6.html?re=view