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);
}
}
}
没放头文件，直接在主函数前声明了
教材上介绍的也很简单：