数据结构(8) 树[二]（二叉树以及性质）

拼搏现实的明天。 2022-02-03 06:55 286阅读 0赞

## 二叉树定义 ##

**二叉树：是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。**

如下图就是一个二叉树：

![img][]

### 二叉树特点 ###

二叉树的特点有：

*  **每个结点最多两个子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。**
 *  **左子树和右子树是有顺序的，次序不能任意颠倒。**
 *  **即使树中的某结点只有一棵子树，也要区分它是左子树还是右子树。如图：树1和树2是同一棵树，但却是不同的二叉树。**

![img][img 1]

二叉树具有五种基本形态：

1.  **空二叉树；**
2.  **只有一个根结点；**
3.  **根结点只有左子树；**
4.  **根结点只有右子树；**
5.  **根结点既有左子树又有右子树。**

不同形态的二叉树

![img][img 2]

### 特殊二叉树 ###

再来介绍一些特殊的二叉树。

1、斜树

顾名思义，斜树一定是斜的，但是往那边斜还是有讲究的。

**所有的结点都只有左子树的二叉树叫左斜树，所有结点都是只有右子树的二叉树叫右斜树。两种统称为斜树。**

下面两个图分别就是左斜树和右斜树：

![img][img 3]

![img][img 4]

2、满二叉树

**在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样的二叉树叫做满二叉树**。如图

![img][img 5]

单单是每个结点都有左右子树，不能算是满二叉树，

还必须要所有的叶子结点都处在同一层，这样就做到了二叉树的平衡。

因此满二叉树的特点有：

1.  **叶子只能出现在最下面一层，出现在其他层就不能达到平衡；**
2.  **非叶子结点的度一定是2；**
3.  **同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。**

3、完全二叉树

\*\*对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。\*\*如图：

![img][img 6]

首先要从字面上区分，“完全”和“满”的差异，**满二叉树一定是完全二叉树**，**完全二叉树不一定是满的**。

注意完全二叉树中的编号与满二叉树中的相同，

而且编号全部连续，

有断开的就不是完全二叉树，

如下图中的三棵树都不是完全二叉树。

![img][img 7]

完全二叉树的特点：

1.  **叶子结点只能出现在最下面两层；**
2.  **最下层的叶子一定集中在左部连续位置；**
3.  **倒数二层，若有叶子结点，一定都在右部连续位置；**
4.  **如果结点的度为1，则该结点只有左孩子，即不存在只有右子树的情况；**
5.  **同样结点数的二叉树，完全二叉树深度最小。**

我们也得出一个判断某二叉树是否是完全二叉树的方法，那就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，\*\*如果编号出现空挡，就说明不是完全二叉树，\*\*否则就是。

# 二叉树的性质 #

二叉树有一些需要理解并记住的特性，便于更好地使用它。

## 二叉树性质1 ##

### **在二叉树的第i层上至多有**![img][img 8]**个结点（i>=1）。** ###

![img][img 9]

上图中：  
第1层： 1个： 21-1=20=1  
第2层： 1个： 22-1=21=2  
第3层： 1个： 23-1=22=4  
第4层： 8个： 24-1=23=8

通过数据归纳法，很容易得出在二叉树的第i层上最多有 ![img][img 10]个结点。

### 二叉树性质2 ###

### **深度为k的二叉树最多有**![img][img 11]**个结点（k>=1）。** ###

这里注意是2的k次幂再减1。

如果有一层，最多1=21-1个结点  
如果有两层，最多1+2=22-1个结点  
如果有三层，最多1+2+4=23-1个结点  
如果有四层，最多1+2+4+8=24-1个结点

通过数据归纳法的论证，可以得出如果有k层，结点数最多为![img][img 12]。

### 二叉树性质3 ###

**对任何一棵二叉树T，如果其终端结点数为**![img][img 13]**，度为2的结点数为**![img][img 14]**，则**![img][img 15]。

终端结点就是叶子结点，而一棵二叉树，除了叶子结点外，剩下的就是度为1和2的结点了，设![img][img 16]是度为1的结点数。则树T的结点总数就是![img][img 17]。

![img][img 18]

我们换个角度，再数一数连接线，由于根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去1，n-1=n1+2n2，又因为n=n0+n1+n2，得出n0=n2+1 。

### 二叉树性质4 ###

**具有n个结点的完全二叉树的深度为不大于log2n的最大整数+1 。**

这里不再详细推导。

### 二叉树性质5 ###

如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到最后一层，每层从左到右），对任一结点i（1<=i<=n）有：

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

[img]: /images/20220203/ad5fd64a822642339fb1f926d43093d6.png
[img 1]: /images/20220203/981a38205a034aa096ed8e5639f5ed1a.png
[img 2]: /images/20220203/a5e157b959d94c079d6db5e944d3041b.png
[img 3]: /images/20220203/c7a45bafe5e944738e708c9e32bf839e.png
[img 4]: /images/20220203/3fc112a7cea448b28d1793b7fd09c467.png
[img 5]: /images/20220203/2e4b8a3fa6924e8988f0139ac5777090.png
[img 6]: /images/20220203/8cbf8a6371a74d6cba27aef86dfa97c5.png
[img 7]: /images/20220203/e58933463b104727b105420ee6051eb0.png
[img 8]: /images/20220203/7045d2e5e0f841c580557825dce21127.png
[img 9]: /images/20220203/289228c2d5ca4f36b3f755261d17db36.png
[img 10]: /images/20220203/54290dee1ea24bc1b1a915a90bc45a9f.png
[img 11]: /images/20220203/8884d0842c3c41b8b862ac68c477647f.png
[img 12]: /images/20220203/d79d230e62684d03b0fb866af353cfb4.png
[img 13]: https://img-blog.csdnimg.cn/2019012410041291.png
[img 14]: https://img-blog.csdnimg.cn/20190124100420937.png
[img 15]: /images/20220203/cda5680e6d3c49d9ac67bb0a8de97c8d.png
[img 16]: https://img-blog.csdnimg.cn/20190124100508697.png
[img 17]: /images/20220203/7cf62b48ee9345fa8d4bdee582f9d8df.png
[img 18]: /images/20220203/968d5662dbe048d68b84d7a050916a3e.png