【範例】二元搜索樹 (Bineary Search Tree, BST)
【題目敘述】 https://zerojudge.tw/ShowProblem?problemid=d526
【解題想法】構造出二元搜索樹 (Bineary Search Tree, BST)
【更多練習】ZeroJudge b148: NOIP2004 3.FBI树 【題解】
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x, TreeNode *L, TreeNode *R) : val(x), left(L), right(R) {}
};
TreeNode *root;
void addNode(int x) {
TreeNode *curr, *node;
curr = root;
while (1) {
if (x > curr->val) {
if (curr->right == NULL) {
node = new TreeNode(x, NULL, NULL);
curr->right = node;
return;
} else {
curr = curr->right;
}
} else {
if (curr->left == NULL) {
node = new TreeNode(x, NULL, NULL);
curr->left = node;
return;
} else {
curr = curr->left;
}
}
}
}
void preOrder(TreeNode *p) {
cout << p->val << " ";
if (p->left != NULL) preOrder(p->left);
if (p->right != NULL) preOrder(p->right);
}
int main() {
int N, n;
while (cin >> N) {
cin >> n;
root = new TreeNode(n, NULL, NULL);
for (int i=1; i<N; i++) {
cin >> n;
addNode(n);
}
preOrder(root);
cout << endl;
}
return 0;
}