问题描述:
建一棵笛卡儿树。给出几个点,每个点包括两个数据:标签1abel、优先级pri。把这n个点建成一棵笛卡儿树，并打印树。
输入：每行是一个测试，输入的第 1 个数是节点数量 n，后面有 n 个点，每个点包括标签和优先级。
输出：打印树，每个节点的打印格式为(<left sub-treap><label>/<priority><rightsub-treap>)，中序打印。
| 输入样例 | 输出样例 |
| 7 a/7 b/6 c/5 d/4 e/3 f/2 g/1 7 a/1 b/2 c/3 d/4 e/5 f/6 g/7 7 a/3 b/6 c/4 d/7 e/2 f/5 g/1 0 | (a/7(b/6(c/5(d/4(e/3(f/2(g/1))))))) (((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7) (((a/3)b/6(c/4))d/7((e/2)f/5(g/1))) |
用单调栈建笛卡尔树
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <stack>
using namespace std;
const int N = 50005;
const int INF = 0x7fffffff;
struct Node{
char s[100]; int ls,rs,fa,pri;
friend bool operator<(const Node& a,const Node& b){ //重载操作符函数<：栈底大，栈顶小
return strcmp(a.s,b.s)<0;} //按 ASCII 值从小到大排列
}t[N];
void buildtree(int n){ //不用栈，直接查最右链
for(int i=1;i<=n;i++){
int pos = i-1; //从前一个结点开始比较，前一个结点在最右链的末端
while(t[pos].pri < t[i].pri) //比较优先级
pos = t[pos].fa; //沿着最右链一直找，直到pos的优先级比i大
t[i].ls = t[pos].rs; // pos 的右儿子赋值给 i 的左儿子，不影响中序键值输出
t[t[i].ls].fa = i; //原 pos 为父节点更换成 i
t[pos].rs = i; //pos 的 右子树也更换成新节点 i
t[i].fa = pos; //新节点的父节点更新为 pos
}
}
void buildtree2(int n){ //用栈来辅助建树
stack <int> ST; ST.push(0); //t[0]进栈，它一直在栈底
for(int i=1;i<=n;i++){
int pos = ST.top(); //取出栈顶
while(!ST.empty() && t[pos].pri < t[i].pri){ //非空栈内比较优先级
pos = t[ST.top()].fa;
ST.pop(); //把比i优先级小的弹出栈
}
t[i].ls = t[pos].rs;
t[t[i].ls].fa = i;
t[pos].rs = i;
t[i].fa = pos;
ST.push(i); //每个结点都一定要进栈
}
}
void inorder(int x){ //中序遍历打印
if(x==0) return;
printf("(");
inorder(t[x].ls); printf("%s/%d",t[x].s,t[x].pri); inorder(t[x].rs);
printf(")");
}
int main(){
int n;
while(scanf("%d",&n),n){ //测试节点数量
for(int i=1;i<=n;i++){
t[i].ls = t[i].rs = t[i].fa = 0; //有多组测试，每次要清零
scanf(" %[^/]/%d", t[i].s, &t[i].pri); //注意输入的写法
}
t[0].ls = t[0].rs = t[0].fa = 0; //t[0]不用，从t[1]开始插结点
t[0].pri = INF; //t[0]的优先级无穷大
sort(t+1,t+1+n); //对标签先排序，非常关键。这样建树时就只需要考虑优先级pri
buildtree(n); //buildtree2(n); //两种建树方法
inorder(t[0].rs); //t[0]在树的最左端，第一个点是t[0].rs
printf("\n");
}
return 0;
}
笔记：笛卡儿树是简化的Treap树，主要处理确定的数列。笛卡儿树建树前已经标签排序，每次新的点总是插在最右边，每次调整的都是纵向位置。代码里的提供了两种建树方式，不用栈就直接查询最右链的优先级，依次插进到树中。用栈建树每次插入新节点 i 就将栈内优先级小于 i 的踢出，调整栈内的优先值是单调递增