数据结构与算法课程设计---AVL TREE的实现及分析

（1）编写 AVL树判别程序，并判别一个二元查找树是否为 AVL树。二元查找树用其先序遍历结果表示，如：5，2，1，3，7，8。 （2）实现 AVL树的 ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二元查找树转变为 AVL树的操作。

#include 
#define LH +1
#define EH 0
#define RH -1
#define TRUE 1
#define FALSE 0

using namespace std;

const int SIZE = 1002;

int preOrder[SIZE] inOrder[SIZE];

struct Node
{
    int data;
    Node *lson;
    Node *rson;
};

typedef struct BSTnode
{
    int data;
    int bf;
    struct BSTnode *lchild*rchild;
}BSTnode*bstree;

int Delete（bstree &Tint e）//删除结点
{
    bstree pq;
    int shorter;
    e=0;
    p=T;
    if （!T->rchild） //右子数为空需要重接它的左子数
    {
        T=T->lchild;
        free（p）;
        shorter=true;
    }
    else if （!T->lchild） //重接它的右子数
    {
        T=T->rchild;
        free（p）;
        shorter=true;
    }
    else  //左右子数均不空
    {
        q=T->lchild;
        while （q->rchild!=NULL） //转左，然后向右到尽头
        {
            q=q->rchild;
        }
        e=q->data;
    }
    return e;
}

void Delete_Rightbalance（bstree &T）//删除在左子树上的，相当于插入在右子树
{
    bstree rc=T->rchildld;
    int shorter;
    switch （rc->bf）
    {
    case LH://双旋 ，先右旋后左旋
        ld=rc->lchild;
        rc->lchild=ld->rchild;
        ld->rchild=rc;
        T->rchild=rc->lchild;
        rc->lchild=T;
        switch （ld->bf）
        {
        case LH:
            T->bf=EH;
            rc->bf=RH;
            break;
        case EH:
            T->bf=rc->bf=EH;
            break;
        case RH:
            T->bf=LH;
            rc->bf=EH;
            break;
        }
        ld->bf=EH;
        T=rc;
        shorter=true;
        break;
    case EH:///////删除在左子树，相当于插入在右子树，左单旋
        T->rchild=rc->lchild;
        rc->lchild=T;
        rc->bf=LH;
        T->bf=RH;
        T=rc;
        shorter=EH;
        break;
    case RH:///////删除在左子树，相当于插入在右子树，左单旋
        T->rchild=rc->lchild;
        rc->lchild=T;
        rc->bf=T->bf=EH;
        T=rc;
        shorter=true;
        break;
    }
}

void Delete_Leftbalance（bstree &T）//删除右子树上的，相当于插入在左子树上
{
    bstree p1p2;
    int shorter;
    p1=T->lchild;
    switch （p1->bf）
    {
    case LH:
        T->lchild=p1->rchild;//右旋
        p1->rchild=T;
        p1->bf=T->bf=EH;
        T=p1;
        shorter=true;
        break;
    case EH:
        T->lchild=p1->rchild;//右旋
        p1->rchild=T;
        p1->bf=RH;
        T->bf=LH;
        T=p1;
        shorter=false;
        break;
    case RH:
        p2=p1->rchild;//右双旋
        p1->rchild=p2->lchild;
        p2->lchild=p1;
        T->lchild=p2->rchild;
        p2->rchild=T;
        switch （p2->bf）
        {
        case LH:
            T->bf=RH;
            p1->bf=EH;
            break;
        case EH:
            T->bf=EH;
            p1->bf=EH;
            break;
        case RH:
            T->bf=EH;
            p1->bf=LH;
            break;
        }
        p2->bf=EH;
        T=p2;
        shorter=true;
        break;
    }
}

bstree DeleteAVL（bstree &Tint e）//删除后要保证该二叉树还是平衡的
{
    int nm=0;//标记
    int shor