AVL树的介绍见http://blog.csdn.net/pngynghay/article/details/22443525，本文给出的是AVL树的一种实现。
采用非递归方式，效率较好，经过常规测试。
#include
#include
#include
#include
#include
typedef enum { EH = 0, LH = 1, RH = -1 }bh_t; typedef enum { FALSE = 0, TRUE = 1 }bool_t; typedef int ElemType; typedef struct BSTNode { ElemType key; int bf; struct BSTNode *lchild,*rchild,*parent; }BSTNode,*BSTree; bool_t searchAVL(BSTree root,ElemType key, BSTNode **parent) { BSTNode *tmp = NULL; assert(root != NULL); *parent = root->parent; tmp = root; while(NULL != tmp) { if(tmp->key == key) { return TRUE; } *parent = tmp; if(tmp->key > key) { tmp = tmp->lchild; } else { tmp = tmp->rchild; } } return FALSE; } /* get the minimum node*/ BSTNode* minNode(BSTNode* root) { if (root == NULL) { return NULL; } while (root->lchild != NULL) { root = root->lchild; } return root; } /* get the maximum node*/ BSTNode* maxNode(BSTNode* root) { if (root == NULL) { return NULL; } while (root->rchild != NULL) { root = root->rchild; } return root; } /* get the previous node*/ BSTNode* preNode(BSTNode* target) { if (target == NULL) { return NULL; } if (target->lchild != NULL) { return maxNode(target->lchild); } while ((target->parent!=NULL) && (target!=target->parent->rchild)) { target = target->parent; } return target->parent; } /* get the next node*/ BSTNode* nextNode(BSTNode* target) { if (target == NULL) { return NULL; } if (target->rchild != NULL) { return minNode(target->rchild); } while ((target->parent!=NULL) && (target!=target->parent->lchild)) { target = target->parent; } return target->parent; } BSTNode* leftbalance(BSTNode* root, BSTNode* parent, BSTNode* child) { BSTNode *cur; assert((parent != NULL)&&(child != NULL)); /* LR */ if (child->bf == RH) { cur = child->rchild; cur->parent = parent->parent; child->rchild = cur->lchild; if (cur->lchild != NULL) { cur->lchild->parent = child; } parent->lchild = cur->rchild; if (cur->rchild != NULL) { cur->rchild->parent = parent; } cur->lchild = child; cur->rchild = parent; child->parent = cur; if (parent->parent != NULL) { if (parent->parent->lchild == parent) { parent->parent->lchild = cur; } else { parent->parent->rchild = cur; } } else { root = cur; } parent->parent = cur; if (cur->bf == EH) { parent->bf = EH; child->bf = EH; } else if (cur->bf == RH) { parent->bf = EH; child->bf = LH; } else { parent->bf = RH; child->bf = EH; } cur->bf = EH; } /* LL */ else { child->parent = parent->parent; parent->lchild = child->rchild; if (child->rchild != NULL) { child->rchild->parent = parent; } child->rchild = parent; if (parent->parent != NULL) { if (parent->parent->lchild == parent) { parent->parent->lchild = child; } else { parent->parent->rchild = child; } } else { root = child; } parent->parent = child; /* when insert */ if (child->bf == LH) { child->bf = EH; parent->bf = EH; } /* when delete*/ else { child->bf = RH; parent->bf = LH; } } return root; } BSTNode* rightbalance(BSTNode* root, BSTNode* parent, BSTNode* child) { BSTNode *cur; assert((parent != NULL)&&(child != NULL)); /* RL */ if (child->bf == LH) { cur = child->lchild; cur->parent = parent->parent; child->lchild = cur->rchild; if (cur->rchild != NULL) { cur->rchild->parent = child; } parent->rchild = cur->lchild; if (cur->lchild != NULL) { cur->lchild->parent = parent; } cur->lchild = parent; cur->rchild = child; child->parent = cur; if (parent->parent != NULL) { if (parent->parent->lchild == parent) { parent->parent->lchild = cur; } else { parent->parent->rchild = cur; } } else { root = cur; } parent->parent =