1738: 查找-二叉排序树
金币值：2
定数：11
时间限制：1.000 s
内存限制：128 M
正确：2
提交：2
正确率：100.00% 命题人：
题目描述
输入n个整数，从空开始建立一棵二叉排序树，每输入一个整数x，判断该数是否在该二叉排序树中，如果不在，则加入到二叉排序树中，如果在，则不加入到二叉排序树中；输入一个整数，判断该整数是否在这棵二叉排序树中，如果不在输出Not Found，否则输出该整数；中序遍历这棵二叉排序树得到一个有序的序列。
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct ElemType {
int key;
} ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void InsertBST(BiTree &T,ElemType e);
BiTree search(BiTree T,int key);
void Inorder(BiTree T);
void create_bsttree(BiTree &bt) {
int i,n;
ElemType e;
bt=NULL;
scanf("%d",&n);
for(i=1; i<=n; i++) {
scanf("%d",&e.key);
InsertBST(bt,e);
}
}
void visit(ElemType e) {
printf("%d ",e.key);
}
int main(void) {
BiTree bt;
create_bsttree(bt);
int key;
scanf("%d",&key);
BiTree p=search(bt,key);
if(p==NULL) printf("Not Found");
else visit(p->data);
printf("\n");
Inorder(bt);
return 0;
}
/*仅提交以下代码*/
void InsertBST(BiTree &T,ElemType e) {
}
BiTree search(BiTree T,int key){
}
void Inorder(BiTree T) {
}
输入格式
第1行输入一个整数表示建立的二叉排序树有n个整数。
第2行输入n个整数。
第3行输入一个整数。
第2行输入n个整数。
第3行输入一个整数。
输出格式
如果找到被查找的数，则第1行输出该整数，否则输出一个字符串Not Found。
第2行输出一个中序遍历此二叉排序树得到的有序序列，格式见样例（行末有空格）
第2行输出一个中序遍历此二叉排序树得到的有序序列，格式见样例（行末有空格）
输入样例 复制
8
10 18 3 8 12 2 7 4
12输出样例 复制
12
2 3 4 7 8 10 12 18提示
注意：题目中要求二叉排序树中不存在关键字值相同的结点