(C语言) AVL树 - 自平衡二叉树:插入、删除

时间:2021-10-02 10:10:17

数组a[9] = {4,2,6,1,3,5,7,16,15};

(C语言) AVL树 - 自平衡二叉树:插入、删除

说明:1、层序遍历AVL树,括号内为每个节点的高度值

          2、第二行为删除节点“5”之后的AVL树

Reference:  https://blog.csdn.net/silence2015/article/details/50966748

                   https://blog.csdn.net/u010552731/article/details/47393549

  1 /*
  2  * FILE: AVL.c
  3  * DATE: 20180324
  4  * ==============
  5  */
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 
  9 struct node{
 10         int data;
 11         struct node *left;
 12         struct node *right;
 13         int height;
 14 };
 15 
 16 #define NODENUMBER 9
 17 
 18 struct node *createNode(int value);
 19 struct node *insertNode(struct node *head, struct node *new);
 20 void printNode(struct node *p);
 21 void levelTraverse(struct node *head, void (*fun)(struct node *));
 22 struct node *deleteNode(struct node *head, int value);
 23 
 24 int main(int argc, char *argv[])
 25 {
 26         int a[9] = {4,2,6,1,3,5,7,16,15};
 27         struct node *head = NULL;
 28         int i;
 29         for(i=0; i<NODENUMBER; i++)
 30                 head = insertNode(head, createNode(a[i]));
 31         levelTraverse(head, printNode);
 32         printf("\n");
 33         head = deleteNode(head, 5);
 34         levelTraverse(head, printNode);
 35         printf("\n");
 36         return 0;
 37 }
 38 // 新建节点
 39 struct node *createNode(int value)
 40 {
 41         struct node *p = (struct node *)malloc(sizeof(struct node));
 42         p->data = value;
 43         p->left = p->right = NULL;
 44         p->height = 1;
 45 }
 46 // 左旋:头节点的右子树向左旋转
 47 struct node *rotationLeft(struct node *head)
 48 {
 49         struct node *new = head->right;
 50         head->right = new->left;
 51         new->left = head;
 52         head->height = getHeight(head); // 旋转后更新两节点的高度值
 53         new->height = getHeight(head);
 54         return new;
 55 }
 56 // 右旋
 57 struct node *rotationRight(struct node *head)
 58 {
 59         struct node *new = head->left;
 60         head->left = new->right;
 61         new->right = head;
 62         head->height = getHeight(head); // 更新节点高度值
 63         new->height = getHeight(new);
 64         return new;
 65 }
 66 // 左右旋:头节点左孩子的右孩子向左旋,头节点的左孩子向右旋
 67 struct node *rotationLeftRight(struct node *head)
 68 {
 69         head->left = rotationLeft(head->left);
 70         head = rotationRight(head);
 71         return head;
 72 }
 73 // 右左旋
 74 struct node *rotationRightLeft(struct node *head)
 75 {
 76         head->right = rotationRight(head->right);
 77         head = rotationLeft(head);
 78         return head;
 79 }
 80 // 节点高度:从下往上
 81 int getHeight(struct node *head)
 82 {
 83         if(head == NULL)
 84                 return 0;
 85         int height_left = getHeight(head->left);
 86         int height_right = getHeight(head->right);
 87         return (height_left>height_right)?(height_left+1):(height_right+1);
 88 }
 89 // 插入节点:AVL平衡二叉树
 90 struct node *insertNode(struct node *head, struct node *new)
 91 {
 92         if(head == NULL)
 93                 return new;
 94         if(new->data < head->data) // 将插入于头节点的左子树中
 95         {
 96                 head->left = insertNode(head->left, new); // 递归
 97                 if(getHeight(head->left)-getHeight(head->right) == 2) // 新插节点后,左右子树高度差
 98                         if(new->data < head->left->data) // 新节点插入于外部:LL
 99                                 head = rotationRight(head);     // 右旋
100                         else // 新节点插入于内部:LR
101                                 head = rotationLeftRight(head); // 左右旋
102         }
103         else if(new->data > head->data) // 将插入于头节点的右子树中
104         {
105                 head->right = insertNode(head->right, new);
106                 if(getHeight(head->left)-getHeight(head->right) == -2)
107                         if(new->data > head->right->data) // 新节点插入于外部:RR
108                                 head = rotationLeft(head); // 左旋
109                         else // 新节点插入于内部:RL
110                                 head = rotationRightLeft(head); // 右左旋
111         }
112         head->height = getHeight(head);
113         return head;
114 }
115 // 最小值:递归
116 struct node *findMin(struct node *head)
117 {
118         if(head==NULL || head->left==NULL)
119                 return head;
120         findMin(head->left);
121 }
122 // 删除节点
123 struct node *deleteNode(struct node *head, int value)
124 {
125         if(head == NULL)
126                 return NULL;
127         if(value < head->data) // 需删除的节点位于左子树
128         {
129                 head->left = deleteNode(head->left, value); // 递归
130                 if(getHeight(head->right)-getHeight(head->left) == 2) // 删除节点后,左右子树高度差
131                         if((head->right->left!=NULL) && (getHeight(head->right->left)>getHeight(head->right->left)))
132                                 head = rotationRightLeft(head); // 右左旋
133                         else
134                                 head = rotationLeft(head); // 左旋
135         }
136         else if(value > head->data) // 需删除的节点位于右子树
137         {
138                 head->right = deleteNode(head->right, value);
139                 if(getHeight(head->right)-getHeight(head->left) == -2)
140                         if((head->left->right!=NULL) && (getHeight(head->left->right)>getHeight(head->left->left)))
141                                 head = rotationLeftRight(head); // 左右旋
142                         else
143                                 head = rotationRight(head); // 右旋
144         }
145         else // 找到要删除的节点
146                 if(head->left && head->right) // 该节点左右子树都有
147                 {
148                         struct node *temp = findMin(head->right); // 寻找该节点右子树的最小值
149                         head->data = temp->data;
150                         head->right = deleteNode(head->right, temp->data);
151                 }
152                 else // 该节点只有一个孩子 或为 叶子节点
153                 {
154                         struct node *del = head;
155                 /*      if(head->left != NULL)  
156                                 head = head->left;
157                         else if(head->right != NULL)
158                                 head = head->right;
159                         else
160                                 head = NULL;
161                 */
162                         head = (head->left!=NULL)?head->left:head->right;
163                         free(del);
164                 }
165         if(head != NULL)
166                 head->height = getHeight(head); // 更新节点高度值
167         return head;
168 }
169 // 打印节点内容
170 void printNode(struct node *p)
171 {
172         printf("%d(%d) ", p->data, p->height); // 节点值、节点高度
173 }
174 // 层序遍历:队列
175 void levelTraverse(struct node *head, void (*fun)(struct node *))
176 {
177         struct node *queue[NODENUMBER];
178         int front = 0, last = 1;
179         int index = 0, level = 0;
180         queue[index++] = head;
181         while(front < index)
182         {
183                 struct node *p = queue[front++];
184                 (*fun)(p);
185                 if(p->left != NULL) queue[index++]=p->left; // 入队
186                 if(p->right != NULL) queue[index++]=p->right;
187                 if(front == last)
188                 {
189                         last = index; level++;
190                 }
191         }
192 }