The order of a Tree 水题 之 二叉搜索的数的先序输出

  这里是杭电hdu上的链接:http://acm.hdu.edu.cn/showproblem.php?pid=3999

 Problem Description:
  As we know,the shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:
  1.  insert a key k to a empty tree, then the tree become a tree with only one node;
  2.  insert a key k to a nonempty tree, if k is less than the root ,insert it to the left sub-tree; else insert k to the right sub-tree. We call the order of keys we insert “the order of a tree”, your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.
  Input:
  There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.
 Output:
  One line with n intergers, which are the order of a tree that generate the same tree with the least lexicographic.
 Sample Input:
  4
  1 3 4 2
 Sample Output
  1 3 2 4
  解题思路:我的标题已经指出了这是水题,套用二叉搜索树的模板就行。另外在输出的时候注意空格即可,如果好几次没有ac的话可以参考下输出。
 #include <iostream>
#include <cstdlib>
using namespace std; int j; struct node {
int val;
node *lch;
node *rch;
}; node *creat (node *p, int x) {
if (p == NULL) {
node *q = new node;
q->val = x;
q->lch = q->rch = NULL;
return q;
}
else {
if (x < p->val) p->lch = creat (p->lch,x);
else p->rch = creat (p->rch,x);
return p;
}
}
void pre_order (node *s) {
//int j = 0;如果写这里--->每一次进来都是0
if (s) {
if (j > )
cout << " ";
j++;
cout << s->val;
pre_order (s->lch);
pre_order (s->rch);
}
} int main() {
int n,x;
while (cin >> n) {
j = ;
node *root = NULL;
for (int i = ;i < n; ++i) {
cin >> x;
root = creat(root,x);
}
pre_order (root);
cout << endl;
}
return ;
}

  欢迎码友评论,一起成长。

上一篇:SqlServer性能优化索引(五)


下一篇:UVa 1391 Astronauts (2SAT)