二叉搜索树c++–每日一题

输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。

输入格式

第一行一个整数 nn，表示输入整数数量。

第二行包含 nn 个整数。

输出格式

共三行，第一行输出前序遍历序列，第二行输出中序遍历序列，第三行输出后序遍历序列。

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

数据范围

1≤n≤1001≤n≤100,
输入元素取值范围 [1,1000][1,1000]。

输入样例：

5
1 6 5 9 8

输出样例：

1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=110;
int l[N],r[N],w[N];
int root,idx;

void insert(int &u,int x) //创建二叉搜索树
{
    if(!u) u=++idx,w[u]=x; //如果u为根结点
    else if(x<w[u]) insert(l[u],x);
    else if(x>w[u]) insert(r[u],x);
}

void dfs(int u,int t) //递归前序遍历，中序遍历，后序遍历
{
    if(!u) return;
    if(t==0) cout<<w[u]<<' ';
    dfs(l[u],t);
    if(t==1) cout<<w[u]<<' ';
    dfs(r[u],t);
    if(t==2) cout<<w[u]<<' ';
}


int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        insert(root,x);
    }
    
    for(int i=0;i<3;i++)
    {
        dfs(root,i);
        cout<<endl;
    }
    return 0;
}

 2022/7/15