【題解】ZeroJudge d526: Binary Search Tree (BST)

【範例】二元搜索樹 (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;
}
分享本文 Share with friends