“树”和“二叉树”的基本定义和性质

- 日理万妓 2022-11-03 05:43 201阅读 0赞

### 文章目录 ###

*  一、树
 *   *  1.1 树的概念
     *  1.2 基本术语
     *  1.3 树的性质
 *  二、二叉树
 *   *  2.1 二叉树的定义
     *  2.2 满二叉树
     *  2.3 完全二叉树
     *  2.4 二叉排序树
     *  2.5 平衡二叉树
     *  2.6 二叉树的性质
 *  本文参考资料

![在这里插入图片描述][20210227172444595.png]

# 一、树 #

## 1.1 树的概念 ##

树是一种逻辑结构。

树是n(n≥0)个结点的有限集合，n=0是，称为空树。  
而任意的非空树应满足：

*  有且仅有一个特定的称为根的结点。
 *  当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根节点的子树。

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

## 1.2 基本术语 ##

部分加粗字体非任何专业术语，不具任何实际意义，会心一笑。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]

**哄堂大孝：**

*  祖先结点和子孙结点——K是ABE的子孙结点，ABE是K的祖先结点。
 *  双亲结点和孩子结点——E是K的双亲结点，K是E的孩子结点
 *  兄弟结点——K、L有共同的双亲结点，称之为兄弟结点

**谁儿子多：**

*  度——数的一个结点的子结点的个数成为该结点的度，B有两个子结点，所以B的度为2
 *  树的度——树中最大度数称为树的度

**枝繁叶茂：**

*  分支结点——度大于0的结点称为分支结点，ABCDE
 *  叶子节点——度为0的结点称之为叶子结点，其余的结点均为叶子结点

**代代相传：**

*  结点层次——A为第一层，B为第二层
 *  结点高度——B的高度为3，从叶子结点数起，经历了K-E-B所以高度为3
 *  结点深度——深度与高度相反，从根节点开始，自顶向下逐层累加，B的深度为2
 *  树的高度（深度）——就是树中结点的最大层数，因为最大高度和最大深度是相等的

**争皇位：**

*  有序树和无序树——例如下图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 2]  
    B、D的位置调换了，
    
     *  如果整个树为无序树，那么这两棵树完全相同，
     *  如果整个树是有序树，这两个树是不同的。

**找儿子/找祖宗：**

*  路径——树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。例如A结点到E结点的路径为“A-B-E”。
    
    > 注意：  
    > 1.路径是不包含边的，正如定义，是结点序列构成的。  
    > 2.树的分支是有向的，即从双亲结点指向孩子结点，所以路径一定是自上而下的。所以从E永远无法到达F结点，它们之间不存在路径。
 *  路径长度——路径长度指的是路径上所经历的边的个数。比如A-E的路径，路径长度为2。

**祖宗死了——分家：**

*  森林——m（m≥0）棵互不相交的树的集合。例如：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 3]
    
    > m可以为0，即为空森林。

## 1.3 树的性质 ##

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

1.  树中的结点数等于所有结点的度数加1。
2.  度为m的树中第i层上至多有mi-1个结点（i≥1）。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 5]
3.  高度为h的m叉树至多有(mh\-1)/(m-1)个结点。
    
    > 对第2条的公式进行应用，将上面图中每一层的节点数进行相加，等比数列求和，可得出结论。
4.  具有n个结点的m叉树的最小高度为  
    ![在这里插入图片描述][20210227091455935.png]  
    我们令第三条性质的式子 = n，即(mh\-1)/(m-1)=n
    
    即可得结论。
    
    > 取上界的原因在于我们在第三条的公式中假设每一层的节点数都达到最大，而在第四条中我们只假设除了最后一层的其余层数的结点数达到最大，取上界来消除这个偏差。  
    > 例如：  
    > ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 6]  
    > 结点数为11，度为3，计算 ![在这里插入图片描述][20210227091644935.png]  
    > 结果大约为2.X，取上界结果为3。

# 二、二叉树 #

## 2.1 二叉树的定义 ##

二叉树是树的一种。也是一种逻辑结构。

二叉树是n（n≥0）个结点的有限集合。

1.  n=0时，二叉树为空；
2.  n>0时，由根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树也分别是一棵二叉树。

![在这里插入图片描述][20210227091806929.png]

> 二叉树是有序树。

**二叉树 五种基本形态：**

空树、只有根结点、根结点和左子树、根结点和右子树，根节点同时拥有左子树和右子树。

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

问题：三个结点的二叉树有多少种？

答案：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 8]  
二叉树和度为2的有序树做对比：

<table> 
 <thead> 
  <tr> 
   <th align="center">二叉树</th> 
   <th align="center">度为2有序树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">可以为空</td> 
   <td align="center">至少有三个结点</td> 
  </tr> 
  <tr> 
   <td align="center">孩子结点始终有左右之分</td> 
   <td align="center">孩子结点次序是相对的</td> 
  </tr> 
 </tbody> 
</table>

## 2.2 满二叉树 ##

**满二叉树：** 一棵高度为h，且含有2h\-1个结点的二叉树为满二叉树。

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

我们回忆一下前面讲过的：

> 高度为h的m叉树至多有(mh\-1)/(m-1)个结点。

通俗来讲，满二叉树就是每一层都达到了最大结点数的二叉树。

我们对满二叉树进行自顶向下，自左向右的编号排序：

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

我们观察可以得出结论，

*  结点`i`的左孩子结点编号为`2i`，右孩子结点的编号为`2i+1`。
    
    > 例如：
    > 
    > 编号为2的结点的左孩子结点编号为4，编号为6结点的左孩子结点编号为12；
    > 
    > 编号为2的结点的右孩子结点编号为5，编号为6结点的右孩子结点编号为13。
 *  对于编号为i的节点，若存在，则其双亲的编号为  
    ![在这里插入图片描述][20210227092009911.png]
    
    > 例如：  
    > 结点10的双亲结点为`10/2` = `5`；  
    > 结点11的双亲结点为`11/2=5.5 取下界` = `5`。

## 2.3 完全二叉树 ##

**完全二叉树：** 设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 11]  
通俗来说，就是一棵二叉树，从上往下，从左往右放结点，中间不能有空缺。

**完全二叉树的几种性质：**

1.  若 i ≤⌊ n / 2⌋，则结点 i 为分支结点，否则则为叶子结点。
2.  叶子结点只可能出现在层次最大的两层上出现。对于最大层次的叶子结点，都依次排在最左边的位置上。
3.  度为1的结点若存在，则只可能有一个，且是编号最大的分支结点，并且孩子结点一定是左结点。例如上图中，只有6结点度为1，且是最大的分支结点，并且它的孩子结点为12，是它的左结点。

## 2.4 二叉排序树 ##

**二叉排序树** 一棵二叉树，若树非空则具有如下性质：  
对于任意结点存在左子树或右子树，则其左子树上所有的结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点。  
![在这里插入图片描述][20210227110304610.png]  
如上图所示，上图中的数字代表的是结点的值，而非序号。  
例如：4所在的结点，其左子树上所有的结点值均小于4，右子树上所有的结点均大于4。

## 2.5 平衡二叉树 ##

**平衡二叉树** 树上任意结点的左子树和右子树的深度只差不超过1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 12]  
我们可以观察一下，上图中的任意结点的左子树和右子树的深度差都不超过1。

> 特别注意的是，平衡二叉树的要求是任意结点的左子树和右子树的深度差都不能超过1。是任意结点！  
> 例如：  
> ![在这里插入图片描述][20210227111411329.png]  
> 该树就不符合要求。

## 2.6 二叉树的性质 ##

① 非空二叉树上的叶子结点数等于度为2的结点数加1，即n0= n2\+1  
( ni 代表度为 i 的结点个数)  
![在这里插入图片描述][20210227112123899.png]

> 我们来简单推导一下：  
> 对于一棵二叉树：
> 
>  *  n = n0 \+ n1 \+ n2  
>     这个很好理解，二叉树的度只有三种情况——0、1、2。所以总结点的个数就是三种情况加起来。
>  *  n = n1 \+ 2n2 \+ 1  
>     这个公式看起来很晦涩，其实也非常好理解。我们用度来表示每个结点的孩子结点，我们可以计算一下孩子结点的个数：  
>     度为0的孩子节点数为0 \* n0；  
>     度为1的孩子节点数为1 \* n1；  
>     度为2的孩子节点数为2 \* n2；  
>     又因为根节点不是任何结点的孩子结点，所以最后再加上1，即可得到以上公式。
> 
> 1.  将上面两个式子整理，就可得到n0= n2\+1

② 非空二叉树上第k层上至多有2k-1个结点（k≥1）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 13]

③ 高度为h的二叉树至多有2h-1个结点(h≥1)

④ 对完全二叉树按从上到下、从左到右的顺序依次编号1,2,…,n，则有以下关系:

*  当 i > 1 时，结点 i 的双亲结点标号为 ⌊ i ∕ 2 ⌋。即当 i 为偶数时，其双亲结点的编号为 i / 2 ，它是双亲结点的左孩子；当 i 为奇数时，其双亲结点的编号为( i - 1 ) / 2，它是双亲结点的右孩子。
 *  当 2i ≤ n 时，结点 i 的左孩子编号为2i，否则无左孩子。
 *  当 2i + 1 ≤ n 时，结点 i 的右孩子编号为 2i + 1，否则无右孩子。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 14]
 *  结点i所在的层次为 ⌊ log 2 i ⁡⌋ + 1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 15]  
    ⑤ 具有n个(n＞0)结点的完全二叉树的高度为  
    ![在这里插入图片描述][20210227171609772.png]

![在这里插入图片描述][20210227172433819.png]

# 本文参考资料 #

文章内容全部是学习笔记。  
来自视频：[https://www.bilibili.com/video/BV1b7411N798][https_www.bilibili.com_video_BV1b7411N798]  
本文中所有示意图（除部分公式）均源自视频截图。

[20210227172444595.png]: /images/20221024/c6a214c7e2c44b3b949d2ddff1bd93b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20221024/3c9d624ba82d432c88dc5a8f0aae89c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]: /images/20221024/d2b2978418f7402898cc8167f548442d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 2]: /images/20221024/e885ddbf75054f1d9d48322e71425e8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 3]: /images/20221024/40100c076b254ab4b01318e51d2ef788.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 4]: /images/20221024/acaf8cb3df8b49998753b7e979cb0006.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 5]: /images/20221024/488ad0fe2b0644ecb567ec20b035448e.png
[20210227091455935.png]: /images/20221024/c31fd1755edb47e0b2c1078c2f51be4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 6]: /images/20221024/4f8e43ff755c488ca3cd775e10f69221.png
[20210227091644935.png]: /images/20221024/ac96ed5c4ce542c5a5278145c2ead79e.png
[20210227091806929.png]: /images/20221024/7b65137cb4484043a7028a6e6eabb719.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 7]: /images/20221024/47a27ae0e90a4c5fab792d558f1e05fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 8]: /images/20221024/9031f6bd289440adaf51773ed0b70016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 9]: /images/20221024/f45423d46dca4ec0ab6b41325b36e333.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 10]: /images/20221024/42a69c928c934539a4f2205f3757dd10.png
[20210227092009911.png]: /images/20221024/f9f24f88b9ee442f9ba6dc594a0f6fbf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 11]: /images/20221024/ee96149f3c5a450eb65761ccae264ca3.png
[20210227110304610.png]: /images/20221024/7bb979f222e8455e9b0190253e6663e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 12]: /images/20221024/077646bc3892412fb389a5c3320c3a5d.png
[20210227111411329.png]: /images/20221024/ea556cf1f86040de9b926d47c00fa695.png
[20210227112123899.png]: /images/20221024/aa80c19558a44e83ac1605e883a4b61d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 13]: /images/20221024/6732e492fd374cafade44e28b545b9c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 14]: /images/20221024/5ab4db5a3dda41eeb4fb87172160ac81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 15]: /images/20221024/0358dafdda5c4f1e8c8d0d3101c6cde0.png
[20210227171609772.png]: /images/20221024/29aec25d7e554b5686b9b045a6b2d6e6.png
[20210227172433819.png]: /images/20221024/14e805d1f90641cc9fecb672d2f32020.png
[https_www.bilibili.com_video_BV1b7411N798]: https://www.bilibili.com/video/BV1b7411N798