3 实现算法
3.1 数据结构
template<typename T>struct BSTNode//平衡二叉树的结点类型结构体
{
T data;//结点数据类型
int bf;//结点的平衡因子，比二叉链表结点多此项
BSTNode<T>*lchild,*rchild;//左右孩子指针
};
3.2 算法
3.2．1 递归法
递归实现AVL树的节点删除的思想如下。
在AVL树T上删除值为E的节点步骤如下：
（1） 若树T为空，返回0退出否则到（2）;
（2） 比较T的数据和E，若相等跳到（3），若E小于T->data跳到（4），若E大于T->data则跳到（5）
（3） 分析T节点的类型
(3.1)若T是叶子节点则直接删除,树变矮即lower=1；
(3.2)若T只有右子树TR则将右子树节点的值赋给T，删除TR节点将T->rchild=NULL，lower=1;
(3.3)若T有左子树，则找到其中序遍历的前驱节点P，将P节点值用临时变量temp保存，并且用指针Tptr保存T；递归删除节点P；将Tptr所指节点即原T节点的值更新为temp；
（4）在左子树T->lchild中递归删除值为E的节点，若删除成功检查左子树是否变矮即lower的值是否为1；若lower=0返回0退出；若lower=1则进行失衡调整各种情况上文有分析
（5）在右子树T->rchild中递归删除值为E的节点，若删除成功检查左子树是否变矮即lower的值是否为1；若lower=0返回0退出；若lower=1则进行失衡调整，各种情况上文有分析
3.2．2 非递归法
非递归的算法思想如下。
在AVL树T上删除值为E的节点的步骤如下：
初始化一个栈s ;
（1） 若树T为空则返回0退出否则跳到(2);
（2） p为工作指针p=T;比较p的数据和E，若相等则跳到（3），若E小于p->data则跳到（4），若E大于p->data则跳到（5）
（3） 分析p节点的类型
（3.1）若p是叶子节点则直接删除，树变矮，
（3.1.1）若p是其父节点的左子树则lower=1;
（3.1.2）若p是其父节点的右子树则lower=2；
（3.2） 若p只有右子树pR则将右子树节点的值赋给p然后删除删除pR，树变矮，lower的值 和（3.1）一样分析，之后不再特别说明则都和（3.1）处理一样。
（3.3） 若p有左子树pL则将p和pL入栈,且用指针tempptr指向p即tempptr=p然后执行
q=TL ; While(q->rchild){q=q->rchild;s.push(q);}之后可以找到p的前驱节点q，将q的值赋给原p节点即tempptr->data=q->data，若q是叶子节点则直接删除否则将q的左子树代替q。树变矮且弹栈s.pop() ；然后执行如下循环体
（3.3.1）若栈不空且lower不为0则执行
a.弹栈 q=s.top();s.pop();及其q的父节点fa=s.top();
若fa=NULL则表明q是根节点则若要执行下面 b
或c时不用在给lower赋值了。
b.若lower=1 则表明左子树变矮，执行相应的失衡调整，并且调整过程中若导致q树变矮也得根据q为fa的左子树还是右子树将 lower=1或为lower=2；
c. 若lower=2 则表明右子树变矮，执行相应的失衡调整，并且调整过程中若导致q树变矮也得根据q为fa的左子树还是右子树将 lower=1或为lower=2；
退出循环后返回0退出；
（4）将p入栈且p=p->lchild;然后跳到（2）；
（5）将p入栈且p=p->rchild;然后跳到（2）；
