题目描述
给出一个数据序列，建立二叉排序树，并实现查找功能
对二叉排序树进行中序遍历，可以得到有序的数据序列
输入
第一行输入t，表示有t个数据序列
第二行输入n，表示首个序列包含n个数据
第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第四行输入m，表示要查找m个数据
从第五行起，输入m行，每行一个要查找的数据，都是自然数
以此类推输入下一个示例
输出
第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到
从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1
以此类推输出下一个示例的结果
输入样例1
1 6 22 33 55 66 11 44 7 11 22 33 44 55 66 77
输出样例1
11 22 33 44 55 66 2 1 2 4 3 4 -1
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
struct Node{
int data;
Node*left=NULL;
Node*right=NULL;
};
class BST{
Node*root=NULL;
public:
void Insert(int&data){
Node*newOne=new Node();
newOne->data=data;
if(root==NULL){
root=newOne;
return;
}
Node*current=root;
while(current){
if(current->data>data){
if(current->left)
current=current->left;
else{
current->left=newOne;
return;
}
}
else{
if(current->right)
current=current->right;
else{
current->right=newOne;
return;
}
}
}
}
void Find(int&data){
int count=0;
Node*current=root;
while(current){
count ;
if(current->data==data){
cout<<count<<endl;
return;
}
if(current->data>data){
if(current->left)
current=current->left;
else{
cout<<"-1"<<endl;
return;
}
}
else{
if(current->right)
current=current->right;
else{
cout<<"-1"<<endl;
return;
}
}
}
}
void Traverse(Node*current){
if(current==NULL)
return;
Traverse(current->left);
cout<<current->data<<' ';
Traverse(current->right);
}
void Show(){
Traverse(root);
cout<<endl;
}
};
int main() {
int t,n,m,temp;
cin>>t;
while(t--){
BST test;
cin>>n;
while(n--){
cin>>temp;
test.Insert(temp);
}
test.Show();
cin>>m;
while(m--){
cin>>temp;
test.Find(temp);
}
}
return 0;
}
