【数据结构】二叉树(Binary Tree)

末蓝、 2022-12-08 04:58 204阅读 0赞

### 目录 ###

*  1 树的概念
 *   *  1.1 树的定义
     *  1.2 相关概念
 *  2 二叉树的概念
 *   *  2.1 二叉树的定义
     *  2.2 二叉树的性质
     *  2.3 特殊二叉树
     *   *  2.3.1 满二叉树
         *  2.3.2 完全二叉树
 *  3 二叉树的储存结构
 *   *  3.1 顺序储存
     *  3.2 二叉链表
 *  4 二叉树的遍历
 *   *  4.1 前序遍历 NLR
     *  4.2 中序遍历 LNR
     *  4.3 后序遍历 LRN
     *  4.4 层序遍历

# 1 树的概念 #

## 1.1 树的定义 ##

树是由根结点和若干颗子树构成的。

树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

这是一个普通的树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center]

## 1.2 相关概念 ##

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

# 2 二叉树的概念 #

## 2.1 二叉树的定义 ##

普通定义：二叉树是指树中节点的度不大于2的有序树。  
递归定义：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

## 2.2 二叉树的性质 ##

*  每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
 *  左子树和右子树是有顺序的，次序不能任意颠倒。
 *  即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

## 2.3 特殊二叉树 ##

### 2.3.1 满二叉树 ###

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

特点：

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

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

### 2.3.2 完全二叉树 ###

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

特点：

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

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

# 3 二叉树的储存结构 #

## 3.1 顺序储存 ##

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 3]  
存储在一位数组中的形式：  
![在这里插入图片描述][20200917225338722.png_pic_center]  
如果二叉树为完全二叉树，节点刚好填满数组。

当二叉树不为完全二叉树时，图中（D、H、I）为不存在的节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 4]  
起存储结构如下，∧表示数组中此位置没有存储结点。此时，存储结构存在浪费问题。  
![在这里插入图片描述][20200917225644457.png_pic_center]  
所以顺序储存结构适用于完全二叉树。

## 3.2 二叉链表 ##

既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。

由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。  
![在这里插入图片描述][20200917225953793.png_pic_center]  
如图采用一种链表结构存储二叉树，这种链表称为二叉链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 5]

# 4 二叉树的遍历 #

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。共分为4种：

*  前序遍历
 *  中序遍历
 *  后序遍历
 *  层序遍历

## 4.1 前序遍历 NLR ##

前序遍历：Preorder Traversal  
NLR：Node→Left→Right

从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 6]  
访问顺序为：  
A→B→D→H→D→I→D→B→E→J→E→B→A→C→F→C→G

遍历输出为：  
ABDHIEJCFG

## 4.2 中序遍历 LNR ##

中序遍历：Inorder Traversal  
LNR：Left→Node→Right

从二叉树的根结点出发，先访问左子树，然后访问根节点，最后访问右子树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 7]

或者说，只有当结点的子结点已经被遍历后才能遍历该结点。

访问循序为：  
A→B→D→H→D→I→D→B→E→J→E→B→A→C→F→C→G

遍历输出为：  
HDIBJEAFCG

## 4.3 后序遍历 LRN ##

后序遍历：Postorder Traversal  
LRN：Left→Right→Node

从二叉树的根结点出发，从左到右先叶子后节点的方式遍历左右子树，最后访问根节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 8]

访问循序为：

A→B→D→H→D→I→D→B→E→J→E→B→A→C→F→C→G→C→A

遍历输出为：  
HIDJEBFGCA

## 4.4 层序遍历 ##

从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问。与上面提到的顺序存储相类似。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 9]  
遍历输出：  
ABCDEFGHIJ

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

**参考**  
[https://www.jianshu.com/p/bf73c8d50dc2][https_www.jianshu.com_p_bf73c8d50dc2]  
[https://www.cnblogs.com/du001011/p/11229170.html][https_www.cnblogs.com_du001011_p_11229170.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d55afff353344f97928633ea4a42163c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/c9e657bc2b824143b04a281b6d53e8fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/92be669d6dea4b4f906d5f53d9ff0019.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/c6a8081b3a644fabab5cdeb889ec2045.png
[20200917225338722.png_pic_center]: /images/20221123/608f9aca1e754b93863042b69cc14085.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/5b6f6a134f9b4fbfbd65363c8f5db094.png
[20200917225644457.png_pic_center]: /images/20221123/3c65135a7eae47739de9d2dbaaca0f96.png
[20200917225953793.png_pic_center]: /images/20221123/ed5bd6055b1c4e1d931d0b661ad7db1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/1f73605a30f7407c8c58381c7b2acaac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/5a50face3a4342b6ab86048bf8d330c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/ac754d38342746fd8da54efa3f4d1462.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/cff49e2aad4944dfb8c8d47b19e04a3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlZV9TdGFy_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/b0d057a7b9fc47fdac0f331fd1d44153.png
[https_www.jianshu.com_p_bf73c8d50dc2]: https://www.jianshu.com/p/bf73c8d50dc2
[https_www.cnblogs.com_du001011_p_11229170.html]: https://www.cnblogs.com/du001011/p/11229170.html