数据结构总结---------非线性表（二叉树）

- 日理万妓 2022-03-15 05:30 167阅读 0赞

### 数据结构总结---------非线性表（二叉树） ###

*  1.二叉树
 *   *  1.1 二叉树的遍历
     *  1.2 存储结构
     *   *  1.顺序存储结构（数组）实现二叉树
         *  2.链表实现二叉树
     *  1.3常见的平衡二叉树
     *   *  1.AVL数（平衡二叉树）
         *  2.红黑树

# 1.二叉树 #

1.  为什么存在二叉树？  
    二叉树的顺序结构可以解决链表的查询慢的问题，因为解决了查询慢的问题所以相对的更改数据也变的快了

## 1.1 二叉树的遍历 ##

![在这里插入图片描述][20190302001729617.png]  
**如何理解？**  
可以理解为递归进行遍历的！！！

**举个例子**：  
![在这里插入图片描述][20190302001856925.png]  
先序遍历：1452367  
中序遍历：4513267  
后续遍历：5437621

## 1.2 存储结构 ##

### 1.顺序存储结构（数组）实现二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]  
注：从上往下从左往右依次填入数组中  
**问题：**  
当我们二叉树只存1，3，7数据的时候  
![在这里插入图片描述][20190301235829798.png]  
存在空间浪费现象

### 2.链表实现二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]  
**问题**：当我们存储1，3，7数据的时候  
![在这里插入图片描述][20190302000211235.png]  
成了链表结构，从而为了解决这个问题，出现了平衡二叉树！

## 1.3常见的平衡二叉树 ##

### 1.AVL数（平衡二叉树） ###

**定义**：

*  它是一棵空树或它的左右两个子树的高度差（平衡因子）的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
    
     *  平衡因子（平衡度）：结点的平衡因子是结点的左子树的高度减去右子树的高度
     *  平衡二叉树：每个结点的平衡因子都为1、-1、0的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树

**如何实现的平衡？**  
通过减少二叉查找树层次，使层次达到平衡。来实现平衡二叉树

### 2.红黑树 ###

**定义**：

*  每个结点是黑色或者是红色
 *  根节点是黑色
 *  每个叶子节点(NIL)是黑色.\[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]
 *  如果一个节点是红色的，则它的子节点必须是黑色的
 *  从一个节点到该节点的子孙节点所有路径上包含相同数目的黑节点

**图解**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2]  
注：红黑数的应用比较广泛（如java集合中的TreeSet和TreeMap，Linux虚拟机内存的管理等），主要是用它来存储有序的数据，他的时间复杂度是O(logN),效率非常之高。他虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：他可以在O(log n)时间内做查询，插入，和删除，这里的n是树中元素的数目。

https://me.csdn.net/qq\_39657909

[20190302001729617.png]: /images/20220315/bd51943cedd04c1cb48c696d04641970.png
[20190302001856925.png]: /images/20220315/93409c128d5a47259b556f82fa824543.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]: /images/20220315/62902707ec274a87a5fae319ef0b3fe3.png
[20190301235829798.png]: /images/20220315/87e523ebd8c24ac19f70ce320c6f237b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]: /images/20220315/a0f595e949564b3e88c04e1112e01599.png
[20190302000211235.png]: /images/20220315/bec934c108ab43d0bfa4461a9f49f910.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2]: /images/20220315/43f975d7db424b41a71649c25abfd573.png