二叉树全分析（超详细总结建议收藏）

淡淡的烟草味﹌ 2024-04-11 13:24 100阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️数据结构与算法】][Link 2]  
> 学习名言：在寻求真理的长河中，唯有学习，不断地学习，勤奋地学习，有创造性地学习，才能越重山跨峻岭。——华罗庚

--------------------

## 系列文章目录 ##

第一章 ❤️ [学前知识][Link 3]  
第二章 ❤️ [单向链表][Link 4]  
第三章 ❤️ [递归][Link 5]  
…

--------------------

#### 文章目录 ####

*  系列文章目录
 *  前言
 *  二叉树
 *  相关概念
 *  二叉树的性质
 *  二叉树的五种基本形态
 *   *  空二叉树
     *  只有一个根节点的二叉树
     *  只有根节点和左子树TL的二叉树
     *  只有根节点和右子树TR的二叉树
     *  完全二叉树
 *  特殊的二叉树
 *   *  满二叉树
     *  斜二叉树
 *  小结

--------------------

## 前言 ##

## 二叉树 ##

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

> 二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。  
> 二叉树的递归定义为：**二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。**  
> 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

![二叉树][d6b506d625a241ef9e28b1e34669d98a.png_pic_center]

## 相关概念 ##

> 节点：包含一个数据元素及若干指向子树分支的信息。  
> 节点的度：一个节点拥有子树的数目称为节点的度。  
> 叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。  
> 分支节点：也称为非终端节点，度不为零的节点称为非终端节点。  
> 树的度：树中所有节点的度的最大值。  
> 节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。  
> 树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。  
> 有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。  
> 无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。  
> 森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树  
> 由原来根节点的各棵子树构成。

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

![二叉树][05693d3eff4547ea8405cef7445e771c.jpeg_pic_center]

## 二叉树的性质 ##

> 1:二叉树的第i层上至多有2i-1（i≥1）个节点 。  
> 2：深度为h的二叉树中至多含有2h-1个节点 。  
> 3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。  
> 4：具有n个节点的满二叉树深为log2n+1。  
> 5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点:  
> **当i=1时，该节点为根，它无双亲节点。  
> 当i>1时，该节点的双亲节点的编号为i/2。  
> 若2i≤n，则有编号为2i的左节点，否则没有左节点。  
> 若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点**

## 二叉树的五种基本形态 ##

*我们知道二又树是有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。*

### 空二叉树 ###

当集合为空时，称该二又树为空二又树（顾名思义它什么都没有???）  
![在这里插入图片描述][315bc30bcd784291b861f1ddcca0a7e6.gif_pic_center]

### 只有一个根节点的二叉树 ###

显然它只有一个根结点  
![在这里插入图片描述][b96874dc603e485a803207eca8d6b4ad.gif_pic_center]  
*没有任何结点的树才是空二叉树*

### 只有根节点和左子树TL的二叉树 ###

每个有孩子的结点都只有左孩子结点的二叉树  
![在这里插入图片描述][00357f45b3c4480c8d7ab63083dd9cc6.gif_pic_center]

### 只有根节点和右子树TR的二叉树 ###

每个有孩子的结点都只有右孩子结点的二叉树

![在这里插入图片描述][9c8f7a20b5b249d39100fae707fb28bb.gif_pic_center]

### 完全二叉树 ###

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。  
![在这里插入图片描述][91c06dc5612641f491cc6ce4826e49d8.png_pic_center]

> 叶子结点只能出现在最下层和次下层。  
> 最下层的叶子结点集中在树的左部。  
> 倒数第二层若存在叶子结点，一定在右部连续位置。  
> 如果结点度为1，则该结点只有左孩子，即没有右子树。  
> 同样结点数目的二叉树，完全二叉树深度最小。

![在这里插入图片描述][8519b443fb20471dae77188a9ee01100.jpeg_pic_center]

## 特殊的二叉树 ##

在二叉树的这个大家族中肯定存在一些特殊的例子，它们有着二叉树的性质，却又与众不同。

### 满二叉树 ###

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)  
*满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。*

> 有意思的是在国外教材中关于满二叉树的定义是这样的：a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树）

![在这里插入图片描述][00c778637002460589604f3f3860a2a8.jpeg_pic_center]

> 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。  
> 非叶子结点的度一定是2。  
> 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

### 斜二叉树 ###

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树  
![在这里插入图片描述][6e6e1ccf3336497b854915e7715af88b.jpeg_pic_center]

> 度为1；  
> 只有左子节点或右子节点；

## 小结 ##

好了关于二叉树的基本知识就讲到这了，关于二叉树的更多内容未来我会持续更新，希望这篇文章对你有帮助，下次见  
![在这里插入图片描述][2eed442fd9cb4acb847309f633d4bc14.gif_pic_center]  
（部分文字与图片来源于网络，侵权请联系删除）

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12226568.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129270463
[Link 5]: https://blog.csdn.net/weixin_73602725/article/details/129450203
[d6b506d625a241ef9e28b1e34669d98a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/24e60db25ccb4596ad09703a4fd81e9e.png
[b54c04a71e5c4f54a2c4532ecf648a4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9833f8d8b2984587b1c42053dfeb0c89.png
[05693d3eff4547ea8405cef7445e771c.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/598edf3c78cf4848a5ab891e34e88c14.jpeg
[315bc30bcd784291b861f1ddcca0a7e6.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/0c0dd568a94a45aaa05b948f631eaaf3.gif
[b96874dc603e485a803207eca8d6b4ad.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/b4673912dd1a482a8139ec7af7fff061.gif
[00357f45b3c4480c8d7ab63083dd9cc6.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/945fb1a013684814bae924d87ff9c721.gif
[9c8f7a20b5b249d39100fae707fb28bb.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/c9ec40cdbe5e450f8a93248c9beaf688.gif
[91c06dc5612641f491cc6ce4826e49d8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/182005e19f3c4a76997e33f1bb090996.png
[8519b443fb20471dae77188a9ee01100.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ac1f42c44d8644c38680a2488729929f.jpeg
[00c778637002460589604f3f3860a2a8.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/7f31147471474d8ab19aa1b840d432cf.jpeg
[6e6e1ccf3336497b854915e7715af88b.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f59a32e1dc074e0f883ab80bd317b0cd.jpeg
[2eed442fd9cb4acb847309f633d4bc14.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/fe124f69db074800aed6dcdfe83a3284.gif