To find the node with the value 34 in the binary search tree created from the given values (368, 115, 121, 88, 741, 762, 801, 34, 41, 511, 60), one would start at the root node 368 and compare values. Since 34 is smaller than 368, the search moves to the left subtree. This process continues until the target value 34 is found, resulting in a total of 5 comparisons needed to locate the desired node.
Construct a binary search tree and output its preorder traversal.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| "EOF" input, the first line contains a number N (1 ≤ N ≤ 1000). The second line will input N numbers M (1 ≤ M < 2^31), and no numbers will be repeated. | Output the result of the pre-order traversal of the tree. |
| 11 368 115 121 88 741 762 801 34 41 511 60 6 5 2 10 4 9 15 | 368 115 88 34 41 60 121 741 511 762 801 5 2 4 10 9 15 |
Thought Process
Create a struct to store the current value and the data on the left and right sides (Value, Left, Right). After inputting the data, use a for loop to iterate through the data one by one and determine whether it should be inserted on the left or right side of the data structure. If there is already data in that direction, determine whether to insert the new data to the right or left using a while(true) loop, pushing the existing data to the left/right because the struct itself contains data on the left and right sides, forming an infinite loop to continually insert data. After building the binary search tree, use recursion to output the data from the initial struct. If there is data on the left, continue outputting to the left until there is no more data, then backtrack from the bottom to find any data to output on the right, and repeat until reaching the bottom-right corner of the tree structure.
Sample Code－ZeroJudge D526: Binary Search Tree (BST)
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int value;
struct Node *left;
struct Node *right;
};
void again(Node* hi)
{
if (hi->left != nullptr)
{
cout << hi->left->value << " ";
again(hi->left);
}
if (hi->right != nullptr)
{
cout << hi->right->value << " ";
again(hi->right);
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(nullptr);
int N;
while (cin >> N)
{
vector<int>a;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
a.push_back(tmp);
}
Node* sean = new Node();
sean->value = a[0];
Node* root;
for(int i = 1; i < N; i++) {
root = sean;
Node* p = new Node();
p->value = a[i];
while(true) {
if(root->value < a[i]) {
if(root->right == nullptr) {
root->right = p;
break;
} else {
root = root->right;
}
}
else if(root->value > a[i]) {
if(root->left == nullptr) {
root->left = p;
break;
} else {
root = root->left;
}
}
}
}
cout << sean->value << " ";
again(sean);
cout << "\n";
}
}
//ZeroJudge D526
//Dr. SeanXD