Question

求数据结构课程设计——二叉排序树的实现

用顺序和二叉链表作存储结构
1) 以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
2) 对二叉排序树T作中序遍历，输出结果；
3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；

要可以直接出运行结果的完整程序，无法运行的就不要回答了。谢谢。

Answer 1

#include <iostream.h>
typedef int KeyType;
typedef char ElemType[10];
typedef struct tnode
{
KeyType key;
ElemType data;
struct tnode *lchild,*rchild;
}BSTNode;
void BSTdisp(BSTNode *b);
BSTNode *BSTSearch(BSTNode *bt,KeyType k)
{
BSTNode *p=bt;
while (p!=NULL && p->key!=k)
{
if (k<p->key)
p=p->lchild; /*沿左子树查找*/
else
p=p->rchild; /*沿右子树查找*/
}
return(p);
}
int BSTInsert(BSTNode *&bt,KeyType k)
{
BSTNode *f,*p=bt;
while (p!=NULL)
{
if (p->key==k)
return(0);
f=p; /*f指向*p结点的双亲结点*/
if (p->key>k)
p=p->lchild; /*在左子树中查找*/
else
p=p->rchild; /*在右子树中查找*/
}
p=new BSTNode; /*建立新结点*/
p->key=k;
p->lchild=p->rchild=NULL;
if (bt==NULL) /*原树为空时,*p作为根结点插入*/
bt=p;
else if (k<f->key)
f->lchild=p; /*插入*p作为*f的左孩子*/
else
f->rchild=p; /*插入*p作为*f的右孩子*/
return(1);
}
/*BSTNode *CreatBST(KeyType A[],int n)
//由数组中的关键字建立一棵二叉排序树
{
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while(i<n)
if(BSTInsert(bt,A[i])) //将A[i]插入二叉排序树T中
{
count<<" 第"<<i+1<<"步，插入:"<<A[i];
DispBST(bt); printf("\n");
i++;
}
return bt; //返回建立的二叉排序树的根指针
}*/
void CreateBST(BSTNode *&bt,KeyType str[],int n)
{
bt=NULL; /*初始时bt为空树*/
int i=0;
while (i<n)
{
BSTInsert(bt,str[i]); /*将关键字str[i]插入二叉排序树bt中*/
i++;
}
}

int BSTDelete(BSTNode *&bt,KeyType k)
{
BSTNode *p=bt,*f,*r,*f1;
f=NULL; /*p指向待比较的结点,f指向*p的双亲结点*/
while (p!=NULL && p->key!=k)/*查找值域为x的结点*/
{ f=p;
if (p->key>k)
p=p->lchild; /*在左子树中查找*/
else
p=p->rchild; /*在右子树中查找*/
}
if (p==NULL) /*未找到key域为k的结点*/
return(0);
else if (p->lchild==NULL) /**p为被删结点,若它无左子树*/
{
if (f==NULL) /**p是根结点,则用右孩子替换它*/
bt=p->rchild;
else if (f->lchild==p) /**p是双亲结点的左孩子,则用其右子替换它*/
{ f->lchild=p->rchild;
delete p;
}
else if(f->rchild==p) /**p是双亲结点的右孩子,则用其右孩子替换它*/
{ f->rchild=p->rchild;
delete p;
}
}
else if (p->rchild==NULL) /**p为被删结点,若它无右子树*/
{
if (f==NULL) /**p是根结点,则用左孩子替换它*/
bt=p->lchild;
if (f->lchild==p) /**p是双亲结点的左孩子,则用其左孩子替换它*/
{ f->lchild=p->lchild;
delete p;
}
else if(f->rchild==p) /**p是双亲结点的右孩子,则用其左孩子替换它*/
{ f->rchild=p->lchild;
delete p;
}
}
else /**p为被删结点,若它有左子树和右子树*/
{
f1=p;r=p->lchild; /*查找*p的左子树中的最右下结点*r*/
while (r->rchild!=NULL) /**r一定是无右子树的结点,*f1作为r的双亲*/
{ f1=r;
r=r->rchild;
}
if (f1->lchild==r) /**r是*f1的左孩子,删除*r*/
f1->lchild=r->rchild;
else if (f1->rchild==r) /**r是*f1的右孩子,删除*r*/
f1->rchild=r->lchild;
r->lchild=p->lchild; /*以下语句是用*r替代*p*/
r->rchild=p->rchild;
if (f==NULL) /**f为根结点*/
bt=r; /*被删结点是根结点*/
else if (f->lchild==p) /**p是*f的左孩子*/
f->lchild=r;
else /**p是*f的右孩子*/
f->rchild=r;
delete p;
}
return(1);
}
//先序遍历
/*void preorder(BSTNode *t)
{
if(t!=0)
{
cout<<t->key<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}*/
//中序遍历
void inorder(BSTNode *t)
{
if(t!=0)
{
inorder(t->lchild);
cout<<t->key<<" ";
inorder(t->rchild);
}
}
void BSTdisp(BSTNode *bt)
{
if(bt!=NULL)
{
cout<<bt->key;
if(bt->lchild !=NULL||bt->rchild !=NULL)
{
cout<<"(";
BSTdisp(bt->lchild );
if(bt->rchild !=NULL)
cout<<",";
BSTdisp(bt->rchild );
cout<<")";
}
}
}
void main()
{
int n;
BSTNode *bt=NULL,*p;
KeyType a[200],k;
cout <<"高国凯二叉排序树的实现请输入元素个数n:";
cin >>n;
cout <<"请输入数据以空格隔开:";

for(int i=0;i<n;i++)
{
cin >>a[i];
}
CreateBST(bt,a,n);
cout<<"BST:";
BSTdisp(bt);cout<<endl;
cout<<"中序遍历二叉排序树:"<<endl;
inorder(bt);
cout<<"\n";
// cout<<"先序遍历二叉排序树:";
// preorder(bt);
// cout<<"\n";

cout<<"输入要查找的元素x:";
cin >>k;
p=BSTSearch(bt,k);
if(p!=NULL)
{
BSTDelete(bt,k);
cout <<"已经删除值为"<<k<<"的结点"<<endl;
cout<<"删除X后的BST:";
BSTdisp(bt);cout<<endl;
cout<<"中序遍历二叉排序树:";
inorder(bt);
cout<<endl;
}
else
cout<<"无"<<k<<"\n";
}

Answer 2

#include "stdio.h"
#include "stdlib.h"

typedef int DataType;

typedef struct OrderTree
{
DataType data;
struct OrderTree *lchild;
struct OrderTree *rchild;
}BigTree,*PTree;

void InsertANode(PTree *aTree,DataType dat)
{
if(*aTree == NULL)
{
PTree helpNode;
helpNode = (PTree)malloc(sizeof(BigTree));
helpNode->data = dat;
helpNode->lchild = helpNode->rchild = NULL;
*aTree = helpNode;
}
else if(dat < (*aTree)->data)
InsertANode(&((*aTree)->lchild),dat);
else
InsertANode(&((*aTree)->rchild),dat);
}

PTree TreeSearch(PTree aTree,DataType dat)
{
if(aTree == NULL)
return NULL;
if(aTree->data == dat)
return aTree;
if(aTree->data > dat)
return TreeSearch(aTree->lchild,dat);
if(aTree->data < dat)
return TreeSearch(aTree->rchild,dat);
}

void DelANode(PTree *aTree,DataType dat)
{
PTree helpPointer,fatherPointer;
PTree BigRightNode,help2Pointer;
helpPointer = *aTree;
fatherPointer = NULL;
while(helpPointer && helpPointer->data != dat)
{
fatherPointer = helpPointer;
if(helpPointer->data > dat)
helpPointer = helpPointer->lchild;
else
helpPointer = helpPointer->rchild;
}
if(helpPointer == NULL)
{
printf("无此节点!\n");
return;
}
if(helpPointer->lchild == NULL)
{
if(fatherPointer ==NULL)
*aTree = helpPointer->rchild;
else if(fatherPointer->lchild == helpPointer)
fatherPointer->lchild = helpPointer->rchild;
else
fatherPointer->rchild = helpPointer->rchild;
}
else
{
BigRightNode = helpPointer;
help2Pointer = helpPointer->lchild;
while(help2Pointer->rchild)
{
BigRightNode = help2Pointer;
help2Pointer = help2Pointer->rchild;
}
if(BigRightNode == helpPointer)
BigRightNode->lchild = help2Pointer->lchild;
else
BigRightNode->rchild = help2Pointer->lchild;
helpPointer->data = help2Pointer->data;
free(help2Pointer);
return;
}
}

void OutTree(PTree aTree)
{
if(aTree)
{
OutTree(aTree->lchild);
printf(" %d ",aTree->data);
OutTree(aTree->rchild);
}
}

void main()
{
PTree aTree;
aTree = NULL;
int dat,number;
printf("输入二叉排序树中的节点数:");
scanf("%d",&number);
for(int i = 1;i <= number;i++)
{
printf("输入第%d个元素:",i);
scanf("%d",&dat);
InsertANode(&aTree,dat);
}
OutTree(aTree);
printf("\n输入要删除的数:");
scanf("%d",&dat);
DelANode(&aTree,dat);
OutTree(aTree);
}

追问

有错误、
fatal error C1004: unexpected end of file found