：查找二叉树又叫二叉排序树

也称为二叉排序树

属性：左儿子的值 < 父节点的值 < 右儿子的值

因此，不可能有两个节点具有相同的值

功能（含义）：大大提高查询数据的效率。 （相当于二分查找的效率）

插入节点：如果存在key值相同的节点，则不会插入。 如果搜索二叉树为空，则直接将其作为根节点。 与父节点比较（首先是根节点）。 小于父节点，则将该节点插入到左子树中。 大于父节点，将该节点插入到右子树中。 删除节点：如果是叶子节点，则直接删除。 如果只有一个子节点，则让该子节点代替它。 如果有两个子节点，则在该节点的左子树上找到键值最大的节点S，将该节点的值改为节点S的值，然后删除节点S。（相当于找到更小的节点比它并替换它的位置）

最优二叉树（哈夫曼树）

是一个工具人工具树

用于霍夫曼编码

霍夫曼编码：一种压缩编码方法，缩短原始信息的编码长度以节省存储空间和传输带宽。 常用于多媒体压缩，属于无损压缩。

基本概念

叶子节点有实际意义！ ！ ！ 非叶子节点是构建树时的工具（工具制造者的工具）

构造哈夫曼树的目的是最小化树的带权路径长度。

建树过程：

这个过程相当于经典的合并石头问题。

例如：

有一组权重为 {5, 29, 7, 8, 14, 23, 3, 11} 的节点

while(结点数量大于一){ 
              选出最小的俩个结点（包括以他们为根结点的树）
              合并到一个新的父结点上，新的结点的值为他们俩的值之和 
}

过程

现在有节点：{5,29,7,8,14,23,3,11}

1、首先选择5和3，合并成一个新节点为8。现在有节点：{5,8,29,7,8,14,23,3,11}

2.然后选择8和7，合并成一个新节点15。（当有多个相同值的节点时，可以选择任意一个，这意味着哈夫曼树不是唯一的）现在有节点：{ 8 , 29 ,7,15,8,14,23,11}

3. 再次选择8和11，将它们合并为新节点19。现在有节点：{29, 15, 8, 14, 23, 11, 19}

4. 再次选择15和14，将它们合并为新节点29。现在有节点：{29, 15, 14, 29, 23, 19}

5. 再次选择23和19，合并为新节点42。现在有节点：{29, 29, 23, 19, 42}

6. 再次选择29和29，将它们合并为新节点58。现在有节点：{29,29,58,42}

7. 再次选择58和42，合并为新节点100。现在有节点：{58, 42, 100}

该树的加权路径长度为：

55+35+74+143+83+113+292+232

线索二叉树

概念：在原来的二叉树上，混杂着虚线箭头。

为什么二叉树有线索：

我们都知道，在二叉树中，每个节点需要三个空格，一个指向左节点的指针，一个指向右节点的指针，以及它自己的值。

但！ 在二叉树中，叶子节点和只有一个儿子的父节点总是会浪费空间。

线索二叉树使用了这个浪费的空间。

用它做什么？ 使用方便，遍历速度加快。

具体实现线索二叉树分为：前序线索二叉树、中序线索二叉树、后序线索二叉树。

前序线索二叉树：空闲左指针指向前序遍历中的前一个节点，空闲右指针指向前序遍历中的下一个节点。

中序线索二叉树：空闲的左指针指向中序遍历的前一个节点，空闲的右指针指向中序遍历的下一个节点。

后序线索二叉树：空闲左指针指向中序遍历的前一个节点，空闲右指针指向中序遍历的下一个节点。

平衡二叉树

概念介绍：在排序二叉树（搜索二叉树）中，我们发现在同一个序列中，不同结构的排序二叉树的搜索效率是不同的。

并且排序二叉树越平衡，其搜索效率就越高。 平衡：任意节点左右子树的深度差越小，排序二叉树越平衡。

例如：图1和图2的顺序相同，但由于图1比图2更加平衡，因此图1的搜索效率高于图2。

图1

图2

和！ 平衡二叉树是同一序列中非常平衡的二叉树。

定义：

深度：有多少代子孙，就有多少深度。 叶子节点深度为0。平衡：