[洛谷 P1377] TJOI2011 树的序

我不是女神ヾ 2021-10-23 12:22 438阅读 0赞

## 问题描述 ##

众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：1、空树中加入一个键值k，则变为只有一个结点的二叉查找树，此结点的键值即为k；2、在非空树中插入一个键值k，若k小于其根的键值，则在其左子树中插入k，否则在其右子树中插入k。

我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为n的生成序列，先比较第一个插入键值，再比较第二个，依此类推。

## 输入格式 ##

第一行，一个整数，n，表示二叉查找树的结点个数。第二行，有n个正整数，k1到kn，表示生成序列，简单起见，k1~kn为一个1到n的排列。

## 输出格式 ##

一行，n个正整数，为能够生成同样二叉查找数的所有生成序列中最小的。

## 样例输入 ##

4  
1 3 4 2

## 样例输出 ##

1 3 2 4

## 解析 ##

根据题目要求，我们可以这么想：字典序最小的构法肯定是从小到大插入，但最后构出来的树会是一条链。我们可以设一个节点有两个关键值：一是本身的值，二是第几个插入。我们需要这棵树越往上第二关键字越小，即每个节点的第二关键字小于自己的两个儿子(不然不满足原树的顺序)，整棵树的第一关键字又要满足二叉搜索树，这就是一棵笛卡尔树。

笛卡尔树的构造方法是：首先把所有节点按照第一关键字排序，这样构造出来的树就是一条在最右边的链。用一个栈保存最右边链的节点。对于每一个插入的节点i，都在栈中找到第一个第二关键字比自己小的点，并将i作为这个点的右儿子，而原来接的右链接到i的左儿子处，并从栈中弹出。最后中序遍历整棵树的序列即为答案。

## 代码 ##

#include <iostream> #include <cstdio> #include <algorithm> #define N 100002 using namespace std; struct node{ int dat,key; }a[N]; int n,i,fa[N],dat[N],key[N],son[N][2],s[N],top; int my_comp(const node &x,const node &y) { return x.dat<y.dat; } void insert(int x,int f,int p) { fa[x]=f; son[f][p]=x; } void dfs(int x) { if(!x) return; cout<<dat[x]<<' '; dfs(son[x][0]); dfs(son[x][1]); } int main() { cin>>n; for(i=1;i<=n;i++){ cin>>a[i].dat; a[i].key=i; } sort(a+1,a+n+1,my_comp); for(i=1;i<=n;i++){ int last=0; while(top>0&&key[s[top]]>a[i].key) last=top,top--; dat[i]=a[i].dat; key[i]=a[i].key; insert(i,s[top],1); insert(s[last],i,0); s[++top]=i; } dfs(son[0][1]); cout<<endl; return 0; }

转载于:https://www.cnblogs.com/LSlzf/p/11150484.html