3540. Binary search tree

Enter a series of integers , Use the given data to build a binary search tree , And output its preamble 、 Middle order and post order traversal sequences .

Input format

The first line is an integer n, Indicates the number of input integers .

The second line contains n It's an integer .

Output format

There are three lines , The first line outputs the preorder traversal sequence , The second line outputs the middle order traversal sequence , The third line outputs the post order traversal sequence .

There may be duplicate elements in the input , But the repeated elements in the output binary tree traversal sequence do not need to be output .

Data range

1≤n≤100,
Input element value range [1,1000][1,1000].

sample input ：

5
1 6 5 9 8

sample output ：

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

Code ：

#include <bits/stdc++.h>
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;
}