[数据结构与算法]STL+树

"Code is beautiful and powerful that can changes the world"

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? --2021.8.23

题目:https://codeforces.com/problemset/problem/675/D

大意:构造一个二叉树，依次输出 输入值对应的父节点

题解:1.利用set从小到大的排序进行存储节点

? ? ? ? 2.分情况考虑

AC代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
using namespace std;
const int N = 1e5;
int a[N+1];
int main()
{
	a[0] = 0;
	int n;
	while (scanf("%d", &n) != EOF)
	{
		set<int>s;
		scanf("%d", &a[1]);
		s.insert(a[1]);
		map<int, int>l, r;//代表是否有左右子树
		for (int i = 2; i <= n; ++i)
		{
			if (i > 2) { cout << " "; }
			scanf("%d", &a[i]);
			set<int>:: iterator add;//获取地址
			add = s.lower_bound(a[i]);//看是否能找到比它大的数
			if (add == s.end())//说明没找到
			{
				printf("%d", *(--add));//就把它作为set中最大值的右子树
				r[*(add)] = 1;//标记其为该父节点的右节点
			}
			else//找到比它大的数
			{
				if (l[*add] == 1)//如果该节点左子树已经存在
				{
					printf("%d", *(--add));//则把它所谓其位置-1的上个节点的右子树
					r[*(add)] = 1;
				}
				else//若左子树存在则把它作为该节点的左子树
				{
					printf("%d", *(add));
					l[*(add)] = 1;
				}
			}
			s.insert(a[i]);
		}
	}
	return 0;
}