---

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

原创 于 2023-11-05 10:03:30 发布 · 粉丝可见 · 191 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/134224649

题目：

样例：

cobol<br/>6<br/>5 2 3 6 1 8<br/>

5 2 1 3 6 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;
}

最后提交：