Special topic of binary tree -- acwing 3540 Binary search tree building (use the board to build a binary search tree and output the pre -, middle -, and post sequence traversal)

The question ：

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 .

Ideas ：

This code can be used to make a practical board .

I used to Array of structs bst Save tree ：

const int N = 110;
struct node
{
	int key;		// The key value of the current node  
	int l = -1, r = -1;	// The left and right sons of the current node , First initialize to  -1, It means you haven't left or right your son 
	int cnt;	// identical  key  How many nodes of value 
} bst[N];

according to Definition of binary search tree , Recursively build a tree , Here is insert function ：

void insert(int u, int key)
{
	if (bst[0].key == 0) bst[idx++].key = key;	// Root node key value special processing 

	if (key < bst[u].key)
	{
		if (bst[u].l == -1)	// Recurse to the left until you can't recurse anymore , Generate a new leaf node and assign the left pointer 
		{
			bst[idx].key = key;
			bst[u].l = idx++;
		}
		else insert(bst[u].l, key);	// Continue to recurse to the left before the end 
	}
	else if (key > bst[u].key)
	{
		if (bst[u].r == -1)	// Recurse to the right until you can no longer recurse , Generate a new leaf node and assign the right pointer 
		{
			bst[idx].key = key;
			bst[u].r = idx++;
		}
		else insert(bst[u].r, key);	 Continue to recurse to the right before the end 
	}
	else if(key == bst[u].key) bst[u].cnt++;
}

Next is the front 、 in 、 The routine code of post sequence traversal ：

Before the order dfs1 function ：（ root Left Right ）

void dfs1(int u)	// Before the order 
{
	if (u == -1) return;	// Back to the end 
	ans1.push_back(bst[u].key);	// root 
	dfs1(bst[u].l);	// Left  
	dfs1(bst[u].r);	// Right 
}

Middle preface dfs2 function ：（ Left root Right ）

void dfs2(int u)	// Continued 
{
	if (u == -1) return;
	dfs2(bst[u].l);	// Left 
	ans2.push_back(bst[u].key);	// root 
	dfs2(bst[u].r);	// Right 
}

In the following order dfs3 function ：（ Left Right root ）

void dfs3(int u)	// follow-up 
{
	if (u == -1) return;
	dfs3(bst[u].l);	// Left 
	dfs3(bst[u].r);	// Right 
	ans3.push_back(bst[u].key);	// root 
}

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 110;
int idx;

struct node
{
    
	int key;
	int l = -1, r = -1;
	int cnt;
} bst[N];

int w[N];
int n;
vector<int> ans1, ans2, ans3;

void insert(int u, int key)
{
    
	if (bst[0].key == 0) bst[idx++].key = key;

	if (key < bst[u].key)
	{
    
		if (bst[u].l == -1)
		{
    
			bst[idx].key = key;
			bst[u].l = idx++;
		}
		else insert(bst[u].l, key);
	}
	else if (key > bst[u].key)
	{
    
		if (bst[u].r == -1)
		{
    
			bst[idx].key = key;
			bst[u].r = idx++;
		}
		else insert(bst[u].r, key);
	}
	else if(key == bst[u].key) bst[u].cnt++;
}

void dfs1(int u)// Before the order 
{
    
	if (u == -1) return;
	ans1.push_back(bst[u].key);
	dfs1(bst[u].l); 
	dfs1(bst[u].r);
}

void dfs2(int u)// Continued 
{
    
	if (u == -1) return;
	dfs2(bst[u].l);
	ans2.push_back(bst[u].key);
	dfs2(bst[u].r);
}

void dfs3(int u)// follow-up 
{
    
	if (u == -1) return;
	dfs3(bst[u].l);
	dfs3(bst[u].r);
	ans3.push_back(bst[u].key);
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
    
			cin >> w[i];
			insert(0, w[i]);
		}
		
		dfs1(0), dfs2(0), dfs3(0);
		for (auto v : ans1) cout << v << ' ';
		puts("");
		for (auto v : ans2) cout << v << ' ';
		puts("");
		for (auto v : ans3) cout << v << ' ';
		puts("");
	}

	return 0;
}