题解 | #二叉排序树#

#include <iostream>
using namespace std;
int n;
struct Node{
    int val;
    Node *left, *right;
    Node(int _val):val(_val), left(NULL), right(NULL){}
};

void insert(Node* &root, int x){
    if(!root)  root = new Node(x);
    else if(x > root->val) insert(root->right, x);
    else if(x < root->val) insert(root->left, x);
    //else return;
}

void dfs(Node* root, int op){
    if(!root) return;
    if(op == 1) cout<<root->val<<' ';
    dfs(root->left, op);
    if(op == 2) cout<<root->val<<' ';
    dfs(root->right, op);
    if(op == 3) cout<<root->val<<' ';

}

int main(){
    Node *root;
    while(cin>>n){
        root = NULL;
        for(int i = 0; i < n; i ++){
            int x;
            cin>>x;
            insert(root, x);
        }
        for(int i = 1; i <= 3; i ++){
            dfs(root, i);
            cout<<endl;
        }
    }
    return 0;
}