平衡二叉树的建立，插入

输入测试数据：

5 4 10 0 0 8 14 0 0 0 0

和

5 4 10 0 0 8 14 0 0 0 0

头文件：head.h

 1 #ifndef HEAD_H_INCLUDE
 2 #define HEAD_H_INCLUDE
 3 
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 
 7 #define MAXSIZE 15
 8 #define NoInfo 0
 9 typedef int ElementType;
10 
11 
12 typedef struct AVLNode* Position;
13 typedef Position AVLTree;
14 struct AVLNode {
15     ElementType Data;    //结点数据
16     AVLTree Left;        //指向左子树
17     AVLTree Right;        //指向右子树
18     int Height;            //树高
19 };
20 
21 typedef AVLTree ElemType;        //队列中的每个元素是AVL树的结点指针类型
22 typedef struct QNode* Queue;
23 
24 struct QNode {
25     ElemType Data[MAXSIZE];
26     int front, rear;
27 };
28 
29 int Max(int a, int b);
30 
31 //获取T树的高度
32 int GetHeight(AVLTree T);
33 
34 //T结点的平衡因子大于2，进行右单旋
35 AVLTree SingleRightRotation(AVLTree T);
36 
37 //T结点的平衡因子小于-2， 进行左单旋
38 AVLTree SingleLeftRotation(AVLTree T);
39 
40 //T结点的平衡因子小于-2， 但是插入的结点位于T结点的左子树的右子树上，进行左右双旋
41 AVLTree DoubleLeftRightRotation(AVLTree T);
42 
43 //T结点的平衡因子大于2， 但是插入的界定啊位于T结点的右子树的左子树上，进行右左双旋
44 AVLTree DoubleRightLeftRotation(AVLTree T);
45 
46 //AVL树的层序建立
47 AVLTree CreateAVLTree();
48 
49 //打印结点
50 void printNode(AVLTree T, int height);
51 
52 //中序递归遍历平衡二叉树
53 void InorderTraversal(AVLTree T, int height);
54 
55 //平衡二叉树的插入
56 AVLTree Insert(AVLTree T, ElementType X);
57 
58 #include "head.h"
59 
60 //建立一个空的队列
61 Queue CreateQueue();
62 
63 //队列的插入
64 void AddQ(Queue Q, ElemType X);
65 
66 //判断队列是否为空
67 int IsEmpty(Queue Q);
68 
69 //队列元素的删除
70 AVLTree DeleteQ(Queue Q);
71 #endif

平衡二叉树源文件：AVLTree.c

插入元素：

   #include "head.h"
 1 AVLTree Insert(AVLTree T, ElementType X)
 2 {
 3     //将X插入AVL树T中，并且返回调整后的AVL数
 4     if (!T)        //如果树为空，或递归到最后的结点为空
 5     {
 6         T = (AVLTree)malloc(sizeof(struct AVLNode));
 7         T->Data = X;
 8         T->Left = T->Right = NULL;
 9     }
10 
11     else if (X < T->Data)
12     {
13         //先将X插入到二叉树中
14         T->Left = Insert(T->Left, X);
15 
16         //如果二叉树的平衡被破坏，那么需要调整使之平衡
17         if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
18         {
19             if (X < T->Left->Data)
20                 T = SingleLeftRotation(T);        //进行左单旋
21             else
22                 T = DoubleLeftRightRotation(T);    //进行左右双旋
23         }
24     }
25     else if (X > T->Data)
26     {
27         //先将X插入到二叉树中
28         T->Right = Insert(T->Right, X);
29 
30         //如果插入X结点后，T的平衡被破坏，那么需要调整使之达到平衡
31         if (GetHeight(T->Left) - GetHeight(T->Right) == -2)
32         {
33             if (X > T->Right->Data)
34                 T = SingleRightRotation(T);        //将对T结点进行右单旋后结果返回给T
35             else
36                 T = DoubleRightLeftRotation(T);        //将对T结点进行右左双旋后结果返回给T
37         }
38     }
39     //else X = T->Data;        //无需插入
40 
41     //重新计算树高
42     T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
43 
44     return T;
45 
46 }

四种旋转方式：

 1 //左单旋
 2 AVLTree SingleLeftRotation(AVLTree A)
 3 {
 4     //A必有一个左子结点B
 5     AVLTree B = A->Left;
 6     A->Right = B->Right;
 7     B->Right = A;
 8 
 9     //重新计算树高
10     A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
11     B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;
12     return B;
13 }
14 
15 //左右双旋
16 AVLTree DoubleLeftRightRotation(AVLTree A)
17 {
18     //先进行一次右单旋，再进行一次左单旋
19     A->Left = SingleRightRotation(A->Left);    //将B 、C做右单旋，并返回C
20 
21     //将A与C做左单旋，C被返回
22     return SingleLeftRotation(A);
23 }
24 
25 
26 //右单旋
27 AVLTree SingleRightRotation(AVLTree A)
28 {
29     //A必有一个右子结点B
30     AVLTree B = A->Right;
31     A->Right = B->Left;
32     B->Left = A;
33 
34     //重新计算高度
35     A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
36     B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;
37 
38     return B;
39 }
40 
41 //右左双旋
42 AVLTree DoubleRightLeftRotation(AVLTree A)
43 {
44     //先进行一次左单旋，再进行一次右单旋
45     A->Right = SingleLeftRotation(A->Right);    //将B、C做左单旋，并返回C
46 
47     return SingleRightRotation(A);        //将A、C做右单旋，并返回结果，即返回C
48 }

平衡二叉树的层序建立：

 1 //AVL树的层序建立
 2 AVLTree CreateAVLTree()
 3 {
 4     ElementType dt;
 5     AVLTree BT, T;
 6     Queue Q = CreateQueue();
 7 
 8     //建立第一个结点，即根节点
 9     scanf_s("%d", &dt);
10     if (dt != NoInfo)
11     {
12         BT = (AVLTree)malloc(sizeof(struct AVLNode));
13         BT->Data = dt;
14         BT->Left = NULL;
15 
16 
17 
18         BT->Right = NULL;
19         BT->Height = 0;
20         AddQ(Q, BT);
21     }
22     else
23         return NULL;        //若第一个结点就建立不成功， 则返回空树
24 
25     while (!IsEmpty(Q))
26     {
27         T = DeleteQ(Q);
28         scanf_s("%d", &dt);
29         if (dt == NoInfo)
30             T->Left = NULL;
31         else
32         {
33             //分配新结点，作为出队结点左孩子，新结点入队
34             T->Left = (AVLTree)malloc(sizeof(struct AVLNode));
35             T->Left->Data = dt;
36             T->Left->Left = T->Left->Right = NULL;
37             T->Left->Height = 0;
38             AddQ(Q, T->Left);
39         }
40         scanf_s("%d", &dt);
41         if (dt == NoInfo)
42             T->Right = NULL;
43         else
44         {
45             //分配新结点，作为出队结点的右孩子，新结点入队
46             T->Right = (AVLTree)malloc(sizeof(struct AVLNode));
47             T->Right->Data = dt;
48             T->Right->Left = T->Right->Right = NULL;
49             T->Right->Height = 0;
50             AddQ(Q, T->Right);
51         }
52     }
53     return BT;
54 }

二叉树的遍历：

 1 //打印结点
 2 void printNode(AVLTree T, int height)
 3 {
 4     while (height--)
 5         printf("  ");
 6     printf("%d
", T->Data);
 7 }
 8 
 9 //中序递归遍历平衡二叉树
10 void InorderTraversal(AVLTree T, int height)
11 {
12     if (T)
13     {
14         InorderTraversal(T->Right, height + 1);
15         printNode(T, height);
16         InorderTraversal(T->Left, height + 1);
17     }
18 }

求树高和Max的函数：

 1 int GetHeight(AVLTree T)
 2 {
 3     int HL, HR, MaxH;
 4     if (T)
 5     {
 6         HL = GetHeight(T->Left);
 7         HR = GetHeight(T->Right);
 8         MaxH = Max(HL, HR) + 1;
 9         return MaxH;
10     }
11     else return 0;    //该数为空树或该结点的父节点为叶节点
12 }
13 
14 int Max(int a, int b)
15 {
16     return a > b ? a : b;
17 }

队列操作的源文件：Queue.c

 1 #include "head.h"
 2 
 3 //建立一个空的队列
 4 Queue CreateQueue()
 5 {
 6     Queue Q = (Queue)malloc(sizeof(struct QNode));
 7     Q->front = Q->rear = 0;
 8     return Q;
 9 }
10 
11 //判断队列是否已满
12 int IsFull(Queue Q)
13 {
14     return (Q->rear + 1) % MAXSIZE == Q->front;
15 }
16 
17 
18 //队列的插入
19 void AddQ(Queue Q, ElemType X)
20 {
21     if (IsFull(Q))
22     {
23         printf("The queue is full!
");
24         return;
25     }
26     else
27     {
28         Q->Data[Q->rear] = X;
29         Q->rear = (Q->rear + 1) % MAXSIZE;
30     }
31 }
32 
33 //判断队列是否为空
34 int IsEmpty(Queue Q)
35 {
36     return Q->front == Q->rear;
37 }
38 
39 //队列元素的删除
40 AVLTree DeleteQ(Queue Q)
41 {
42     if (IsEmpty(Q))
43     {
44         printf("The Queue is empty!
");
45         return NULL;
46     }
47     else
48     {
49         AVLTree T = Q->Data[Q->front];
50         Q->front = (Q->front + 1) % MAXSIZE;
51         return T;
52     }
53 }

主函数源文件：main.c

 1 #include "head.h"
 2 
 3 int main()
 4 {
 5     int elem;
 6     AVLTree T = CreateAVLTree();
 7     InorderTraversal(T, 0);
 8     printf("

Please the element that you want to insert: ");
 9     scanf_s("%d", &elem);
10     T = Insert(T, elem);
11     InorderTraversal(T, 0);
12 
13     return 0;
14 }