题目描述

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

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

输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要查找m个数据

从第五行起，输入m行，每行一个要查找的数据，都是自然数

以此类推输入下一个示例

输出

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

从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1

以此类推输出下一个示例的结果

样例输入

1 6 22 33 55 66 11 44 7 11 22 33 44 55 66 77

样例输出

11 22 33 44 55 66 2 1 2 4 3 4 -1

#include <iostream>
using namespace std;
class BSTNode {
public:
    int data;
    BSTNode* LeftChild;
    BSTNode* RightChild;
    BSTNode() :LeftChild(NULL), RightChild(NULL) {};
};
class BST {
private:
    BSTNode* Root;
public:
    BST() {};
    ~BST() {};
    void Create();
    void Inorder();//用于外部调用
    void Insert();
private:
    void Inorder(BSTNode* t);
};
void BST::Inorder() {
    BSTNode* t = Root;
    Inorder(t);
}
void BST::Create()     //创建排序树
{
    int n;
    cin >> n;
    Root = new BSTNode();
    cin >> Root->data;
    for (int i = 0; i < n - 1; i++)
    {
        Insert();//与insert方法相同直接借用
    }
}
void BST::Inorder(BSTNode* t)//先序
{
    if (t == NULL)
        return;
    Inorder(t->LeftChild);
    cout << t->data << ' ';
    Inorder(t->RightChild);
}
void BST::Insert()            //插入操作
{
    int data;
    cin >> data;
    BSTNode* temp;
    temp = Root;
    while (1)
    {
        if (temp->data > data)
        {
            if (temp->LeftChild != NULL)        //比temp大，且temp的左孩子不为空
                temp = temp->LeftChild;
            else                              //temp的左孩子为空时
            {
                BSTNode* lc = new BSTNode();
                temp->LeftChild = lc;
                lc->data = data;
                break;
            }
        }
        else
        {
            if (temp->RightChild != NULL)        //比temp小，且temp的右孩子不为空
                temp = temp->RightChild;
            else                               //temp的右孩子为空时
            {
                BSTNode* rc = new BSTNode();
                temp->RightChild = rc;
                rc->data = data;
                break;
            }
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        BST t;
        t.Create();
        t.Inorder();
        cout << endl;
        int m;
        cin >> m;
        while (m--)
        {
            t.Insert();
            t.Inorder();
            cout << endl;
        }
    }
}