题解 | #二叉排序树#

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

struct Treenode{
    int data;
    Treenode* leftchild;
    Treenode* rightchild;
    Treenode(int x):data(x),leftchild(NULL),rightchild(NULL){}
};

Treenode* insert(Treenode* root,int x){
    if(root==NULL){  //创建新结点
        root=new Treenode(x);
    }else if(x<root->data){  //插入左子树
        root->leftchild=insert(root->leftchild,x);
    }else if(root->data<x){  //插入右子树
        root->rightchild=insert(root->rightchild,x);
    }
    return root;
}

void PreOrder(Treenode* root){  //前序遍历
    if(root==NULL){
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->leftchild);
    PreOrder(root->rightchild);
    return;
}
void InOrder(Treenode* root){  //中序遍历
    if(root==NULL){
        return;
    }
    InOrder(root->leftchild);
    printf("%d ", root->data);
    InOrder(root->rightchild);
    return;
}
void PostOrder(Treenode* root){  //后序遍历
    if(root==NULL){
        return;
    }
    PostOrder(root->leftchild);
    PostOrder(root->rightchild);
    printf("%d ", root->data);
    return;
}

int main(){
    int n;
    while(cin>>n){
        Treenode * root=NULL;  //建立空树
        for(int i=0;i<n;++i){  //逐个插入
            int x;
            cin>>x;
            root=insert(root,x);
        }
        PreOrder(root);
        printf("\n");
        InOrder(root);
        printf("\n");
        PostOrder(root);
        printf("\n");
    }
    return 0;
}