3540. 二叉搜索树

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

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

第二行包含 n 个整数。

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

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

1≤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 
using namespace std;
const int N = 110;
int w[N], l[N], r[N], idx;
int n;
int root;
void add(int u, int x)
{
    if (x < w[u])
    {
        if (!l[u])
            l[u] = ++idx, w[idx] = x;
        else
            add(l[u], x);
    }
    else if (x > w[u])
    {
        if (!r[u])
            r[u] = ++idx, w[idx] = x;
        else
            add(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()
{
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        if (root == 0)
            root = 1, w[root] = x, ++idx;
        else
            add(root, x);
    }

    for (int i = 0; i < 3; i++)
    {
        dfs(root, i);
        cout << endl;
    }

    return 0;
}