树和二叉树的应用

梦里梦外; 2022-02-23 09:54 341阅读 0赞

本文主要介绍树和二叉树的应用，主要包含3个部分：**二叉排序树**、**平衡二叉树**和**哈夫曼树和哈夫曼编码**。

## 二叉排序树（BST） ##

### 定义 ###

二叉排序树（简称**BST**），也称二叉查找树。二叉排序树或者是一棵空树，或者是一棵有下列特性的非空二叉树：

1.  若**左子树非空**，则**左子树**上所有结点关键字的值均**小于根结点**的关键字值
2.  若**右子树非空**，则**右子树**上所有结点关键字的值均**大于根结点**的关键字值
3.  左、右子树本身也分别是一棵二叉排序树

### 查找 ###

关于二叉排序的查找，在[C语言实现七大查找算法（三）][C]我的这篇博文中，已经详细介绍了，此处不再赘述。

**查找效率**：平均查找长度主要取决于**树的高度**。

**二叉排序树和二分查找的对比**

<table> 
 <thead> 
 <tr> 
 <th align="center"></th> 
 <th align="center">二叉排序树</th> 
 <th align="center">二分查找（有序顺序表）</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">判定树</td> 
 <td align="center">不唯一</td> 
 <td align="center">唯一</td> 
 </tr> 
 <tr> 
 <td align="center">有序性</td> 
 <td align="center">无需移动结点，修改指针</td> 
 <td align="center"></td> 
 </tr> 
 <tr> 
 <td align="center">插入、删除</td> 
 <td align="center"> O ( l o g 2 n ) O(log_2^n) O(log2n)</td> 
 <td align="center"> O ( n ) O(n) O(n)</td> 
 </tr> 
 <tr> 
 <td align="center">有序表静态</td> 
 <td align="center"></td> 
 <td align="center">√</td> 
 </tr> 
 <tr> 
 <td align="center">有序表动态</td> 
 <td align="center">√</td> 
 <td align="center"></td> 
 </tr> 
 </tbody> 
</table>

### 插入 ###

二叉排序树作为一种动态集合，特点是树的结构不是一次生成的，而是在查找过程中当树中不存在关键字给定值的结点时在进行插入。

由于二叉排序树是递归定义的，插入结点的过程如下：

1.  若原二叉排序树为空，直接插入结点
2.  若关键字 k k k小于根结点的关键字，插入到左子树中
3.  若关键字 k k k大于根结点的关键字，插入到右子树中

一个插入示例如下（插入28，58），**发现插入的新结点一定是某个叶子结点**。

![1.png][]

**实现代码如下**

int BST_InSert(BiTree &T,KeyType k){
 
 if(T==NULL){
 //原树为空，新插入的记录为根结点
 T=(BiTree) malloc (sizeof(BSTNode));
 T->key=k;
 T->lchild=T->rchild=NULL;
 return 1;
 }
 else if(k==T->key) //树中存在相同关键字的结点
 return 0;
 else if(k<T->key)
 return BST_InSert(T->lchild,k); //递归插入T的左子树中
 else
 return BST_InSert(T->rchild,k); //递归插入T的右子树中
 }

### 构造 ###

void Creat_BST(BiTree &T,KeyType str[],int n){
 
 //用关键字数组str[]建立一个二叉排序树
 T=NULL;
 int i=0;
 while(i<n){
 
 BST_InSert(T,str[i]);
 i++;
 }
 }

### 删除 ###

在二叉排序树中删除一个结点时，**不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来**，同时确保二叉排序树的性质不会丢失。

**删除操作实现过程按以下3种情况来处理**：

1.  若删除的结点z为叶子结点，直接删除
2.  若结点 z z z只有一颗左子树或右子树，则让 z z z的子树成为 z z z父节点的子树，替代 z z z的位置
3.  若 z z z有左右2棵子树，则令 z z z的直接后继（或直接前驱）替代 z z z，然后从 B S T BST BST中删去这个直接后继（或直接前驱），这样就转化为了第一种或第二种情况

**删除示例如下**：

![2.jpg][]

## 平衡二叉树（AVL） ##

### 定义 ###

为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证**任意结点的左、右子树高度差的绝对值不超过1**，将这样的树称为平衡二叉树。

**平衡因子**：结点左子树和右子树的高度差，取值只可能为 − 1 , 0 , 1 -1,0,1 −1,0,1。

**平衡二叉树示例图**

![3.jpg][]

### 插入 ###

1.  未破坏平衡，无需调整
2.  破坏平衡，先找到**插入路径上离插入结点最近的平衡因子绝对值大于1的结点A**，再对以A为根的子树，调整各结点的位置关系，使之重新达到平衡。

**示例图如下**，其中75即为A结点

![4.png][]

平衡二叉树的插入过程前半部分与二叉排序树相同，但是在插入新结点后，如果造成了不平衡，要做出相应的调整，可以**归纳为以下4种调整情况**：

1.  **LL（右单旋转）** 在A的左孩子的左子树上插入新结点。将A的左孩子B向**右上旋转**替代A成为根结点，将A结点向**右下旋转**成为B的右子树的根结点，而**B的原右子树则作为A结点的左子树**。

![5.png][]

1.  **RR（左单旋转）** 在A的右孩子的右子树上插入新结点。将A的右孩子B向**左上旋转**替代A成为根结点，将A结点向**左下旋转**成为B的左子树的根结点，而**B的原左子树则作为A结点的右子树**。

![6.png][]

1.  **LR（先左后右）** 在A的左孩子的右子树上插入新结点。先将A的左孩子B的右子树的根结点C向**左上旋转**提升到B的位置，然后再把该C结点向**右上旋转**提升到A的位置。

![7.png][]

1.  **RL（先右后左）** 在A的右孩子的左子树上插入新结点。先将A的右孩子B的左子树的根结点C向**右上旋转**提升到B的位置，然后再把该C结点向**左上旋转**提升到A的位置。

![8.png][]

### 查找 ###

平衡二叉树的查找过程和二叉排序树相同。假设 N h N\_h Nh表示深度为 h h h的 A V L AVL AVL中含有的最少结点数，显然 N 0 = 1 , N 1 = 2 , N h = N h − 1 + N h − 2 + 1 N\_0=1,N\_1=2,N\_h=N\_\{h-1\}+N\_\{h-2\}+1 N0=1,N1=2,Nh=Nh−1\+Nh−2\+1。

**结论**： n n n个结点的平衡二叉树的最大深度为 l o g 2 n log\_2^n log2n，平均查找长度为 O ( l o g 2 n ) O(log\_2^n) O(log2n)。

## 哈夫曼（Huffman）树和哈夫曼编码 ##

### 哈夫曼树 ###

#### 定义和构造 ####

![9.jpg][]

#### 示例 ####

![10.jpg][]

### 哈夫曼编码 ###

![11.jpg][]

[C]: https://blog.csdn.net/bluesliuf/article/details/89033884
[1.png]: /images/20220223/718b4f29ec0a4a3aa0dbc4fd49a83bcc.png
[2.jpg]: /images/20220223/b74c81ff8e5d4a3b96061b642a7f9f0a.png
[3.jpg]: /images/20220223/55ec5bd2b28c4252a4e6f821a3b3d09f.png
[4.png]: /images/20220223/2f940459e0db4b6f90dfe78daeb09d96.png
[5.png]: /images/20220223/6088355000cf4ba9bb0b1b12d10c7720.png
[6.png]: /images/20220223/a442b1db0d45449c92afafdd067f21db.png
[7.png]: /images/20220223/4e9049f3705a4948ae736d60e940cf5e.png
[8.png]: /images/20220223/0a687fefd5d1489fa33990fa536e56b0.png
[9.jpg]: /images/20220223/c27e0c56b2e040f7a8632b0e127945b2.png
[10.jpg]: /images/20220223/de119002afb0405fbbeb2946183f9285.png
[11.jpg]: /images/20220223/73b9fa5bfebf4cd491fb490941b49dc3.png