1.编写AVL树判别程序,并判别一个二元查找树是否为AVL树.二元查找树用其先序遍历结果表示,如:5,2,1,3,7,8
来源:学生作业帮 编辑:大师作文网作业帮 分类:综合作业 时间:2024/09/21 11:20:02
1.编写AVL树判别程序,并判别一个二元查找树是否为AVL树.二元查找树用其先序遍历结果表示,如:5,2,1,3,7,8.
2.实现AVL树的ADT,包括其上的基本操作:结点的加入和删除;另外包括将一般二元查找树转变为AVL树的操作.
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
#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
1.编写AVL树判别程序,并判别一个二元查找树是否为AVL树.二元查找树用其先序遍历结果表示,如:5,2,1,3,7,8
编写一个判别M是否为完数的函数,并编写主函数,通过调用此函数统计自然数1~100完数的个数
二叉树T,已知其前序遍历序列为1 2 4 3 5 7 6,中序遍历序列为4 2 1 5 7 3 6,其后序遍历序列为
编写程序,定义一个整数型一维数组,并存放5个数,查找并输出数组中的最大值和最小值.
根据树怎么判别方向`
编写一个函数primeNum(int x),功能是判别一个数是否为素数
判别级数是否收敛∑[(ln n)^2]/(n^3/2)用极限判别法判别它是否收敛,答案是收敛,同(n^5/4)比较,可是
数据结构折半查找的二叉查找树的问题
编写一个JAVA程序,求1!+2!+3!+.+10!的结果,并将结果输出
一、用图像法解下列二元一次方程组 二、用图像法判别下列方程是否有解?
给定数据序列d={7,16,4,8,20,9,6,18,5},构造一棵二叉排列数,并求出该二叉排列树查找成功的平均查找长
数理结构题!已知某棵二叉树的前序遍历结果为ABDEGCFHIJ