DS二叉排序树之查找

题目描述

给出一个数据序列，建立二叉排序树，并实现查找功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入

第一行输入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代码

#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;
}