题解 | #二叉排序树#

#include <iostream>
using namespace std;
const int N = 101;

struct Node{
    int data;
    Node* left;
    Node* right;
    Node(int x):data(x), left(NULL), right(NULL){}
};

Node* insert(Node* root, int x){
    if(root == NULL){
        root = new Node(x);
    }
    else if(x < root->data){
        root->left = insert(root->left, x);
    }
    else if(x > root->data){
        root->right = insert(root->right, x);
    }
    else if(x == root->data){}//不做处理

    return root;
}

void preOrder(Node* root){
    if(root != NULL){
        cout << root->data << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

void inOrder(Node* root){
    if(root != NULL){
        inOrder(root->left);
        cout << root->data << " ";
        inOrder(root->right);
    }
}

void postOrder(Node* root){
    if(root != NULL){
        postOrder(root->left);
        postOrder(root->right);
        cout << root->data << " ";
    }
}


int main() {
    int n, x;
    while(cin >> n){
        Node* root = NULL;
        while(n --){
            cin >> x;
            root = insert(root, x);
        }
        preOrder(root);
        cout << endl;
        inOrder(root);
        cout << endl;
        postOrder(root);
        cout << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")