算法：什么是二叉树

Dear 丶 2023-03-14 10:56 4阅读 0赞

# 二叉树的定义 #

## 二叉树的特点 ##

*  每个节点最多有两棵子树，即二叉树中不存在度大于2的节点。

>  *  节点的度：就是当前节点有几个孩子
>  *  树的度：树中的节点最多可以拥有的孩子。
>     
>      *  如果最多2个孩子，就叫做二叉树
>      *  如果最多3个孩子，就叫做三叉树

*  左子树和右子树是有顺序的，次序不能任意颠倒，就像人的双手，双脚一样
 *  即使树中某节点只有一颗子树，也要取分它是左子树还是右子树。

## 二叉树的形态 ##

二叉树有五种基本形态

*  空二叉树
 *  只有一个根节点
 *  根节点只有左子树
 *  根节点只有右子树
 *  根节点既有左子树又有右子树

[N个节点的二叉树有多少种形态（卡特兰数）][N]

*  2个节点的树有2种形态
 *  3个节点的树有5种形态  
    ![在这里插入图片描述][2020102221464544.png_pic_center]

# 特殊的二叉树 #

## 斜树 ##

斜树的种类：

*  **左斜树**： 所有的节点都只有左子树
 *  **右斜树**： 所有的节点都只有右子树

斜树的特点：

*  每一层都只有一个节点
 *  节点的个数与二叉树的深度相同

## 满二叉树 ##

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

> 一颗深度为k且有2^(k-1)个节点的二叉树称为满二叉树

![在这里插入图片描述][20201022214923101.png_pic_center]

因此，满二叉树的特点：

*  叶子只能出现在最下面一层
 *  非叶子节点的度一定是2
 *  在同样深度的二叉树中。满二叉树的节点个数最多，叶子树最多

## 完全二叉树 ##

对一棵具有n个节点的二叉树按层序编号，如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，这样的二叉树叫做完全二叉树

> 当二叉树的深度为h时，它的h层节点必须都是连续靠左并不可隔开的(满二叉树也符合)，并且1～h-1层的结点数都达到最大个数(即1~h-1层为一个满二叉树)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

### 完全二叉树的特点： ###

*  叶子节点只能出现在最下面两层：**所有的叶节点都出现在第k层或者k-1层。**
 *  最下层的叶子一定集中在左部连续位置，倒数二层的叶子节点一定集中在右边连续位置：**如果其右子树的最大层次为l，那么其左子树的最大层次为l或者l+1**
 *  如果节点度为1，则该节点只有左孩子，即不存在只有右子树的情况。
 *  同样节点数的二叉树，完全二叉树的深度最小

### 完全二叉树的其他性质： ###

（1）**具有n个节点的完全二叉树的深度为 \[ l o g 2 n \] + 1 \[log2n\] +1 \[log2n\]\+1** ，其中\[log2n\]表示log2n的整数部分

* 证明： 假设当前二叉树的深度为k，则 2 ( k − 1 ) − 1 < n < 2 ( k ) − 1 2^\{(k-1)\}-1<n<2^\{(k)\}-1 2(k−1)−1<n<2(k)−1 —> 2 ( k − 1 ) < = n < 2 ( k ) − 1 2^\{(k-1)\}<=n<2^\{(k)\}-1 2(k−1)<=n<2(k)−1
 
 * 2 ( k − 1 ) < = n 2^\{(k-1)\} <= n 2(k−1)<=n的意思是对于完全二叉树倒数第二层一定是满的
 * n < 2 ( k ) − 1 n< 2 ^ \{(k)\} - 1 n<2(k)−1的意思是对于完全二叉树倒数第一层一定是不满的
 * 取对数得： k − 1 < = l o g 2 n < k k-1<=log\_2n<k k−1<=log2n<k，因为 k = l o g 2 n + 1 k=log\_2n+1 k=log2n\+1

（2）**如果对一棵有n个节点的完全二叉树**的节点按层序编号\[从第1层到第 L o g 2 n + 1 Log\_2n+1 Log2n\+1层，每层从左到右\]，对任一节点i(1 <= i <= n)有：

*  如果i=1，则节点是二叉树的根，没有双亲；如果i>1，那么双亲是节点\*\*\[i/2\]\*\*
    
     *  所以对于节点n，它的双亲节点是 \[i/2\]
 *  如果当前节点编号为i，则左孩子left = i \* 2 + 1，右孩子 right = index \* 2 + 2
 *  序数 >= floor(N/2)都是叶子节点

**如果对一棵有n个节点的完全二叉树的节点按层序编号**

<table> 
 <thead> 
 <tr> 
 <th>性质</th> 
 <th>满二叉树</th> 
 <th>完全二叉树</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>高度</td> 
 <td>k</td> 
 <td>k</td> 
 </tr> 
 <tr> 
 <td>第i层节点数</td> 
 <td> 2 ( i − 1 ) 2^{(i-1)} 2(i−1)</td> 
 <td> 1 &lt; = x &lt; 2 ( i − 1 ) 1 &lt;= x &lt; 2^{(i-1)} 1&lt;=x&lt;2(i−1)</td> 
 </tr> 
 <tr> 
 <td>总节点数</td> 
 <td> 2 ( k ) − 1 2^{(k)} - 1 2(k)−1</td> 
 <td> 2 ( k − 1 ) &lt; = n &lt; 2 ( k ) − 1 2^{(k-1)} &lt;= n&lt; 2 ^ {(k)} - 1 2(k−1)&lt;=n&lt;2(k)−1</td> 
 </tr> 
 </tbody> 
</table>

# 二叉树的性质 #

## 性质1 ##

**在二叉树的第 i 层上至多有 2^(i - 1) 个结点 ( i > 1 )。**

证明：

第一层是根结点，只有一个，所以 2^(1 - 1) = 2^0 = 1。  
第二层有两个，2^(2 -1) = 2^1 = 2。  
第三层有四个，2^(3 -1) = 2^2 = 4。  
第四层有八个，2^(4 -1) = 2^3 = 8。  
通过数据归纳法的论证，可以很容易得出在二叉树的第 i 层上至多有 2^(i-1) 个结点 (i >= 1 ) 的结论。

## 性质2 ##

**深度为 k 的二叉树至多有 2^k - 1 个结点 (k >= 1 )**

证明1：

如果有一层，至多 1 = 2^1 - 1 个结点。  
如果有二层，至多 1+ 2 = 3 =2^2 - 1 个结点。  
如果有三层，至多 1 + 2 + 4 = 7 = 2^3 - 1 个结点。  
如果有四层， 至多 1 + 2 + 4 + 8 = 15 = 2^4 - 1 个结点。  
通过数据归纳法的论证，可以得出，如果有 k 层，此二叉树至多有 2^k - 1 个结点。

证明2：

有性质一推出，深度为k的二叉树最多节点 =  2 0 + 2 1 + 2 2 + . . . + 2 ( k − 1 ) = 2 k − 1 2^0+2^1+2^2+...+2^(k-1)=2^k-1 20\+21\+22\+...\+2(k−1)=2k−1

## 性质3 ##

**在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1**

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=“0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此，得到等式一。  
(等式一) n=n0+n1+n2  
　 另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。  
(等式二) n=n1+2n2+1  
由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！

[N]: https://blog.csdn.net/zhizhengguan/article/details/109231393
[2020102221464544.png_pic_center]: /images/20230312/e0321c4a7f3442ce861ce87e3ebf5b17.png
[20201022214923101.png_pic_center]: /images/20230312/45ef60527e4c4e2b99235f897649a877.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230312/5e9aedf92e25481abd6c4a5facd59fe0.png