时间限制: 1 Sec  内存限制: 128 MB

题目描述

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

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

输入

第一行输入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>
class Tree {
private:
    struct Node {
        int data;
        Node *leftChild, *rightChild;
        Node() = default;
        explicit Node(int data) : data(data), leftChild(nullptr), rightChild(nullptr) {}
    };
    Node *_root{};
    static void addRoot(int data, Node* parent) {
        if (data > parent->data) {
            if (parent->rightChild == nullptr) {
                parent->rightChild = new Node(data);
            } else {
                addRoot(data, parent->rightChild);
            }
        } else {
            if (parent->leftChild == nullptr) {
                parent->leftChild = new Node(data);
            } else {
                addRoot(data, parent->leftChild);
            }
        }
    }
    static int find(Node *root, int index, int *times) {
        (*times)++;
        if (root->data == index) {
            return *times;
        } else if (root->data < index) {
            if (root->rightChild == nullptr) {
                return -1;
            } else {
                return find(root->rightChild, index, times);
            }
        } else {
            if (root->leftChild == nullptr) {
                return -1;
            } else {
                return find(root->leftChild, index, times);
            }
        }
    }
    void print(Node *node) {
        if (node->leftChild != nullptr) {
            print(node->leftChild);
        }
        std::cout << node->data << " ";
        if (node->rightChild != nullptr) {
            print(node->rightChild);
        }
    }
public:
    explicit Tree(int data) {
        _root = new Node(data);
    }
    void addRoot(int data) {
        addRoot(data, _root);
    }
    void print() {
        print(_root->leftChild);
        std::cout << _root->data << " ";
        print(_root->rightChild);
        std::cout << std::endl;
    }
    int find(int index) {
        int times = 0;
        return find(_root, index, &times);
    }
};
int main() {
    size_t T;
    std::cin >> T;
    while (T--) {
        int size, data;
        std::cin >> size;
        std::cin >> data;
        Tree tree(data);
        for (int i = 1; i < size; ++i) {
            std::cin >> data;
            tree.addRoot(data);
        }
        tree.print();
        int count;
        std::cin >> count;
        while (count--) {
            int index;
            std::cin >> index;
            std::cout << tree.find(index) << std::endl;
        }
    }
}