# Root of AVL Tree 平衡二叉树C语言完成

### 树5 Root of AVL Tree（25 分）

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:

``````5
88 70 61 96 120``````

Sample Output 1:

``70``

Sample Input 2:

``````7
88 70 61 96 120 90 65``````

Sample Output 2:

``88``
``大概意思就是建立一个平衡二叉树,最后把根节点打印出来``

LL旋转 RR旋转 RL旋转 LR旋转 ## 以下是接口:

``````void PrintTree(Node Tree);

Node CreateNode(int V);

Node Insert(Node Tree,int V);

int GetHeight(Node node);

Node SingleLeftRotation(Node tree);

Node SingleRightRotation(Node tree);

Node LeftRightRotaion(Node tree);

Node RightLeftRotation(Node tree);

int Max(int a,int b); ``````

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

typedef struct _node * Node;

struct _node
{
int Data;
Node Left,Right;
int Height;
};

void PrintTree(Node Tree);

Node CreateNode(int V);

Node Insert(Node Tree,int V);

int GetHeight(Node node);
//LL旋转
Node SingleLeftRotation(Node tree);
//RR旋转
Node SingleRightRotation(Node tree);
//LR旋转
Node LeftRightRotaion(Node tree);
//RL旋转
Node RightLeftRotation(Node tree);

int Max(int a,int b);

int main()
{

// int arr[]={88 ,70 ,61 ,96, 120 ,90, 65};
int n;
scanf("%d",&n);
Node tree=NULL;
int input;
for(int i=0;i<n;i++)
{
scanf("%d",&input);
tree=Insert(tree,input);
}

printf("%d",tree->Data);
return 0;
}

int GetHeight(Node node){

if(!node){
return 0;
}else{
return node->Height;
}
}
int Max(int a,int b){
return a>b?a:b;
}

Node CreateNode(int V)
{
Node node = (Node)malloc(sizeof(struct _node));
node->Left=node->Right=NULL;
node->Data = V;
node->Height=0;
return node;
}

Node Insert(Node tree,int V){
// printf("=====================\n");
if(!tree)
{
tree = CreateNode(V);
}else
{
if(V < tree->Data)
{
tree->Left = Insert(tree->Left,V);
//******************** ×ó±ß¸ß
if((GetHeight(tree->Left)-GetHeight(tree->Right))==2)
{
if(V<tree->Left->Data){//LL
tree = SingleLeftRotation(tree);
}else{//LR
tree =  LeftRightRotaion(tree);
}
}
}else if(V > tree->Data)
{
tree->Right = Insert(tree->Right,V);
//********************ÓÒ±ß¸ßÁË
if((GetHeight(tree->Left)-GetHeight(tree->Right))==-2)
{

if(V<tree->Right->Data){//RL

tree = RightLeftRotation(tree);

}else{//RR
tree =  SingleRightRotation(tree);
}
}

}

}

tree->Height = 1+Max(GetHeight(tree->Left),GetHeight(tree->Right));
return tree;
}

Node SingleLeftRotation(Node A){
// Node Atmp = A;
// A = A->Left;
// Atmp->Left=A->Right;
// A->Right = Atmp;
// Atmp->Height=1+Max(Atmp->Left->Height,Atmp->Right->Height);
// A->Height=1+Max(A->Left->Height,A->Right->Height);
Node B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height=1+Max(GetHeight(A->Left),GetHeight(A->Right));
B->Height=1+Max(GetHeight(B->Left),GetHeight(B->Right));
return B;
}

Node SingleRightRotation(Node A){
Node B = A->Right; // Left
A->Right = B->Left;
B->Left = A;
A->Height=1+Max(GetHeight(A->Left),GetHeight(A->Right));
B->Height=1+Max(GetHeight(B->Left),GetHeight(B->Right));
return B;

}
Node LeftRightRotaion(Node A){
A->Left = SingleRightRotation(A->Left);
A=SingleLeftRotation(A);
return A;
}

Node RightLeftRotation(Node A){
A->Right=SingleLeftRotation(A->Right);
A =  SingleRightRotation(A);
return A;
}

``````
原文作者：平衡二叉树
原文地址: https://blog.csdn.net/qianyedoufulao/article/details/78189352
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。