AcWing 3540. 二叉搜索树 二叉排序树 BST

题目

https://www.acwing.com/problem/content/description/3543/
纯写一个二叉排序树

思路

二叉排序树其实非常的简单，是二叉树与结点大小关系的结合。
结点值的大小：左儿子<父结点<右儿子

代码

#include<iostream>
#include<unordered_map>
using namespace std;
struct TreeNode    //树结构体
{
    
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL)
    {
    }
};
TreeNode *root,*fa;   //根节点、待插入位置结点的父亲结点
unordered_map<int,bool> M;  //判重的哈希表，防止插入重复元素值
int n,x;   //插入数的总数，待插入值
void search(TreeNode *t)  //返回插入位置的父亲结点
{
    
    if(!t) return;  //如果搜索到了空结点，则返回空，结束
    if(x<t->val)    //如果待插入值比当前结点小
    {
    
        fa=t;    //当前结点为父亲节点
        search(t->left);  //递归去查它的左儿子
    }
    else if(x>t->val)  //如果待插入值比当前结点大
    {
    
        fa=t;     //当前结点为父亲节点
        search(t->right);   //递归去查它的右儿子
    }
}
void PrePrint(TreeNode *t)    //前序遍历
{
    
    if(!t) return;
    printf("%d ",t->val);
    PrePrint(t->left);
    PrePrint(t->right);
}
void inPrint(TreeNode *t)      //中序遍历
{
    
    if(!t) return;
    inPrint(t->left);
    printf("%d ",t->val);
    inPrint(t->right);
}
void succPrint(TreeNode *t)    //后序遍历
{
    
    if(!t) return;
    succPrint(t->left);
    succPrint(t->right);
    printf("%d ",t->val);
}
int main()
{
    
    for(int i=1;i<=1000;i++)   //哈希表，1-1000内的数都没有被访问过
        M[i]=false;
    
    scanf("%d",&n);
    scanf("%d",&x);
    root=new TreeNode(x);     //建立根节点
    
    n--;
    while(n--)
    {
    
        fa=NULL;
        scanf("%d",&x);
        if(!M[x])   //已经在树里面的就别放进来了
        {
    
            search(root);   //找到当前要插入的结点该插入位置的父结点指针
            if(fa)  //如果找到了
            {
    
                TreeNode *temp=new TreeNode(x);  //建立节点
                if(x<(fa->val))         //值比父结点小，作为左儿子
                    fa->left=temp;
                else if(x>(fa->val))    //值比父节点大，作为右儿子
                    fa->right=temp;
                M[x]=true;  //设置访问标记，表示被访问过了
            }
        }
    }
    //输出
    PrePrint(root);
    printf("\n");
    
    inPrint(root);
    printf("\n");
    
    succPrint(root);
    
    return 0;
}