A : DS二叉排序树之查找

Description

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

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

Input

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

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

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

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

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

以此类推输入下一个示例

Output

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

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

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

Sample

#0

Input

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

Output

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

AC代码

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int value) {
    //遇到空了就开一块把value塞进去
    if (root == nullptr) {
        return new TreeNode(value);
    }
    // value小于当前根的data则向左孩子方向递归
    if (value < root->data) {
        root->left = insert(root->left, value);
    }
    // 反之向右
    else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

// 中序遍历输出有序序列
void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

// 查找节点
int search(TreeNode* root, int value, int& count) {
    count = 0;//查找次数
    TreeNode* current = root;

    while (current != nullptr) {
        count++;

        if (value == current->data) {//找到了直接退出
            return count;
        }
        else if (value < current->data) {
            current = current->left;
        }
        else {
            current = current->right;
        }
    }

    return -1; // 查找失败
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;

        TreeNode* root = nullptr;

        // 迭代n次将每一个value插入到树中
        for (int j = 0; j < n; ++j) {
            int value;
            cin >> value;
            root = insert(root, value);
        }

        // 中序遍历输出有序序列
        //cout << "Case #" << i + 1 << endl;
        inorderTraversal(root);
        cout << endl;

        int m;
        cin >> m;

        for (int k = 0; k < m; ++k) {
            int target;
            cin >> target;

            int count;
            int result = search(root, target, count);

            if (result != -1) {
                //cout << "Found in " << count << " steps" << endl;
                cout << count << endl;
            }
            else {
                cout << -1 << endl;
            }
        }
    }

    return 0;
}