第一次做关于平衡树的题目
第一次做的时候 忘记判断是否是空节点
第二次做，发现LR平衡自己理解错了
对于链式结构理解还是不够深刻，乖乖看书去
题目链接PAT 1066
附上关于平衡树的四种旋转操作
代码如下：
#include<stdio.h>typedef int ElementType; typedef struct AVLTreeNode *AVLTree;typedef struct AVLTreeNode{ ElementType Data; AVLTree Left; AVLTree Right; int Height; };int GetHeight(AVLTree A){if(A==NULL)return -1;elsereturn A->Height;}int Max(int a,int b){return (a>b)?a:b;} AVLTree SingleLeftRotation(AVLTree A) {//A必须有一个左子结点B//将A与B做左单旋 ， 更新AB的高度 ， 返回新的根节点BAVLTree 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; } AVLTree SingleRightRotation(AVLTree 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; }AVLTree DoubleLeftRightRotation(AVLTree A) {//A必须有一个左子结点B，且B必须有一个右子节点C//将AB与C 做两次单选，返回新的节点CA->Left = SingleRightRotation(A->Left);//将BC做右单旋，返回Creturn SingleLeftRotation(A);//将AC做左单旋，，C返回}AVLTree DoubleRightLeftRotation(AVLTree A) {A->Right= SingleLeftRotation(A->Right);return SingleRightRotation(A);} AVLTree AVL_Insertion(ElementType X,AVLTree T) { /* 将 X插入 AVLAVL 树 T中，并且返回调整后的AVLAVL 树 */if(!T){ /* 若插入空树 ，则新建包含一个结点的树*/T= (AVLTree)malloc(sizeof(struct AVLTreeNode));T->Data = X;T->Height = 0;T->Left = T->Right =NULL;}else if(X<T->Data){//插入T的左子树T->Left = AVL_Insertion(X,T->Left);if(GetHeight(T->Left)-GetHeight(T->Right)==2)//需要左转if(X<T->Left->Data)T=SingleLeftRotation(T);//左单旋elseT= DoubleLeftRightRotation(T);//左右双旋}else if(X>T->Data){//插入T的右子树T->Right =AVL_Insertion(X,T->Right);if(GetHeight(T->Left)-GetHeight(T->Right)==-2)//需要右转if(X>T->Right->Data)T=SingleRightRotation(T);//右单旋elseT=DoubleRightLeftRotation(T);//右左双旋}T->Height = Max(GetHeight(T->Left),GetHeight(T->Right))+1;return T; }int main(){AVLTree T=NULL;int i,n,num;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&num);T= AVL_Insertion(num,T);}printf("%d",T->Data);return 0;}
蚁穴虽小，溃之千里。
