#include
#include
#define MaxSize 100
#include"BST.h"
void main()
{
int T;
int data[MaxSize],i=0,num,j,choice,s;
printf("请先输入空格符,再输入所要测试的序列T:\n");
while((getchar())!='\n')
{
scanf("%d",&num);
data[i]=num;
i++;
}
T=Create(data,i);
printf("指令菜单如下:");
printf("\n 0: exit");
printf("\n 1中序遍历:");
printf("\n 2:查找成功的平均查找长度:");
printf("\n 3:删除:");
while(choice)
{
printf("\n choose the opperation to continue\n");
scanf("%d",&choice);
switch(choice)
{
case 0: exit(0);
case 1: printf("\n此二叉排序树中序遍历结果为:");
InorderTraverse(T,1);
break;
case 2:
s=0;
computeASL(T,1,&s,0);
printf("\n二叉排序树T查找成功的平均查找长度:ASL=%d/%d",s,i);
break;
case 3:
printf("输入你要删除的数据元素:");
scanf("%d",&num);
j=Search(T,num,1);
if(j)
{
T=Delete(T,num);
printf("删除后,序列T的中序遍历结果:");
InorderTraverse(T,1);
}
else
printf("此二叉排序树中无数据元素x\n");
break;
}
}
}
int Insert(BiTreeNode **root,int item) //插入
{
BiTreeNode *current,*parent=NULL,*p;
current= *root;
while(current != NULL)
{
if(current->data == item)
return 0;
parent=current;
if(current->data < item)
current = current->rightChild;
else
current= current->leftChild;
}
p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
if(p==NULL)
{
printf("空间不够!");
exit(1);
}
p->data = item;
p->leftChild = NULL;
p->rightChild = NULL;
if(parent == NULL)
*root = p;
else if(item< parent->data)
parent->leftChild =p;
else
parent->rightChild =p;
return 1;
}
int Search(BiTreeNode *root,int item)
{
BiTreeNode *p;
if(root!=NULL)
{
p=root;
while(p!=NULL)
{
if(p->data == item)
return 1;
if(item>p->data)
p=p->rightChild;
else
p=p->leftChild;
}
}
return 0;
}
void InorderTraverse(BiTreeNode *root) //中序遍历显示
{
if(root == NULL)
return;
if(root->leftChild != NULL)
InorderTraverse(root->leftChild);
printf("%d ",root->data);
if(root->rightChild !=NULL)
InorderTraverse(root->rightChild);
}
BiTreeNode* Delete(BiTreeNode *root,int x) //删除操作
{
BiTreeNode *s,*curr,*f,*q;
int flag=0;
curr=root;
while((curr!=NULL)&&(!flag)) //找到要删除的结点
{
if(curr->data==x)
flag=1;
else if(x<curr->data)
{
f=curr; //记住双亲的指针
curr=curr->leftChild;
}
else
{
f=curr;
curr=curr->rightChild;
}
}
if(flag)
{
if(curr->leftChild==NULL&&curr->rightChild==NULL) //左右子树都为空
{
if(curr==root)
{
free(curr);
root=NULL;
}
else
{
if(curr==f->leftChild)
{
free(curr);
f->leftChild=NULL;
}
else
{
free(curr);
f->rightChild=NULL;
}
}
}
else if(curr->leftChild==NULL&&curr->rightChild!=NULL) //左子树为空
{
if(curr==root)
{
root=curr->rightChild;
free(curr);
}
else
{
s=curr->rightChild;
if(curr==f->leftChild) //判断要删除结点是双亲结点的左子树还是右子树
f->leftChild=s;
else
f->rightChild=s;
free(curr);
}
}
else if(curr->rightChild==NULL&&curr->leftChild!=NULL) //右子树为空
{
if(curr==root)
{
root=curr->leftChild;
free(curr);
}
else
{
s=curr->leftChild;
if(curr==f->leftChild) //判断要删除结点是双亲结点的左子树还是右子树
f->leftChild=s;
else
f->rightChild=s;
free(curr);
}
}
else //左,右子树都有
{
q=curr;
s=curr->rightChild;
while(s->leftChild!=NULL)
{
q=s;
s=s->leftChild;
}
curr->data=s->data;
if(curr=q)
{
if(s->rightChild==NULL)
{
free(s);
q->rightChild=NULL;
}
else
{
q->rightChild=s->rightChild;
free(s);
}
}
else
{
if(s->rightChild==NULL)
{
free(s);
q->leftChild=NULL;
}
else
{
q->leftChild=s->rightChild;
free(s);
}
}
}
}
else
printf("此二叉排序树为空");
return root;
}
#include
#include
#include"math.h"
#define MaxSize 100
typedef struct node
{
int data;
struct node *leftChild;
struct node *rightChild;
}BiTreeNode;
#include "BiTree.h"
void main()
{
int T[MaxSize],x,choice;
int i=0,n;
double ASL;
BiTreeNode *root =NULL;
printf("请先输入一个空格符,再输入所要测试的序列T:\n"); //getchar()函数的要求
while((getchar()) !='\n') //以\n作为输入结束的标志
{
scanf("%d",&T[i]);
i++;
}
n=i;
for(int j=0;j<n;j++)
Insert(&root,T[j]);
printf("指令菜单如下:");
printf("\n 0: exit");
printf("\n 1中序遍历:");
printf("\n 2:查找成功的平均查找长度:");
printf("\n 3:删除:");
while(choice)
{
printf("\n choose the opperation to continue\n");
scanf("%d",&choice);
switch(choice)
{
case 0: exit(0);
case 1: printf("\n此二叉排序树中序遍历结果为:");
InorderTraverse(root);
break;
case 2:
ASL=(log10(n+1))/(log10(2));
printf("\n二叉排序树T查找成功的平均查找长度:%f\n",ASL);
break;
case 3:
printf("输入你要删除的数据元素:");
scanf("%d",&x);
if(Search(root,x))
{
root=Delete(root,x);
printf("删除后,序列T的中序遍历结果:");
InorderTraverse(root);
}
else
printf("此二叉排序树中无数据元素%d\n",x);
break;
}
}
}
typedef struct
{
int *data;
int size;
}BST;
void Insert(BST T,int i,int key)
{
if(iMaxSize)
printf("overflow!");
if(T.data[i]==-1)
T.data[i]=key;
else if(key
Insert(T,2*i,key);
else if(key>T.data[i])
Insert(T,2*i+1,key);
}
BST Create(int *data,int num)
{
BST T;
T.data=(int *)malloc(MaxSize*sizeof(int)); //动态申请数组空间
for(int j=0;j<MaxSize;j++)
T.data[j]=-1;
T.size=0; //初始化
for(int i=0;i<num;i++)
{
Insert(T,1,data[i]);
T.size++;
}
return T;
}
void InorderTraverse(BST T,int i)
{
if(T.data[i]>=0)
{
InorderTraverse(T,2*i);
printf("%d ",T.data[i]);
InorderTraverse(T,2*i+1);
}
}
int Search(BST T,int key,int i)
{
if(T.data[i]==-1)
return 0;
else if(key==T.data[i])
return 1;
else if(key<T.data[i])
Search(T,key,2*i);
else
Search(T,key,2*i+1);
}
BST Delete(BST T,int key)
{
BST Q;
Q.data=(int *)malloc(MaxSize*sizeof(int));
for(int i=0;i
Q.data[i]=-1;
for(i=1;i0;i++)
{
if(T.data[i]==-1||T.data[i]==key)
continue;
Insert(Q,1,T.data[i]);
T.size--;
Q.size++;
}
return Q;
}
computeASL(BST T,int i,int *s,int j) //计算平均查找长度
{
if(T.data[i]!=-1)
{
j++; //j记录当前结点的在当前树中的深度
*s=*s+j; //记录已遍历过的点的深度之和
if(computeASL(T,2*i,s,j)) //计算左子树的ASL
{
if(computeASL(T,2*i+1,s,j)) //计算右子树的ASL
{j--; return 1;}
}
}
else
return 1;
}