-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAVL.c
More file actions
77 lines (67 loc) · 1.66 KB
/
Copy pathAVL.c
File metadata and controls
77 lines (67 loc) · 1.66 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode
{
int data;
int bf;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/*对p为根的二叉树进行右旋处理*/
void R_Rotate(BiTree *P)
{
BiTree L;
L = (*P)->lchild;
(*P)->lchild = L->rchild;
L->rchild = (*P);
*P = L;
}
/*对p为根的二叉树进行左旋处理*/
void L_Rotate(BiTree *P)
{
BiTree R;
R = (*P)->rchild;
(*P)->rchild = R->lchild;
R->lchild = (*P);
*P = R;
}
/*左平衡旋转处理*/
#define LH +1 /*左高*/
#define EH 0 /*等高*/
#define RH -1 /*右高*/
/*对指针T所指结点为根的二叉树做左平衡旋转处理*/
/*本算法结束时，指针T指向新的根节点*/
void LeftBalance(BiTree *T)
{
BiTree L, Lr;
L = (*T)->lchild;
// Lr = L->rchild;
// 关键的难点在于这个bf参数的判断和改变，真的是很难理解清楚
switch(L->bf)
{
case LH:
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH:
Lr = L->rchild;
switch(Lr->bf)
{
case LH:
(*T)->bf = RH;
L->bf = EH;
break;
case EH:
(*T)->bf = L->bf=EH;
break;
case RH:
(*T)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*T)->lchild);
R_Rotate(T);
}
}
Status InsertAVL(BiTree *T, int e, Status *taller)
{
}