我死活没看明白我的代码和后面的这个代码有什么区别
先给题目吧
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.
我的代码
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode *Tree;
typedef Tree Position;
struct TreeNode{
int Data; /*结点数据*/
Tree Left; /*指向左子树*/
Tree Right; /*指向右子树*/
int Height; /*树高*/
};
int Max(int a,int b)
{
return a > b ? a : b;
}
int GetHeight(Tree T)
{
if(!T) return 0;
else return T->Height;
}
Tree SingleRightRotation( Tree A )
{
Tree B = A->Right;
A->Right = B->Left;
B->Left = A;
A->Height = Max(GetHeight(A->Left),GetHeight(A->Right))+1;
B->Height = Max(GetHeight(B->Right),A->Height)+1;
return B;
}
Tree SingleLeftRotation( Tree A )
{
Tree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max(GetHeight(A->Left),GetHeight(A->Right))+1;
B->Height = Max(GetHeight(B->Left),A->Height)+1;
return B;
}
Tree DoubleLeftRightRotation( Tree A )
{
A->Left = SingleRightRotation(A->Left);
return SingleLeftRotation(A);
}
Tree DoubleRightLeftRotation( Tree A )
{
A->Right = SingleLeftRotation(A->Right);
return SingleRightRotation(A);
}
Tree Insert( Tree T, int X )
{
if(!T){/*若插入空树，则新建包含一个结点的树*/
T = (Tree)malloc(sizeof(struct TreeNode));
T->Data = X;
T->Height = 1;
T->Left = NULL;
T->Right = NULL;
}/*if(插入空树)结束*/
else if(X<T->Data){
T->Left = Insert(T->Left,X);
/*判断是否需要左旋*/
if(GetHeight(T->Left)-GetHeight(T->Right) == 2){
if(X<T->Left->Data){
T = SingleLeftRotation(T);
}else{
T = DoubleLeftRightRotation(T);
}
}
}
else if(X>T->Data){
T->Right = Insert(T->Right,X);
/*判断是否需要右旋*/
if(GetHeight(T->Right)-GetHeight(T->Left) == 2){
if(X>T->Right->Data){
T = SingleRightRotation(T);
}else{
T = DoubleRightLeftRotation(T);
}
}
}/*else X==T->Data 无需插入*/
T->Height = Max(GetHeight(T->Left),GetHeight(T->Right))+1;
/*T->Height = Max(T->Left->Data,T->Right->Data)+1;*/
return T;
}
int main()
{
int N,i,X;
Tree BST;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",&X);
BST = Insert(BST,X);
}
printf("%d\n",BST->Data);
return 0;
}
结果
搜出来的别人的代码
#include<stdio.h>
#include<malloc.h>
typedef struct AVLNode *AVLTree;
struct AVLNode{
int data; // 存值
AVLTree left; // 左子树
AVLTree right; // 右子树
int height; // 树高
};
// 返回最大值
int Max(int a,int b){
return a>b?a:b;
}
// 返回树高，空树返回 -1
int getHeight(AVLTree A){
return A==NULL?-1:A->height;
}
// LL单旋
// 把 B 的右子树腾出来挂给 A 的左子树，再将 A 挂到 B 的右子树上去
AVLTree LLRotation(AVLTree A){
// 此时根节点是 A
AVLTree B = A->left; // B 为 A 的左子树
A->left = B->right; // B 的右子树挂在 A 的左子树上
B->right = A; // A 挂在 B 的右子树上
A->height = Max(getHeight(A->left),getHeight(A->right)) + 1;
B->height = Max(getHeight(B->left),A->height) + 1;
return B; // 此时 B 为根结点了
}
// RR单旋
AVLTree RRRotation(AVLTree A){
// 此时根节点是 A
AVLTree B = A->right;
A->right = B->left;
B->left = A;
A->height = Max(getHeight(A->left),getHeight(A->right)) + 1;
B->height = Max(getHeight(B->left),A->height) + 1;
return B; // 此时 B 为根结点了
}
// LR双旋
AVLTree LRRotation(AVLTree A){
// 先 RR 单旋
A->left = RRRotation(A->left);
// 再 LL 单旋
return LLRotation(A);
}
// RL双旋
AVLTree RLRotation(AVLTree A){
// 先 LL 单旋
A->right = LLRotation(A->right);
// 再 RR 单旋
return RRRotation(A);
}
AVLTree Insert(AVLTree T,int x){
if(!T){ // 如果该结点为空，初始化结点
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->data = x;
T->left = NULL;
T->right = NULL;
T->height = 0;
}else{ // 否则不为空，
if(x < T->data){ // 左子树
T->left = Insert(T->left,x);
if(getHeight(T->left)-getHeight(T->right)==2){ // 如果左子树和右子树高度差为 2
if(x < T->left->data) // LL 单旋
T = LLRotation(T);
else if(T->left->data < x) // LR双旋
T = LRRotation(T);
}
}else if(T->data < x){
T->right = Insert(T->right,x);
if(getHeight(T->right)-getHeight(T->left)==2){
if(x < T->right->data) // RL 双旋
T = RLRotation(T);
else if(T->right->data < x) // RR单旋
T = RRRotation(T);
}
}
}
//更新树高
T->height = Max(getHeight(T->left),getHeight(T->right)) + 1;
return T;
}
int main(){
AVLTree T=NULL;
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++){
int tmp;
scanf("%d",&tmp);
T = Insert(T,tmp);
}
printf("%d",T->data);
return 0;
}
结果
话说着CSDN问答的要求真多，还非要我把平衡二叉树换成AVLTree
