题解 | 二叉排序树

#include<bits/stdc++.h>
using namespace std;
struct Treenode{
    int val;
    Treenode* left;
    Treenode* right;
    Treenode(int x) : val(x), left(nullptr), right(nullptr){}
};
Treenode* InsertTree(Treenode* root, int n){
    if(root == nullptr){
        return new Treenode(n);
    }
    if(n < root -> val){
        root -> left = InsertTree(root -> left, n);
    }
    else if(n > root-> val){
        root -> right = InsertTree(root -> right, n);
    }
    return root;
}

void Preorder(Treenode* root){
    if(root == nullptr)
        return;
    else{
        cout << root -> val << " ";
        Preorder(root -> left);
        Preorder(root -> right);
    }
}
void Inorder(Treenode* root){
    if(root == nullptr){
        return;
    }
    else{
        Inorder(root -> left);
        cout << root -> val << " ";
        Inorder(root -> right); 
    }

}
void Postorder(Treenode* root){
    if(root == nullptr){
        return;
    }
    else{
        Postorder(root -> left);
        Postorder(root -> right);
        cout << root -> val << " ";
    }
}
int main(){
    int n;
    while(cin >> n){
        Treenode* root = nullptr;
        for(int i = 0; i < n; i++){
            int val;
            cin >> val;
            root = InsertTree(root, val);
        }
        Preorder(root);
        cout << endl;
        Inorder(root);
        cout << endl;
        Postorder(root);
        cout << endl;
    }
    return 0;
}

犯的错误：在main()函数中忘记更新root，导致root始终为空没有输出；后序遍历root->val误写成root；

后续可有的改进思路：将三种遍历得到的数字顺序存储成vector容器，方便除了仅输出之外可能有的其他操作