Binary search tree (day 75)

1： subject

 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].

 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

2： Code implementation

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int l[N], r[N], w[N], idx;
int root;

void insert(int& u, int x)
{
    
    if (!u) u = ++ idx, w[u] = x;
    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()
{
    
    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;
}