时间限制: 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, ×);
}
};
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;
}
}
}