avl树的新算法,欢迎测试并指出不足
程序代码:
#include "avltree.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #define FALSE 0 #define TRUE 1 struct element{ char key[15]; }; struct treeNode{ treePointer leftChild; element data; short int bf; treePointer rightChild; }; typedef struct treeNode *treePointer; void avlInsert(treePointer *parent, element x, int *unbalancedp);/*插入结点函数*/ void leftRotation(treePointer *parent, int *unbalancedp); /* 左旋函数*/ void rightRotation(treePointer *parent, int *unbalancedp); /* 右旋函数*/ void preprintree(treePointer ptr); /* 前序打印二叉树 */ void inprintree(treePointer ptr); /* 中序打印二叉树 */ void avlDelete(treePointer *parent, element x, int *balanced); /* 删除结点函数*/ void leftMaxNode(treePointer *parent, treePointer *maxNode, int *balanced); /* 查找左子树最大元*/ int main(void) { treePointer rootp = NULL; int unbalanced = FALSE; element mydata; int i; for(i = 1; i < 13; i++){ printf("请输入月份名称%d:\n", i); scanf("%s",mydata.key); avlInsert(&rootp, mydata, &unbalanced); } preprintree(rootp); printf("\n"); inprintree(rootp); for(i = 1; i < 2; i++){ printf("\n请输入需删除的月份名称%d:\n", i); scanf("%s",mydata.key); avlDelete(&rootp, mydata, &unbalanced); } preprintree(rootp); printf("\n"); inprintree(rootp); } void avlInsert(treePointer *parent, element x, int *unbalancedp) { if(!*parent){ /* insert element into null tree */ *unbalancedp = TRUE; *parent = (treePointer)malloc(sizeof(struct treeNode)); (*parent)->leftChild = (*parent)->rightChild = NULL; (*parent)->bf = 0; (*parent)->data = x; }else if(strcmp(x.key, (*parent)->data.key) < 0){ avlInsert(&(*parent)->leftChild, x, unbalancedp); if(*unbalancedp) /* left branch has grown higher */ switch((*parent)->bf){ case -1: (*parent)->bf = 0; *unbalancedp = FALSE; break; case 0: (*parent)->bf = 1; break; case 1: leftRotation(parent, unbalancedp); } }else if(strcmp(x.key, (*parent)->data.key) > 0){ avlInsert(&(*parent)->rightChild, x, unbalancedp); if(*unbalancedp) /* right branch has grown higher */ switch((*parent)->bf){ case 1: (*parent)->bf = 0; *unbalancedp = FALSE; break; case 0: (*parent)->bf = -1; break; case -1: rightRotation(parent, unbalancedp); } }else{ *unbalancedp = FALSE; printf("The key is already in the tree!\n"); } } void leftRotation(treePointer *parent, int *unbalancedp) { treePointer grandChild, child; child = (*parent)->leftChild; if(child->bf == 1){ /* LL rotation */ (*parent)->leftChild = child->rightChild; child->rightChild = *parent; (*parent)->bf = 0; (*parent) = child; }else{ /* LR rotation */ grandChild = child->rightChild; child->rightChild = grandChild->leftChild; grandChild->leftChild = child; (*parent)->leftChild = grandChild->rightChild; grandChild->rightChild = *parent; switch(grandChild->bf){ case 1: (*parent)->bf = -1; child->bf = 0; break; case 0: (*parent)->bf = child->bf= 0; break; case -1: (*parent)->bf = 0; child->bf = 1; } *parent = grandChild; } (*parent)->bf = 0; *unbalancedp = FALSE; } void rightRotation(treePointer *parent, int *unbalancedp) { treePointer grandChild, child; child = (*parent)->rightChild; if(child->bf == -1){ /* RR rotation */ (*parent)->rightChild = child->leftChild; child->leftChild = *parent; (*parent)->bf = 0; (*parent) = child; }else{ /* RL rotation */ grandChild = child->leftChild; child->leftChild = grandChild->rightChild; grandChild->rightChild = child; (*parent)->rightChild = grandChild->leftChild; grandChild->leftChild = *parent; switch(grandChild->bf){ case 1: (*parent)->bf = 0; child->bf = -1; break; case 0: (*parent)->bf = child->bf= 0; break; case -1: (*parent)->bf = 1; child->bf = 0; } *parent = grandChild; } (*parent)->bf = 0; *unbalancedp = FALSE; } void preprintree(treePointer ptr) { if(ptr == NULL) /* 为空树则返回 */ return ; printf(" %s ", ptr->data.key); if(ptr->leftChild != NULL) preprintree(ptr->leftChild); if(ptr->rightChild != NULL) preprintree(ptr->rightChild); } void inprintree(treePointer ptr) { if(ptr == NULL) /* 为空树则返回 */ return ; if(ptr->leftChild != NULL) inprintree(ptr->leftChild); printf(" %s ", ptr->data.key); if(ptr->rightChild != NULL) inprintree(ptr->rightChild); } void avlDelete(treePointer *parent, element x, int *unbalanced) { treePointer temp; treePointer* delp; if(!*parent){ *unbalanced = FALSE; printf("未查找到要删除的节点!\n"); return 0; } if(strcmp(x.key, (*parent)->data.key) == 0){ if(((*parent)->leftChild == NULL) && ((*parent)->rightChild == NULL)) { //情况1:无孩子 free(*parent); *parent = NULL; *unbalanced = TRUE; }else if(((*parent)->leftChild == NULL) && ((*parent)->rightChild != NULL)) { //情况2:无左孩子 temp = *parent; *parent = (*parent)->rightChild; free(temp); *unbalanced = TRUE; }else if(((*parent)->leftChild != NULL) && ((*parent)->rightChild == NULL)) { //情况3:无右孩子 temp = *parent; *parent = (*parent)->leftChild; free(temp); *unbalanced = TRUE; }else{ //情况4:有俩孩子 if((*parent)->leftChild->rightChild == NULL){//左孩无右孙 temp = *parent; *parent = (*parent)->leftChild; free(temp); *unbalanced = TRUE; }else{ //左孩有右孙 leftMaxNode(parent, &(*parent)->leftChild, unbalanced); if(*unbalanced) if((*parent)->leftChild->bf == -1){ (*parent)->leftChild->bf = 0; }else if((*parent)->leftChild->bf == 0){ (*parent)->leftChild->bf = 1; }else if((*parent)->leftChild->bf == 1){ leftRotation(&(*parent)->leftChild, unbalanced); } } } }else if(strcmp(x.key, (*parent)->data.key) < 0){ avlDelete(&(*parent)->leftChild, x, unbalanced); if(*unbalanced) if((*parent)->bf == 1){ (*parent)->bf = 0; }else if((*parent)->bf == 0){ (*parent)->bf = -1; }else if((*parent)->bf == -1){ rightRotation(parent, unbalanced); } }else if(strcmp(x.key, (*parent)->data.key) > 0){ avlDelete(&(*parent)->rightChild, x, unbalanced); if(*unbalanced) if((*parent)->bf == -1){ (*parent)->bf = 0; }else if((*parent)->bf == 0){ (*parent)->bf = 1; }else if((*parent)->bf == 1){ leftRotation(parent, unbalanced); } } } void leftMaxNode(treePointer *parent, treePointer *maxNode, int *unbalanced) { /* 与左子树最大元交换,并删除结点 */ if((*maxNode)->rightChild->rightChild == NULL){ treePointer temp; struct treeNode tempn; temp = *parent; tempn = *(*maxNode)->rightChild; *parent = (*maxNode)->rightChild; (*parent)->leftChild = temp->leftChild; (*parent)->rightChild = temp->rightChild; (*parent)->bf = temp->bf; (*maxNode)->rightChild = tempn.leftChild; free(temp); *unbalanced = TRUE; }else{ leftMaxNode(parent, &(*maxNode)->rightChild, unbalanced); if(*unbalanced) if((*maxNode)->bf == -1){ (*maxNode)->bf = 0; }else if((*maxNode)->bf == 0){ (*maxNode)->bf = 1; }else if((*maxNode)->bf == 1){ leftRotation(maxNode, unbalanced); } } }