题解 | 二叉排序树

#include <bits/stdc++.h>
using namespace std;

struct Tnode{
    int data;
    struct Tnode* left;
    struct Tnode* right;
    Tnode(int i):data(i),left(nullptr),right(nullptr){}
};

Tnode* insert(Tnode* t,int x){
    if(t==nullptr)t=new Tnode(x);
    else if(x<t->data)t->left=insert(t->left,x);
    else if(x>t->data) t->right=insert(t->right,x);
    return t;
}

void preOrder(Tnode* t){
    if(t==nullptr)return;
    cout<<t->data<<" ";
    preOrder(t->left);
    preOrder(t->right);
}

void inOrder(Tnode* t){
    if(t==nullptr)return;
    inOrder(t->left);
    cout<<t->data<<" ";
    inOrder(t->right);
}

void postOrder(Tnode* t){
    if(t==nullptr)return;
    postOrder(t->left);
    postOrder(t->right);
    cout<<t->data<<" ";
}

int main(){
    int n;
    while(cin>>n){
        Tnode *t=nullptr;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            t=insert(t,x);
        }
        preOrder(t);cout<<endl;
        inOrder(t);cout<<endl;
        postOrder(t);cout<<endl;
    }
}

这个问题属于一系列问题，都是创建一个二叉排序树，然后进行三序输出的过程，对于后面的三序输出，非常简单，主要难点在构造，这个构造过程其实也不难，对于每一个输入的值，我们都要插入到一个确定的树里面，那么根据二叉排序的规则，我们需要数值进行判断，大于则往右子树去找，小于则往左子树去找，每个的操作都是一样的，所以确定递归函数，又知道，为空的时候可以就无序比较了，找到了位置，写入创建，return即可，然后我们要的是第一个节点，所以最后return第一个的t即可。