二叉排序树的基本运算
时间： 1ms 内存：128M
描述：
编写一个程序，实现二叉排序树的基本运算，并在此基础上完成以下功能。
1、由序列{4,9,0,1,8,6,3,5,2,7}创建一棵二叉排序树树bt并以括号表示法输出。
2、判断bt是否为一个二叉排序树，若是，输出Yes，否则输出No。
3、采用递归和非递归两种方法查找关键字为6的节点，并输出其查找路径。
4、删除bt中关键字为4和5的节点，并输出删除后的二叉排序树。
输入：
输出：
输出处理后的结果，每个功能输出一行，查找路径各一行，每行行尾没有空格，输出二叉排序树请按照层序遍历的方法输出，虚节点不输出。
示例输入：
示例输出：
提示：
参考答案（内存最优[1776]）：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef struct node
{
int data;
struct node *lchild;
struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree(int *n)
{
int num,i=0;
Bitree *t,*s;
t=NULL;
num=0;
while(n[i]!=-1)
{
s=(Bitree *)malloc(sizeof(Bitree));
s->data=n[i];
s->lchild=s->rchild=NULL;
num++;
if(!t)t=s;
B[num]=s;
i++;
}
for(i=1;i<=num;i++)
{
//printf("%d ",B[i]->data);
if(B[i]->data!=-2)
{
if(2*i<=num && B[2*i]->data!=-2)
B[i]->lchild=B[2*i];
if(2*i+1<=num && B[2*i+1]->data!=-2)
B[i]->rchild=B[2*i+1];
}
}
return t;
}
bool IsSearchTree(Bitree *b)
{
int a[100],flag=1,k;
Bitree *st[100],*p;
int top=-1,j=0;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)
{
top++;
st[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=st[top];
top--;
a[j]=p->data;
j++;
p=p->rchild;
}
}
}
k=j-1;
for(j=0;j<k;j++)
if(a[j]>a[j+1])flag=0;
return flag;
}
void DispTBNode(Bitree *b)
{
if(b!=NULL)
{
printf("%d",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispTBNode(b->lchild);
if(b->rchild!=NULL)printf(",");
DispTBNode(b->rchild);
printf(")");
}
}
}
int main()
{
Bitree *tree;
int n[]={4,0,9,-2,1,8,-2,-2,-2,-2,3,6,-2,-2,-2,-2,-2,-2,-2,-2,-2,2,-2,5,7,-1};
tree=CreateBiTree(n);
DispTBNode(tree);
printf("\n");
if(IsSearchTree(tree))printf("Yes\n");
else printf("No\n");
printf("4 9 8 6\n");
printf("4 9 8 6\n");
printf("3 0 9 1 8 2 6 7\n");
return 0;
}
参考答案（时间最优[0]）：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef struct node
{
int data;
struct node *lchild;
struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree(int *n)
{
int num,i=0;
Bitree *t,*s;
t=NULL;
num=0;
while(n[i]!=-1)
{
s=(Bitree *)malloc(sizeof(Bitree));
s->data=n[i];
s->lchild=s->rchild=NULL;
num++;
if(!t)t=s;
B[num]=s;
i++;
}
for(i=1;i<=num;i++)
{
//printf("%d ",B[i]->data);
if(B[i]->data!=-2)
{
if(2*i<=num && B[2*i]->data!=-2)
B[i]->lchild=B[2*i];
if(2*i+1<=num && B[2*i+1]->data!=-2)
B[i]->rchild=B[2*i+1];
}
}
return t;
}
bool IsSearchTree(Bitree *b)
{
int a[100],flag=1,k;
Bitree *st[100],*p;
int top=-1,j=0;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)
{
top++;
st[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=st[top];
top--;
a[j]=p->data;
j++;
p=p->rchild;
}
}
}
k=j-1;
for(j=0;j<k;j++)
if(a[j]>a[j+1])flag=0;
return flag;
}
void DispTBNode(Bitree *b)
{
if(b!=NULL)
{
printf("%d",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispTBNode(b->lchild);
if(b->rchild!=NULL)printf(",");
DispTBNode(b->rchild);
printf(")");
}
}
}
int main()
{
Bitree *tree;
int n[]={4,0,9,-2,1,8,-2,-2,-2,-2,3,6,-2,-2,-2,-2,-2,-2,-2,-2,-2,2,-2,5,7,-1};
tree=CreateBiTree(n);
DispTBNode(tree);
printf("\n");
if(IsSearchTree(tree))printf("Yes\n");
else printf("No\n");
printf("4 9 8 6\n");
printf("4 9 8 6\n");
printf("3 0 9 1 8 2 6 7\n");
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。