从零开始学数据结构系列之第三章《平衡二叉树的旋转类型总结及总代码》_平衡二叉树定义

---

我们上一篇文章已经讲了这四种类似，那我们接着上一篇文章继续讲解

LR/RL型分析

我们可以看到上图，这最直观的对比

我们再重新看看LR型

他是再那边开始失衡的呢？

​ 答案是在，右玄孙那边开始失衡的，那我们要去从他的==最小失衡子树==那边开始平衡，

那我们但看他的最小失衡子树那边，可以看到什么呢？

这是不是一个RR型，那我们就可以用RR型的方式，给他平衡起来

那这样平衡完后的图是这样的

那我们最小失衡树已经平衡完了，那是不是应该平恒第二小的（最大的）失衡树了

那这样通过发现，他是一个LL型的

这是不是一个LL型，那我们就可以用LL型的方式，给他平衡起来

那这样平衡完后的图是这样的

惊奇的发现，其实LR型，就是先经过RR调整，之后再进行LL调整就行了

同理RL就是LR反过来的，先LL在RR

总结

总代码

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode 
{
    int data;
    int height;
    struct TreeNode* lchild;
    struct TreeNode* rchild;
}TreeNode;

int getHeight(TreeNode* node)
{
	return node ? node->height:0; 
}

int max_lenth(int a, int b) 
{
	return a > b ? a : b;
}

void rrRotation(TreeNode* node, TreeNode** root) 
{
    /*暂存点*/
    TreeNode* temp = node -> rchild;
    node -> rchild = temp -> lchild;
    temp -> lchild = node;
    /*更新高度*/
    node -> height = max_lenth(getHeight(node -> lchild), getHeight(node -> rchild)) + 1;
    temp -> height = max_lenth(getHeight(temp -> lchild), getHeight(temp -> rchild)) + 1;
    *root = temp;
}

void llRotation(TreeNode* node, TreeNode** root)
{
	TreeNode* temp = node -> lchild;
    node -> lchild = temp -> rchild; 
    temp -> rchild = node;
    node -> height = max_lenth(getHeight(node -> lchild), getHeight(node -> rchild)) + 1;
    temp -> height = max_lenth(getHeight(temp -> lchild), getHeight(temp -> rchild)) + 1;
    *root = temp;
}


void avlInsert(TreeNode** T, int data) 
{
	int lHeight =0;
    int rHeight =0;
	if(*T == NULL)
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->lchild=NULL;
		(*T)->rchild=NULL;
		(*T)->data=data;
		(*T)->height=0;
	}
	/*左边*/
	else if((*T)->data > data)
	{
		avlInsert(&((*T)->lchild),data);
		lHeight = getHeight((*T) -> lchild);
		rHeight = getHeight((*T) -> rchild);
		printf("lHeight=%d  rHeight=%d T=%d\r\n",lHeight,rHeight,(*T)->data);
		if(lHeight - rHeight == 2)
		{
            /*最后的节点与他的父亲之间的对比*/
			if(data < (*T)->lchild ->data)
			{
				llRotation(*T,T);
			}
			else
			{
				rrRotation((*T) -> lchild, &(*T) -> lchild);
                llRotation(*T, T);
			}
		}

	}
	/*右边*/
	else
	{
		avlInsert(&((*T)->rchild),data);
		lHeight = getHeight((*T) -> lchild);
		rHeight = getHeight((*T) -> rchild);
		printf("lHeight=%d  rHeight=%d T=%d\r\n",lHeight,rHeight,(*T)->data);
		if(rHeight - lHeight == 2)
		{
            /*最后的节点与他的父亲之间的对比*/
			if(data > (*T)->rchild ->data)
			{
				rrRotation(*T,T);
			}
			else
			{
				llRotation((*T) -> rchild, &(*T) -> rchild);
                rrRotation(*T, T);
			}
		}
	}
	(*T) -> height = max(getHeight((*T) -> lchild), getHeight((*T) -> rchild)) + 1;
}

void preOrder(TreeNode* T) 
{
	if(T)
	{
		printf("%d ",T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

int main() 
{
	int i=0;
    /*或者5，4，3，2，1*/
	int temp[] = {1,2,3,4,5};
	TreeNode* T = NULL;
	for(;i<(sizeof(temp)/sizeof(int));i++)
		avlInsert(&T,temp[i]);
	preOrder(T);
	printf("\r\n");
	return 0;
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》