Java 二叉树

ゝ一纸荒年。 2024-03-27 17:07 46阅读 0赞

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

### 数据结构（二叉树） ###

*  节点：父节点地址值 值 左子节点地址值 右子节点地址值
 *  度：每一个节点的子节点数量
 *  树高：树的总层数
 *  根节点：最顶层的节点
 *  左子节点：左下方的节点
 *  右子节点：右下方的节点
 *  根节点的左子树：根节点左边的树
 *  根节点的右子树：根节点右边的树  
    数据没有规律，难以查询

### 二叉查找树（二叉排序树、二叉搜索树） ###

特点：
    	每一个节点个最多有两个子节点
    	任意节点左子树上的值，都小于当前节点
    	任意右子树上的值，都大于当前节点
    弊端
    	左右子树高度差过大（长短腿问题）

#### 添加节点 ####

规则：大的存左边，小的存右边，一样的不存

### 二叉树的遍历方式 ###

#### 前序遍历 ####

从根节点开始：根左右

#### 中序遍历 ####

从最左边的节点开始：左中右

#### 后序遍历 ####

从最左边的节点开始：左右中

#### 层序遍历 ####

从根节点开始，一层层的遍历

### 平衡二叉树 ###

规则：任意节点左右子树高度差不超过一1

#### 旋转机制 ####

##### 规则一：左旋 #####

**确定支点**：从添加的节点开始，不断的往父节点找不平衡的节点

1.  以不平衡的的点作为支点
2.  把支点左旋降级，变成左子节点
3.  晋升原来的右子节点  
    ![在这里插入图片描述][e5f83055efee4cf4adb7ea986f3151fc.png]![在这里插入图片描述][93e6d8f56d534ff8b955d860a0a8cd8b.png]

*  复杂的
    
     *  左旋的时候，原本的左子节点让出自己的位置，左旋结束后，作为已经降级节点的右子节点  
        ![在这里插入图片描述][44aa8bd90eca489286c86c600807a802.png]  
        ![在这里插入图片描述][be7dd68acf26407287805393070a0bea.png]

#### 规则二：右旋 ####

1.  以不平衡的的点作为支点
2.  把支点右旋降级，变成右子节点
3.  晋升原来的左子节点

#### 需要旋转的四种情况 ####

##### 左左：当根节点的左子树的左子树有节点插入，导致二叉树不平衡 #####

*  一次右旋

##### 左右：当根节点的左子树的右子树有节点插入，导致二叉树不平衡 #####

*  先进行局部左旋（不平衡支点的左子树），再进行整体右旋

##### 右右：当根节点的右子树的右子树有节点插入，导致二叉树不平衡 #####

*  一次左旋

##### 右左：当根节点的右子树的左子树有节点插入，导致二叉树不平衡 #####

*  先进行局部右旋（不平衡支点的右子树），再进行整体左旋

### 红黑树 ###

*  红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
 *  1972年出现，当时被称为平衡二叉B树。后来，78年被修改为：红黑树
 *  它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位，表示结点的颜色
 *  **每一个节点，可以是红或者黑**
 *  红黑树**不是高度平衡的**，他的平衡是通过“**红黑规则**”进行实现的

#### 红黑规则 ####

1. 每一个节点是红色的，或者黑色的
    2. 根节点必须是黑色
    3. 如果一个节点没有子节点或者父节点，则该节点对应指针的属性值为Nil ，这些Nil视为叶节点，每个叶节点（Nil）是黑色的
    4. 如果某一个节点是红色，那么他的子节点必须是黑色（不能出现两个红色节点相连的情况）
    5. 对每一个节点，从该节点到其所有的后代叶节点Nil 的简单路径上，均包含相同数目的黑色节点

![在这里插入图片描述][39792225b43c45069d1f5f7e56dd4680.png]  
![在这里插入图片描述][bcffb2cd273f483daa96adb3ec5b8d71.png]

#### 红黑树添加节点 ####

*  默认颜色：添加节点默认是红色的 ，效率高  
    ![97ded905b2cb4a6db3bad37059e5beff.png][]

[f9c78ec26278487e9b87f3e537553d5d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/38570b819d8840a58d1f89cec4681d18.png
[e5f83055efee4cf4adb7ea986f3151fc.png]: https://img-blog.csdnimg.cn/e5f83055efee4cf4adb7ea986f3151fc.png
[93e6d8f56d534ff8b955d860a0a8cd8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e955271ae969403eb8e345b965b69c2d.png
[44aa8bd90eca489286c86c600807a802.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/08c4c7f12384447d89efe6cec85e7db0.png
[be7dd68acf26407287805393070a0bea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5d0d13cd65cc4cd285d65a689fd324b1.png
[39792225b43c45069d1f5f7e56dd4680.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e67d1681374b4d8abd6c132979167124.png
[bcffb2cd273f483daa96adb3ec5b8d71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2bf871eede9842fbbd229da9daad856f.png
[97ded905b2cb4a6db3bad37059e5beff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b6786b6806d94a2cb8368bcd036af044.png