题解 | 二叉排序树

#include <iostream>
using namespace std;

struct tnode {
    int data;
    tnode* right, *left;
    tnode() {};
    tnode(int x): data(x), left(nullptr), right(nullptr) {};
};

void func_insert(tnode* T, int x) {
    if (x == T->data) return;
    else if (x < T->data) {
        if (T->left == nullptr) {
            tnode* s = new tnode(x);
            T->left = s;
        } else {
            func_insert(T->left,  x);
        }
    } else {
        if (T->right == nullptr) {
            tnode* s = new tnode(x);
            T->right = s;
        } else {
            func_insert(T->right, x);
        }
    }
}

void func_pre(tnode* T) {
    if (T == nullptr) return;
    cout << T->data << " ";
    func_pre(T->left);
    func_pre(T->right);
}
void func_mid(tnode* T) {
    if (T == nullptr) return;
    func_mid(T->left);
    cout << T->data << " ";
    func_mid(T->right);
}
void func_post(tnode* T) {
    if (T == nullptr) return;
    func_post(T->left);
    func_post(T->right);
    cout << T->data << " ";
}

int main() {
    int num, x;
    while (cin >> num) {
        tnode* T = new tnode(x);
        for (int i = 0; i < num; i++) {
            cin >> x;
            if (i == 0) T->data = x;
            else {
                func_insert(T,  x);
            }
        } //建树完毕
        func_pre(T);
        cout << endl;
        func_mid(T);
        cout << endl;
        func_post(T);
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")