数据结构--二叉树

一时失言乱红尘 2022-04-10 10:50 455阅读 0赞

# 数据结构--二叉树 #

[文章转自：https://blog.csdn.net/zxm317122667/article/details/85017317][https_blog.csdn.net_zxm317122667_article_details_85017317]

## 二叉树 ##

通常树的结点中可以有0个或多个子结点。但是，当一棵树的结点都**最多只有2个子结点**时，我们称这种树为 ***二叉树***，这两个子结点分别被称为“左子树”(left subtree)和“右子树”(right subtree)。

非二叉树和二叉树区分如下：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZnVDYWk_size_16_color_FFFFFF_t_70][]  
一个二叉树的结点包含3个属性：

> **data** 保存当前结点的数据值  
> **leftChild** 一个指向左子结点的指针  
> **rightChild** 一个指向右子结点的指针

## 完全二叉树 ##

如果在一棵二叉树中，除了叶子结点，其余层的结点都是满的，并且最后一层的结点都是靠左排列，则此二叉树为完全二叉树。用一张对比图如下：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70][]  
上面左图中的红色结点并不是叶子结点，但是其只有一个子结点，所以左图并不是一个完全二叉树。也可以这样理解：在一棵完全二叉树中做插入操作时，必须先保证当前最低层已经完全被填满，然后再在新的一层中添加结点。

`完全二叉树`可以说是一种应用最广泛的树形结构，很多其他功能强大的树都是基于完全二叉树的基础的进行扩展形成的。基于完全二叉树的定义，我们可以得出如下几个特点：

> 叶子结点只能出现在最下一层  
> 最下层叶子结点一定集中在左部连续位置。  
> 倒数第二层，如有叶子节点，一定出现在右部连续位置。  
> 同样结点树的二叉树，完全二叉树的深度最小

## 二叉树的表示 ##

为什么 **完全二叉树** 会被单独拎出来讲呢? 为什么 **完全二叉树** 的最后一层结点需要靠左排列呢? 要理解这两个为什么之前，我们需要先了解，如何用代码去实现(或者说表示)一棵二叉树。  
想要在代码中存储一棵二叉树，基本上有两种方式：

1.  基于指针或者引用的二叉链式存储法
2.  基于数组的顺序存储法

链式存储法

直接上图：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 1][]  
将上图转化成代码，如下所示：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 2][]  
从上面的代码中可以很清楚的看出，每个结点有三个字段，其中 `data` 是结点的数据域， `left` 和 `right` 分别是指向左右子结点的指针(或引用)。我们只要拿到一个根结点，就可以通过其左右子结点的指针，把整棵树都串起来。

顺序存储法

这种存储方式是基于数组的顺序存储法，也就是用一个数组来保存整棵树的结点数据，只不过向数组中添加数据时，并不是从1, 2, 3…n的顺序依次排列数据。而是按照一定的规律，向数组填充数据。比如数组的第一个(下标i = 0)元素保存的是根结点，那根结点的左子结点应该保存在 `2 * i + 1` 的位置，同样根结点的右子结点应该被保存在 `2 * i + 2`的位置。用一张图来表示如下：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 3][]

> **因此，如果某棵二叉树是一棵完全二叉树，那用数组存储方式是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储那样，需要存储额外的左右子结点的指针。这也是完全二叉树会被单独拎出来的原因，也是为什么完全二叉树要求最后一层的子结点都靠左排列。**

**顺序存储和链式存储对比**  
上面讲了树的实现方式有两种: 链式存储和顺序存储。那么在日常开发中我们应该选择哪一种方式去实现一个树形结构呢？ 一般情况下，我们会从以下几个方面去综合的衡量两种实现方式的优缺点，并根据实际情况选择一种合适的实现方式

1.  在实现方式的  
    在实现方式上使用链式存储的方式会更加容易理解一些。毕竟链式存储的实现代码更加具体化，而用数组的方式就需要我们充分的运用一下想象力，将一个 **线性并且连续** 的内存区域想象成一个树形结构，多了一步转化的操作
2.  在运行效率上  
    因为数组本身就有`随机访问`的优势, 访问数组中任意下标的元素的时间复杂度都是`O(1)`, 同样访问顺序存储的树形结构中的结点的时间复杂度也是`O(1)`，这样的结构对于查找、排序等操作是有利的。在后续章节的 `堆排序` 中就是使用的这种方式  
    但是如果我们需要频繁的对某二叉树进行`插入`或`删除`操作，那么链式存储方式可能会更合适一些，因为我们只需要重新指定一下指针指向的地址即可实现`插入`或`删除`某一个结点操作
3.  在内存空间的利用率上  
    如果实现的是完全二叉树，建议使用数组实现树形结构。因为数组不需要创建额外的`左子结点`和`右子结点`指针对象，所以数组对内存的使用效率更高。**但是假如需要树形结构保存的数据量比较大，则需要进行一番斟酌取舍，因为数组的内存需要是连续的**。假如我们需要保存的数据大小是100，虽然系统剩余可用内存总共200M，但是并没有一块100M的连续内存，这种情况还是无法申请内存成功，进而导报错，反而链式存储因为是动态申请内存，所以就不存在这种问题

## 二叉树的遍历 ##

前面讲了二叉树的基本定义和表示方式，现在我们来看一下一个二叉树的重要操作：**二叉树的遍历**。这也是在面试中经常被问到的问题。  
所谓遍历也就是将二叉树中所有的结点数据都查找并打印出来。那如果实现这种操作呢？

基本上有4种方法：**前序遍历**、**中序遍历**、**后序遍历**，以及 **层级遍历**。

先来看下前、中、后续，分别表示的是结点与它左右子结点的顺序。

1.  前序遍历，是指对于树中的任意结点，先打印这个结点的data，然后再打印左子树，最后打印右字数
2.  中序遍历，是指对于树中的任意结点，先打印左子树，然后再打印这个结点的data，最后打印右字数
3.  后续遍历，是指对于树中的任意结点，先打印左子树，然后再打印右子树，最后打印这个结点的data

实际上，二叉树的前、中、后续遍历就是一个递归过程。用一段伪代码表示如下：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 4][]

再来看下层级遍历

his kind of traversal is also called level-order and visits all the levels of the tree starting from the root, and from left to right.

For the implementation, we’ll use a Queue to hold the nodes from each level in order. We’ll extract each node from the list, print its values, then add its children to the queue:  
顾名思义，这种遍历方式是一层一层的遍历。也就是说

1.  先打印处于第一层的根结点，
2.  再打印根结点左子结点和再右子结点。也就是第二层的数据
3.  以此类推，再打印第三层等等。。

具体过程如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZnVDYWk_size_16_color_FFFFFF_t_70 1][]  
对于代码的实现，我们可以借助于数据结构 `Queue` 的帮助。具体实现代码如下所示：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 5][]

## 内容小结 ##

二叉树是树形结构中最重要的一种结构，几乎没有之一。二叉树的每个结点最多只有两个子结点，分别是左子树和右子树。二叉树中又有一种比较特殊的树–完全二叉树。  
二叉树既可以使用链式存储，也可以使用顺序存储。要遍历一个二叉树有4中方式，分别是前、中、后续遍历和层级遍历(类似后续图算法中要讲的广度优先遍历)。

在日常开发中，我们通常不会简单的使用一棵普通的二叉树或者是二叉树遍历操作。而是在二叉树或者完全二叉树的基础上进行某些方面的功能扩展，从而达到某些特定的效果

[https_blog.csdn.net_zxm317122667_article_details_85017317]: https://blog.csdn.net/zxm317122667/article/details/85017317
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZnVDYWk_size_16_color_FFFFFF_t_70]: /images/20220331/74b08ee1f9654a1199c92239f0811c36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70]: /images/20220331/a95bb03347044742818ce1fd508c84b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 1]: /images/20220331/b4679035dc37454da4be5e1cf519a149.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 2]: /images/20220331/bd7d1f1c62a04614812b37c7e0dfa276.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 3]: /images/20220331/d48e41234d6e4a5592a336bdd1b70252.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 4]: /images/20220331/fb0a1b3d69d449b8992259b123159102.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZnVDYWk_size_16_color_FFFFFF_t_70 1]: /images/20220331/a212298b5f4745a5819e866435e8fe0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4bTMxNzEyMjY2Nw_size_16_color_FFFFFF_t_70 5]: /images/20220331/954b1a1e2b5e4b7fbd7957b13e7b7844.png