二叉搜索树专题1 二叉查找树的建立

专题1 二叉查找树的建立"/>

二叉搜索树专题1 二叉查找树的建立

题目：

样例：

6
5 2 3 6 1 8

思路：

        二叉搜索树的建立，需要了解二叉搜索树的性质。

根据所给的序列进行按序插入即可。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;int n;
umap<int,int>l,r;	// l 为左支树，r 为右支树// 插入构建二叉搜索树
void Insert(int& root,int x)
{if(!root){	// 如果当前结点是空结点// 那么就插入进去root = x;return ;}// 递归，比根节点小，递归插入在左支树上，反之if(root > x) Insert(l[root],x);else Insert(r[root],x);
}void Preorder(int root)
{if(root){cout << root;if(--n) cout << ' ';Preorder(l[root]);Preorder(r[root]);}
}inline void solve()
{int root;cin >> n;for(int i = 0,x;i < n;++i){cin >> x;if(!i) root = x;	// 第一个元素作为根节点else Insert(root,x);	// 其余按序插入构建}Preorder(root);	// 前序遍历树
}int main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}

最后提交：