题解 | #二叉排序树#

#include <cstddef>
#include <iostream>
using namespace std;

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

void preorder(Node *root){
    if(root==nullptr) return;
    cout<<root->val<<" ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node *root){
    if(root==nullptr) return;
    inorder(root->left);
    cout<<root->val<<" ";
    inorder(root->right);
}

void lastorder(Node *root){
    if(root==nullptr) return;
    lastorder(root->left);
    lastorder(root->right);
    cout<<root->val<<" ";
}

Node *buildTree(Node *&root,int x){//建树
    if(root==nullptr)  root = new Node(x);
    if(root->val==x);
    else if(root->val>x) buildTree(root->left,x);
    else if(root->val<x) buildTree(root->right,x);
    return  root;
}


int main() {
    int n;
    while(cin>>n){
    Node *root = nullptr;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        root = buildTree(root,x);
    }
    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
    lastorder(root);
    cout<<endl;
    }
   

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