﻿HDU 3999 The order of a Tree(二叉树)-Ocrosoft

# The order of a Tree

### 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.

```4

1 3 4 2
```

### Sample Output

```1 3 2 4

```

### Solution

```#include <iostream>
#include <cstdio>
#include <cstring>
#define ms(a) memset(a,-1,sizeof(a))
using namespace std;
struct node
{
int data;
int left;
int right;
}tree[100010];
int pos;
void build(int cur)
{
if(tree[cur].data<tree[pos].data)
{
if(tree[cur].right==-1)//如果没有右节点
tree[cur].right=pos;//设为右节点
else build(tree[cur].right);//继续查找
}
else
{
if(tree[cur].left==-1)//如果没有左节点
tree[cur].left=pos;//设为左节点
else build(tree[cur].left);//继续查找
}
}
void dfs(int pos)
{
if(pos==-1)return;
else
{
if(pos==1)cout<<tree[pos].data;
else  cout<<" "<<tree[pos].data;
}
dfs(tree[pos].left);
dfs(tree[pos].right);
}
int main()
{
int n,t;
while(cin>>n)
{
ms(tree),pos=1;
for(int i=1; i<=n; i++,pos++)
{
cin>>tree[pos].data;
if(i!=1)build(1);//根节点不需要
}
dfs(1);
cout<<endl;
}
return 0;
}
```