#include<time.h>#include<stdio.h> #include<stdlib.h> //左子树比右子树高一#define LH 1//左子树和右子树一样高#define EH 0//左子树比右子树低一#define RH -1#define EQ(a,b) ((a) == (b))#define LT(a,b) ((a) < (b))#define LQ(a,b)((a) <= (b))typedef struct BSTNode{int data;int bf;BSTNode * lchild;BSTNode * rchild;}BSTNode;typedef BSTNode * BSTree;//左旋void leftRotate(BSTree & root) {BSTree rc = root->rchild;root->rchild = rc->lchild;rc->lchild = root;root = rc;}//右旋void rightRotate(BSTree & root) {BSTree lc = root->lchild;root->lchild = lc->rchild;lc->rchild = root;root = lc;}//对二叉树root进行左平衡处理(LL型和LR型)void leftBalance(BSTree & root) {BSTree lc = root->lchild;switch (lc->bf) {//LL型的只需要进行右旋操作case LH://右旋之后根和左子树都的平衡的root->bf = EH;lc->bf = EH;//右旋操作rightRotate(root);break;//LR型的需要进行左旋操作，然后右旋操作case RH:BSTree rc = lc->rchild;switch (rc->bf) {case LH:root->bf = RH;lc->bf = EH;break;case EH:root->bf = EH;lc->bf = EH;break;case RH:root->bf = EH;lc->bf = LH;break;}rc->bf = EH;leftRotate(root->lchild);rightRotate(root);break;}}//功能：对二叉树root进行左平衡处理(RR型和RL型)void rightBalance(BSTree & root) {BSTree rc = root->rchild;switch (rc->bf) {//RR型只需要做左旋操作case RH:root->bf = EH;rc->bf = EH;//左旋操作leftRotate(root);break;//RL型需要先做右旋操作，然后做左旋操作case LH:BSTree lc = rc->lchild;switch (lc->bf) {case LH:root->bf = EH;rc->bf = RH;break;case EH:root->bf = EH;rc->bf = EH;break;case RH:root->bf = LH;rc->bf = EH;break;}lc->bf = EH;rightRotate(root->rchild);leftRotate(root);break;}}//功能：把元素data插入平衡二叉树root中bool insert(BSTree & root, int data, bool & taller) {if (NULL == root) {root = (BSTree)malloc(sizeof(BSTNode));root->rchild = NULL;root->lchild = NULL;root->data = data;root->bf = EH;taller = true;}else{//该元素已经在平衡二叉树中存在了if (data == root->data) {taller = false;return false;}//插入左子树else if (data < root->data) {if (!insert(root->lchild, data, taller)){return false;}//插入成功，并且树变高了if (taller){switch (root->bf){case LH:leftBalance(root);//平衡二叉树做完左平衡操作后//树高没有变化，故taller = falsetaller = false;break;case EH:root->bf = LH;//原来是平衡的故插入一个元素后//树高必然变高taller = true;break;case RH:root->bf = EH;//原来是右子树比左子树高，，但是当向左子树中//插入一个元素的时候，树变平衡了，故taller = falsetaller = false;break;default:break;}}}//插入右子树else {if (!insert(root->rchild, data, taller)){return 0;}if (taller){switch (root->bf){case LH:root->bf = EH;taller = false;break;case EH:root->bf = RH;taller = true;break;case RH:rightBalance(root);taller = false;break;}}}}return true;}// 在平衡二叉树中查找int节点int * search(BSTree & root, int data) {if (root ==NULL) {return NULL;}if (root->data == data) {return &root->data;}else if (data < root->data) {return search(root->lchild, data);} else {return search(root->rchild, data);}}//功能：输出平衡二叉树中的所有的元素（小->大，中序遍历）void print(BSTree & root){if (NULL == root) {return ;}print(root->lchild);printf("%d ",root->data);print(root->rchild);}//功能：释放平衡二叉树的空间void clear(BSTree & root) {if (NULL == root) {return ;}clear(root->lchild);clear(root->rchild);free(root);}int DeleteAVL(BSTree &T, int key, bool &shorter){if (!T){//No such keyshorter = false;return 0;}else{if (EQ(key, T->data))//找到了需要删除的结点{//如果该结点的lchild 和//rchild 至少有一个为NULL//则大功告成，否则请参照//下方解释BSTree q = T;if (!T->lchild)//如果该结点的lchild 为NULL{q = T;T = T->rchild;free(q);shorter = true;return 1;}else if (!T->rchild){//如果该结点的rchild 为 NULLq = T;T = T->lchild;//如果不是&（引用）的强大功能，这句话是没有意义的free(q);shorter = true;return 1;}else {//删除一个左右孩子都不为空的结点//使该结点的直接前驱p的data替换该结点的data//然后改变key=p.dataBSTree s = T->lchild;while (s->rchild)s = s->rchild;T->data = s->data;key = s->data;//Now, delete the vertice whose data was the new key}}if (LQ(key, T->data)){//这里与InsertAVL不同if (!DeleteAVL(T->lchild, key, shorter)) return 0;if (shorter){switch(T->bf){case LH:T->bf = EH; shorter = true;break;case EH:T->bf = RH;shorter = false;break;case RH:rightBalance(T);if (T->rchild->bf == EH)shorter = false;elseshorter = true;break;}}}else{if (!DeleteAVL(T->rchild, key, shorter)) return 0;if (shorter){switch(T->bf){case LH:leftBalance(T);if (T->lchild->bf == EH)shorter = false;elseshorter = true;break;case EH:T->bf = LH; shorter = false;break;case RH:T->bf = EH;shorter = true;break;}}}}return 1;}//Deletevoid menu() { printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙ ⊙☆⊙ 主菜单⊙☆⊙ ⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n"); printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 1:连续插入数据 输入0结束插入⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n"); printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 2:查找数据⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n"); printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 3删除特定数据⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n"); printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 4输出当前结果⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 5结束程序⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");} int main(){BSTree root = NULL;int num,n;bool taller = false,shorter;system("color 2e"); menu();while(1) {scanf("%d",&num); //if(num==5) break;switch (num){case 1:system("cls");printf("请插入数据 ，输入0结束插入\n");while(scanf("%d",&n)){if(n==0) break;else insert(root,n,taller);}system("cls");menu();break;case 2:system("cls");printf("请输入要查询的数\n");scanf("%d",&n);int *p;p=search(root,n);if (p==NULL){printf("对不起 没有找到 %d!\n",n);}else{printf("恭喜你 数据中存在 %d!\n",n);}menu();break;case 3:system("cls");printf("请输入要删除的数据\n");scanf("%d",&n);DeleteAVL(root,n,shorter);menu();break;case 4:system("cls");print(root);printf("输入0进入主菜单\n");scanf("%d",&n);if(!n)menu();break;case 5:clear(root);return 0;}}return 0;}
参考了 ACb0y的代码
版权声明：本文为博主原创文章，未经博主允许不得转载。
在爱情里，有时候简单的一句话，能胜过千言万语。
