Java集合核心内容之二叉树，大厂越来越注重基础了，建议收藏

小灰灰 2022-10-06 15:57 55阅读 0赞

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

数组查询的效率很高但是添加和删除的效率会很低，链表的添加和删除的效率很高但是查询的效率又很低，这时有没有更好的选择方案呢？这时二叉树出现了。

# 二叉树 #

## 1 相关概念 ##

**二叉树**：每个子节点只有两个节点的树，每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 1]  
**二叉查找树**也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质：

1.  任意节点左子树不为空,则左子树的值均小于根节点的值
2.  任意节点右子树不为空,则右子树的值均大于于根节点的值
3.  任意节点的左右子树也分别是二叉查找树
4.  没有键值相等的节点

二叉树又分为：完美二叉树，完全二叉树，完满二叉树

完美二叉树：又称为**满二叉树**，除了叶子节点之外的每一个节点都有两个孩子节点，每层都被完全填充![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 2]  
完全二叉树:除了最后一层之外的其他每一层都被完全填充，并且所有的节点都保持向左对齐  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 3]

完满二叉树：除了叶子节点之外的每一个节点都有两个孩子节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 4]

## 2 遍历操作 ##

二叉树中的遍历规则有如下三种：

**中序遍历**：所谓的中序遍历就是先访问左节点，再访问根节点，最后访问右节点，即左-根-右遍历

**先序遍历**：所谓的前序遍历就是先访问根节点，再访问左节点，最后访问右节点，即根-左-右遍历(前序)

**后序遍历**：所谓的后序遍历就是先访问左节点，再访问右节点，最后访问根节点。即左-右-根遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 5]查找最小值：沿着根节点的左子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最小节点

查找最大值：沿着根节点的右子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最大节点

**查找前驱节点**：小于当前节点的最大值

**查找后继节点**：大于当前节点的最小值![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 6]

## 3 删除节点 ##

二叉树中的删除节点：本质上是找前驱节点或者后继节点来替代

*  叶子节点直接删除
 *  只有一个子节点的用子节点替代(本质上就是找的前驱节点或者后继节点，左节点就是前驱节点，右节点就是后继节点)
 *  有两个子节点的，需要找到替代节点(替代节点就是前驱节点或者后继节点)

## 4 查找局限性 ##

一个二叉查找树是由n个节点随机构成,所以，对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图

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

# AVL #

BST存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上，这样树的高度为N。基于BST存在的问题，平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树（**高度平衡树**，具备二叉搜索树的全部特性，而且左右子树高度差不超过1）和红黑树。

AVL树是如何实现平衡的呢？，具体是通过左旋或者右旋来实现的。具体如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 8]

虽然AVL可以解决二叉树所存在的问题，但是AVL树要求太过严格，左旋和右旋的开销会比较大，这时出现了红黑树，只要求黑色节点平衡即可。下篇我们介绍红黑树！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70]: /images/20221005/9342d38516134cff86fc7dee87cd959e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 1]: /images/20221005/74f3b07cb2b54bf18880e0c67ea3d859.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 2]: /images/20221005/5279aa7bacfd4485b4e57e1e1c8e8163.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 3]: /images/20221005/51d1384829b944568a5d19594201029f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 4]: /images/20221005/3084b48343c84778b46461a7b3c52a4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 5]: /images/20221005/2c0948e00807459ba3ddca9e9bf2d02f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 6]: /images/20221005/e7c184a28c38430898237042c403dcf8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 7]: /images/20221005/4eda358778a74035bd48c58329f307e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTI2NTcz_size_16_color_FFFFFF_t_70 8]: /images/20221005/f534721338774cd6af06f892d74a8690.png