AVL树的节点声明：
typedef int ElementType;#ifndef _AvlTree_Hstruct AvlNode;typedef struct AvlNode *Position;typedef struct AvlNode *AvlTree;AvlTree MakeEmpty(AvlTree T);Position Find(ElementType X,AvlTree T);Position FindMin(AvlTree T);Position FindMax(AvlTree T);AvlTree Insert(ElementType X,AvlTree T);AvlTree Delete(ElementType X,AvlTree T);ElementType Retrieve(Position P);#endifstruct AvlNode{ ElementType Element; AvlTree Left; AvlTree Right; int Height;}; 下面只是写出了Insert函数以及它调用的函数的程序：
static int Height(Position P){ if(P==NULL) return -1; else return P->Height;}static Position SingleRotateWithLeft(Position K2){ Position K1; K1=K2->Left; K2->Left=K1->Right; K1->Right=K2; K2->Height=Max(Height(K2->Left), Height(K2->Right))+1; K1->Height=Max(Height(K1->Left), K2->Height)+1; return K1;}static Position SingleRotateWithRight(Position K2){ Position K1; K1=K2->Right; K2->Right=K1->Left; K1->Left=K2; K2->Height=Max(Height(K2->Left),Height(K2->Right))+1; K1->Height=Max(K2->Height,Height(K1->Right))+1; return K1;}static Position DoubleRotateWithLeft(Position K3){ K3->Left=SingleRotateWithRight(K3->Left); return SingleRotateWithLeft(K3);}static Position DoubleRotateWithRight(Position K3){ K3->Right=SingleRotateWithLeft(K3->Right); return SingleRotateWithRight(K3);}AvlTree Insert(ElementType X,AvlTree T){ if(T==NULL) { T=malloc(sizeof(struct AvlNode)); if(T==NULL) { printf("Out of space !\n"); } p->Element=X; p->Left=NULL; p->Right=NULL; p->Height=0; } else { if(X < T->Element ) { T->Left=Insert(X,T->Left); if(Height(T->Left)-Height(T->Right)==2) { if(X < T->Left->Element) T=SingleRotateWithLeft(T); else T=DoubleRotateWithLeft(T); } } else if(X > T->Element ) { T->Right=Insert(X,T->Right); if(Height(T->Right)-Height(T->Left)==2) { if(X > T->Right->Element) T=SingleRotateWithRight(T); else T=DoubleRotateWithRight(T); } } } T->Height=Max(Height(T->Left),Height(T->Right))+1; return T;} 在上面的Insert程序中，if(X < T->Element) 和 else if(X > T->Element)的内容是我没有写出来的，也就是几乎整个程序都没写出来。这个函数是需要谨记的！！！
仔细看这个程序的话，就会发现不是表面上看上去的那么简单！
递归调用Insert函数，接下来如果调整树。最先调整的是，距离插入节点到根的路径上，最先出现不平衡的那个子树。然后检验往上的路径中的子树是否是平衡的。
以上是书上的一个递归Insert程序。
下面是我自己写的一个非递归Insert程序：
AvlTree Insert(ElementType X,AvlTree T){ Position q=malloc(sizeof(struct AvlNode)); if(q==NULL) { printf("malloc space fail !\n"); return T; } q->Element=X; q->Left=NULL; q->Right=NULL; q->Height=0; if(T==NULL) return q; if(Find(X,T)) return T; Position p=T; while(p!=NULL) { if(X < p->Element ) { p->Height=0; Push(p,s); p=p->Left; } else if(X > p->Element ) { p->Height=1; Push(p,s); p=p->Right; } } p=TopAndPop(s); int i=2, first, second=p->Height; if(p->Height==0) { p->Left=q; p->Height=1; } else p->Right=q; Position tmp; while(!IsEmpty(s)) { p=TopAndPop(s); first=p->Height; p->Height=i; if(first==0) { if(Height(p->Left)-Height(p->Right)==2) { if(second==0) tmp=SingleRotateWithLeft(p); else tmp=DoubleRotateWithLeft(p); if(IsEmpty(s)) { p=tmp; } else { p=Top(Stack(s)); if(p->Height==0) p->Left=tmp; else p->Right=tmp; } } } else { if(Height(p->Right)-Height(p->Left)==2) { if(second==1) tmp=SingleRotateWithRight(p); else tmp=DoubleRotateWithRight(p); if(IsEmpty(s)) { p=tmp; } else { p=Top(Stack(s)); if(p->Height==0) p->Left=tmp; else p->Right=tmp; } } } second=first; i++; } return p;} 这个非递归程序的思想是这样的：
创建一个Position节点q，将Insert函数参数中的X放进去。
先判断函数的参数T是否为NULL，若是，那就返回q。
查找AVL树T中是否有元素X，若有，返回T；
第18行到33行，查找元素X的位置。从根到元素位置的路径上经过的每个节点p(包括根节点，但不包括元素X所在的节点)：如果元素在它左边，这个节点的p->Height=0；如果元素在它右边，这个节点的p->Height=1， p入栈。
第35到43行，将元素X插入到正确位置，它的父节点为p，且p->Height=1。
从45行到98行，将栈s中的指针依次出栈。用i表示出栈的对应节点p的Height的值，first=0表示元素X在p的左子树上，first=1表示元素X在p的右子树上。second=0表示元素X在p的儿子的左子树上，second=1表示元素X在p的儿子的右子树上。 对于出栈的每个节点p，检查是否平衡。如果不平衡，根据first和second调用相应的单旋转或双旋转使子树p平衡。并且，根据节点p的父亲的Height值，使平衡后的子树p重新成为它父亲的对应儿子( p的父亲的Height=0，那么p在平衡前是左儿子，平衡后也应该成为左儿子)。