二叉排序树之查找

时间限制: 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;
        }
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇