1. 定义：一种经典的数据结构，是一棵空树，或者是具有特定性质的二叉树
2. 性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
3. 时间复杂度：如果共有n个元素，那么平均每次操作需要O(logn)的时间。
4. 特点：链表的快速插入与删除操作
5. 优势：数组快速查找
6. 应用：在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作

例

The order of a Tree

已知一棵树的所有节点，求二叉查找树的先序遍历

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.

4
1 3 4 2

Output

One line with n intergers, which are the order of a tree that generate the same tree with the least lexicographic.

1 3 2 4

#include<cstdio>
#include<iostream>
using namespace std;

struct node{
	int value;
	node *left,*right;
	node(int value=0,node *left=NULL,node *right=NULL):value(value),left(left),right(right){};	
};
void buildtree(int t,node *&root){
	if(root==NULL) root=new node(t);
	else if(t<root->value) buildtree(t,root->left);
	else buildtree(t,root->right);
} 
void preorder(node *root){
	if(root!=NULL){
		printf("%d ",root->value);
		preorder(root->left); 
		preorder(root->right);
	}
} 
void remove_tree(node *root){
	if(root==NULL) return;
	remove_tree(root->left);
	remove_tree(root->right);
	delete root;
}
int main(void){
	int n,t;
	while(~scanf("%d",&n)){
		node *root=NULL;
		for(int i=0;i<n;i++) scanf("%d",&t),buildtree(t,root);
		preorder(root);
		printf("\n");
		remove_tree(root);
	}
	return 0;
}