首页 > 其他分享 >【数据结构】C语言实现的AVL树操作集

【数据结构】C语言实现的AVL树操作集

时间：2023-01-07 10:44:46浏览次数：47  
标签：Right AVLTree C语言 AVL Height Position 数据结构 Data Left

看到网上完整的AVL树操作集较少，索性自己写了一个，望大佬指教！

不多废话，上代码:

AVLTREE.h头文件

 1 #pragma once
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <assert.h>
 5 
 6 struct AVLNode;
 7 typedef struct AVLNode* Position;
 8 typedef struct AVLNode* AVLTree;
 9 typedef int ElementType;
10 
11 //清空AVL树
12 void MakeEmpty(AVLTree T);
13 //查找
14 Position Find(AVLTree T, ElementType X);
15 //递归实现查找最大元位置
16 Position FindMin(AVLTree T);
17 //非递归实现查找最小元位置
18 Position FindMax(AVLTree T);
19 //插入
20 AVLTree Insert(AVLTree T, ElementType X);
21 //删除
22 AVLTree Delete(AVLTree T, ElementType X);
23 //遍历
24 ElementType Retrieve(Position P);
25 //打印AVL树
26 void PrintTree(AVLTree T);
27 
28 struct AVLNode
29 {
30     ElementType Data;
31     AVLTree Left;
32     AVLTree Right;
33     int Height;
34 };

AVLTREE.c源文件

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include "AVLTREE.h"
  3 
  4 static int Height(Position P);
  5 static int Max(int a, int b);
  6 static Position SingleRotationWithLeft(Position K2);
  7 static Position doubleRotationWithLeft(Position K3);
  8 static Position SingleRotationWithRight(Position K2);
  9 static Position doubleRotationWithRight(Position K3);
 10 
 11 //计算AVL节点的高度
 12 static int Height(Position P)
 13 {
 14     if (P == NULL)
 15     {
 16         return -1;
 17     }
 18     else
 19     {
 20         return P->Height;
 21     }
 22 }
 23 
 24 //清空AVL树
 25 void MakeEmpty(AVLTree T)
 26 {
 27     if (T != NULL)//递归终止
 28     {
 29         MakeEmpty(T->Left);
 30         MakeEmpty(T->Right);
 31         free(T);
 32     }
 33 }
 34 
 35 //查找
 36 Position Find(AVLTree T, ElementType X)
 37 {
 38     if (T == NULL)
 39     {
 40         printf("Element %d is not found!\n", X);
 41     }
 42     else if (X < T->Data)
 43     {
 44         return Find(T->Left, X);
 45     }
 46     else if (X > T->Data)
 47     {
 48         return Find(T->Right, X);
 49     }
 50     //不然就是找到了，不进行任何操作
 51     return T;
 52 }
 53 
 54 //递归实现查找最小元位置
 55 Position FindMin(AVLTree T)
 56 {
 57     if (T == NULL)
 58     {
 59         return NULL;
 60     }
 61     else if (T->Left == NULL)
 62     {
 63         return T;
 64     }
 65     else
 66     {
 67         return FindMin(T->Left);
 68     }
 69 }
 70 
 71 //非递归实现查找最大元位置
 72 Position FindMax(AVLTree T)
 73 {
 74     if (T != NULL)
 75     {
 76         while (T->Right != NULL)
 77         {
 78             T = T->Right;
 79         }
 80     }
 81     return T;
 82 }
 83 
 84 //返回两者之间的较大值
 85 static int Max(int a, int b)
 86 {
 87     return (a > b ? a : b);
 88 }
 89 
 90 //左单旋转（LL型状态）
 91 static Position SingleRotationWithLeft(Position K2)
 92 {
 93     Position K1;
 94 
 95     K1 = K2->Left;
 96     K2->Left = K1->Right;
 97     K1->Right = K2;
 98 
 99     K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
100     K1->Height = Max(Height(K1->Left), K2->Height) + 1;
101 
102     return K1;//新的根节点
103 }
104 
105 //左双旋转（LR型状态）先左旋在右旋
106 static Position doubleRotationWithLeft(Position K3)
107 {
108     K3->Left = SingleRotationWithRight(K3->Left);
109     return SingleRotationWithLeft(K3);
110 }
111 
112 //右单旋转（RR型状态）
113 static Position SingleRotationWithRight(Position K2)
114 {
115     Position K1;
116 
117     K1 = K2->Right;
118     K2->Right = K1->Left;
119     K1->Left = K2;
120 
121     K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
122     K1->Height = Max(Height(K1->Right), K2->Height) + 1;
123 
124     return K1;//新的根节点
125 }
126 
127 //右双旋转（RL型状态）先右旋在左旋
128 static Position doubleRotationWithRight(Position K3)
129 {
130     K3->Right = SingleRotationWithLeft(K3->Right);
131     return SingleRotationWithRight(K3);
132 }
133 
134 //插入
135 AVLTree Insert(AVLTree T, ElementType X)
136 {
137     if (T == NULL)
138     {
139         T = malloc(sizeof(struct AVLNode));
140         assert(T);
141 
142         T->Data = X;
143         T->Height = 0;
144         T->Left = T->Right = NULL;
145     }
146     else if (X < T->Data)
147     {
148         T->Left = Insert(T->Left, X);
149         if (Height(T->Left) - Height(T->Right) == 2)
150         {
151             if (X < T->Left->Data)
152             {
153                 T = SingleRotationWithLeft(T);
154             }
155             else
156             {
157                 T = doubleRotationWithLeft(T);
158             }
159         }
160     }
161     else if (X > T->Data)
162     {
163         T->Right = Insert(T->Right, X);
164         if (Height(T->Right) - Height(T->Left) == 2)
165         {
166             if (X > T->Right->Data)
167             {
168                 T = SingleRotationWithRight(T);
169             }
170             else
171             {
172                 T = doubleRotationWithRight(T);
173             }
174         }
175     }
176     /*else x 已经在树中，我们什么都不做*/
177 
178     T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
179     return T;
180 }
181 
182 //删除
183 AVLTree Delete(AVLTree T, ElementType X)
184 {
185     Position TmpCell;
186     if (T == NULL)
187     {
188         printf("Element not found!");
189     }
190     else if (X < T->Data)//往左走
191     {
192         T->Left = Delete(T->Left, X);
193         if (Height(T->Left) - Height(T->Right) == 2)
194         {
195             if (X < T->Left->Data)
196             {
197                 T = SingleRotationWithLeft(T);
198             }
199             else
200             {
201                 T = doubleRotationWithLeft(T);
202             }
203         }
204     }
205     else if (X > T->Data)//往右走
206     {
207         T->Right = Delete(T->Right, X);
208         if (Height(T->Right) - Height(T->Left) == 2)
209         {
210             if (X > T->Right->Data)
211             {
212                 T = SingleRotationWithRight(T);
213             }
214             else
215             {
216                 T = doubleRotationWithRight(T);
217             }
218         }
219     }
220     else if (X == T->Data)//如果就是要删除的节点
221     {
222         if (T->Left && T->Right)//有两个儿子
223         {
224             if (Height(T->Left) > Height(T->Right))
225             {
226                 Position min = FindMax(T->Left);
227                 T->Data = min->Data;
228                 T->Left = Delete(T->Left, min->Data);
229             }
230             else
231             {
232                 Position max = FindMin(T->Right);
233                 T->Data = max->Data;
234                 T->Right = Delete(T->Right, max->Data);
235             }
236         }
237         else//有一个或零个儿子
238         {
239             TmpCell = T;
240             if (T->Left == NULL)
241             {
242                 T = T->Right;
243             }
244             else if (T->Right == NULL)
245             {
246                 T = T->Left;
247             }
248             free(TmpCell);
249         }
250     }
251 
252     return T;
253 }
254 
255 //遍历
256 ElementType Retrieve(Position P)
257 {
258     return P->Data;
259 }
260 
261 //打印AVL树
262 void PrintTree(AVLTree T)
263 {
264     if (T != NULL)
265     {
266         PrintTree(T->Left);
267         printf("%d ", T->Data);
268         PrintTree(T->Right);
269     }
270 }

main.c源文件

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include "AVLTREE.h"
 3 
 4 int main()
 5 {
 6     AVLTree T = NULL;
 7     Position P;
 8 
 9     //插入1 ~ 30
10     for (int i = 1; i <= 30; i++)
11     {
12         T = Insert(T, i);
13     }
14     PrintTree(T);
15     printf("\n");
16 
17     P = FindMin(T);
18     printf("\n最小元为：%d\n", P->Data);
19     P = FindMax(T);
20     printf("\n最大元为：%d\n", P->Data);
21 
22     printf("--------------------------------------------------------------------------------");
23 
24     //删除其中的18
25     printf("\n删除其中的18\n\n");
26     T = Delete(T, 18);
27     PrintTree(T);
28     printf("\n\n");
29 
30     //查找18
31     P = Find(T, 18);
32 
33     //清空AVL树
34     MakeEmpty(T);
35     if (T != P)
36     {
37         printf("\n清空完毕！\n");
38     }
39 
40     system("pause");
41     return 0;
42 }

 

标签：Right,AVLTree,C语言,AVL,Height,Position,数据结构,Data,Left
From： https://www.cnblogs.com/Aeternus/p/17032215.html

相关文章

  • Pytorch基础-tensor数据结构
    torch.Tensor是一种包含单一数据类型元素的多维矩阵，类似于numpy的array。Tensor可以使用torch.tensor()转换Python的list或序列数据生成，生成的是dtype......
  • 【数据结构与算法】Collection接口&迭代器
    Java合集框架数据结构是以某种形式将数据组织在一起的合集（collection）。数据结构不仅存储数据，还支持访问和处理数据的操作在面向对象的思想里，一种数据结构也被认为是一个容器......
  • C语言百日刷题第一天
    猜名次5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：A选手说：B第二，我第三；B选手说：我第二，E第四；C选手说：我第一，D第二；D选手说：C最后，我第三；E选手说：我第四，A第一；比赛结束后，每......
  • 【C语言】解决error C4996: 'fopen': This function or variable may be unsafe. Cons
    转载：http://t.csdn.cn/WkbhK几天编译文件的时候报错，编译出错信息：错误1errorC4996:'fopen':Thisfunctionorvariablemaybeunsafe.Considerusingfopen_sinst......
  • C语言图书管理系统[2023-01-06]
    C语言图书管理系统[2023-01-06]模仿图书馆的借书还书操作，用C语言实现图书管理系统。系统必须先登录方可进入系统。该系统分为读者和图书管理员2类用户，若是读者登录成功后......
  • 理解HashMap底层数据结构
    文章目录​​`hash`​​​​常用解决哈希冲突方法​​​​链地址法​​​​开放地址法​​​​`array`​​​​链表​​​​红黑树​​​​`HashMap`​​​​参考文章​​在......
  • QFramework v1.0 使用指南 工具篇：15. 补充内容：GridKit 二维格子数据结构
    在做游戏的过程中，我们经常需要处理二维格子类的数据，比如消除类游戏、俄罗斯方块、各种棋类游戏，还有我们最常用的Tilemap的地块数据，这些都需要二维格子数据结构。而在Ga......
  • 数据结构：ST表 学习笔记
    ST表RMQ问题RMQ是英文RangeMaximum/MinimumQuery的缩写，表示区间最大（最小）值。ST表是用于解决离线RMQ问题的一种线性数据结构，在全国青少年信息学奥林匹克系列竞......
  • dataframe数据结构之数据的筛选
    导入模块importpandasaspd案例数据my_dict={'姓名':['张三','李四','王二','六月','北海'],'年龄':[23,27,26,22,18],'性别':['男......
  • 数据结构
    数据结构：操作对象和操作对象之间的关系1、操作对象为数值对象例：长方形S=ab面积计算公式操作对象：S\a\b对象关系：S=ab特点：数据元素的关系简单，计算复杂，因......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99