Description
Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority (a number) such that the priority of each internal node is less than the priority of its parent. As a consequence, the root has the greatest priority in the tree, which is one of the reasons why heaps can be used for the implementation of priority queues and for sorting.A binary tree in which each internal node has both a label and a priority, and which is both a binary search tree with respect to the labels and a heap with respect to the priorities, is called a treap. Your task is, given a set of label-priority-pairs, with unique labels and unique priorities, to construct a treap containing this data.
Input
The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=50000. Then follow n pairs of strings and numbers l1/p1,...,ln/pn denoting the label and priority of each node. The strings are non-empty and composed of lower-case letters, and the numbers are non-negative integers. The last test case is followed by a zero.Output
For each test case output on a single line a treap that contains the specified nodes. A treap is printed as (< left sub-treap >< label >/< priority >< right sub-treap >). The sub-treaps are printed recursively, and omitted if leafs.Sample Input
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
Sample Output
(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)))
Source
Ulm Local 2004
思路:先按字符串排下序,建笛卡尔树,递归输出。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct S{
int id,val;
int parent,l,r;
}node[50005];
int stk[50005],top;
char s[50005][20];
bool cmp(struct S a,struct S b)
{
if(strcmp(s[a.id],s[b.id])<0) return 1;
return 0;
}
int build(int n)
{
int i;
top=0;
stk[top]=0;
for(i=1;i<n;i++)
{
while(top>=0 && node[stk[top]].val<node[i].val) top--;//注意,这里让小于当前值的出栈
if(top>-1)
{
node[i].parent=stk[top];
node[node[stk[top]].r].parent=i;
node[i].l=node[stk[top]].r;
node[stk[top]].r=i;
}
else
{
node[stk[0]].parent=i;
node[i].l=stk[0];
}
stk[++top]=i;
}
return stk[0];//返回根节点
}
void dfs(int x)
{
printf("(");//先输出左括号
if(node[x].l!=-1) dfs(node[x].l);//如果有左子树,就先输出左子树
printf("%s/%d",s[node[x].id],node[x].val);//输出自己
if(node[x].r!=-1) dfs(node[x].r);//再输出右子树
printf(")");//右括号
}
int main()
{
int n,i,root;
while(~scanf("%d",&n) && n)
{
for(i=0;i<n;i++)
{
scanf("%*[ ]%[a-z]/%d",s[i],&node[i].val);
node[i].id=i;
node[i].parent=node[i].l=node[i].r=-1;
}
sort(node,node+n,cmp);//按字符串字典序排序
root=build(n);//建树
dfs(root);//递归输出
printf("\n");
}
}
更多推荐
POJ-1785-Binary Search Heap Construction(笛卡尔树)
发布评论