1.编写AVL树判别程序,并判别一个二元查找树是否为AVL树.二元查找树用其先序遍历结果表示,如：5,2,1,3,7,8

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

#include
#include
using namespace std;
#define max(a,b) ((a>b)?(a):(b))//最大值
#define geth(a) ((a)?a->h:0)//得到高度
//编译器 VC6.0
class node
{
public:
int data;//数据域
int h;//高度
node *left,*right,*parent;//指针域,带父指针
node(int d,int hh=1,node *l=NULL,node *r=NULL,node *p=NULL):data(d),h(hh),left(l),right(r),parent(p){}//构造
};
class avl
{
public:
node *root;//根节点
avl(){root=NULL;}
avl(){}//没写
void insert(int data);//插入
void spinleft(node *p);//左旋
void spinright(node *p);//右旋,这里的左旋和右旋都是单旋
void spin(node *p);//这个是判断单旋还是双旋
void print();//输入
void del(int data);//删除
};
void avl::insert(int data)
{
node *x=root;
node *y=NULL;
while(x)
{
y=x;
if(x->data>=data)
x=x->left;
else
x=x->right;
}
node *p=new node(data);
if(y==NULL)
root=p;
else
{
if(y->data>=data)
y->left=p;
else
y->right=p;
p->parent=y;
}
p->h=1;//新插入的节点高度肯定为1;;
node *z=p->parent;
while(z)//向上查找不平衡节点
{
int f=geth(z->left)-geth(z->right);
if(f==2||f==-2)
spin(z);//找到并不停止,为了修改上层节点的高度h,
z->h=max(geth(z->left),geth(z->right))+1;
z=z->parent;
}
}
void avl::del(int data)
{
node *p=root;
while(p&&p->data!=data)
{
if(p->data>data)
p=p->left;
else
p=p->right;
}
if(p==NULL)
{
coutleft;
if(replace->left)
replace->left->parent=p;
}
else
{
replace->parent->right=replace->left;
if(replace->left)
replace->left->parent=replace->parent;
}//以上是寻找replace,下面是replace和它的左右孩子连接
replace->left=p->left;
if(p->left)
p->left->parent=replace;
replace->right=p->right;
if(p->right)
p->right->parent=replace;
}
node *z;//记录回溯起始节点
if(replace)
{
z=replace->parent;
if(z==p)
z=replace;
}
else
z=p->parent;
if(p->parent==NULL)//下面是replace与其父节点连接
{
root=replace;
if(replace)
replace->parent=NULL;
}
else
{
if(p->parent->left==p)
p->parent->left=replace;
else
p->parent->right=replace;
if(replace)
replace->parent=p->parent;
}
delete p;
if(z)
z->h=max(geth(z->left),geth(z->right))+1;
while(z)//向上查找不平衡节点
{
int f=geth(z->left)-geth(z->right);
if(f==2||f==-2)
spin(z);
z->h=max(geth(z->left),geth(z->right))+1;
z=z->parent;
}
}
void avl::spinleft(node *p)
{
node *temp=p->parent;//p的父节点
node *temp1=p->left;
node *temp2=p->left->right;
if(temp==0)//p为根节点
{
root=temp1;
temp1->parent=NULL;
}
else
{
if(p==temp->right)//确定p与父亲的关系
temp->right=temp1;
else
temp->left=temp1;
temp1->parent=temp;
}
temp1->right=p;//各种指针交换
p->parent=temp1;
p->left=temp2;
if(temp2)
temp2->parent=p;
p->h=max(geth(p->left),geth(p->right))+1;//重置节点高度,只有 有孩子发生变化的节点高度才可能改变,
temp1->h=max(geth(temp1->left),geth(temp1->right))+1;
}
void avl::spinright(node *p)
{
node *q=p->parent;
node *temp1=p->right;
node *temp2=p->right->left;
if(q==0)
{
root=temp1;
temp1->parent=NULL;
}
else
{
if(p==q->right)
q->right=temp1;
else
q->left=temp1;
temp1->parent=q;
}
temp1->left=p;
p->parent=temp1;
p->right=temp2;
if(temp2)
temp2->parent=p;
p->h=max(geth(p->left),geth(p->right))+1;
temp1->h=max(geth(temp1->left),geth(temp1->right))+1;
}
void avl::spin(node *p)//根据节点左高还是右高 以及其对应孩子 是左高还是右高 来确定怎样旋转,
{
if(geth(p->left)>geth(p->right))//左高
{
node *q=p->left;
if(geth(q->left)>=geth(q->right))//删除节点时这里可能出现=号,处理方法是尽量单旋,下同
spinleft(p);
else
{
spinright(q);
spinleft(p);
}
}
else
{
node *q=p->right;
if(geth(p->left)right))
spinright(p);
else
{
spinleft(q);
spinright(p);
}
}
}
void avl::print()//按层次输出,
{
queueq;
q.push(root);
node *p=root;
while(p&&!q.empty())
{
p=q.front();
q.pop();
cout