二叉查找树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树。
以题目http://oj.lizi101.com/problem.php?id=1255为例：

#include<iostream>  //建立二叉排序树 
using namespace std;
const int N=1e5+10;
struct node{  //结点 
    int v,lc,rc;
}a[N];
int n; 
void build(int p,int x){//建树：当前位置p，增加x
    if(a[p].v<a[x].v){
        if(a[p].rc){  //右子树存在 
             build(a[p].rc, x);
        }else{  //右子树不存在 
            a[p].rc=x;  //挂在树的右边 
            return;
        }
    }else{
        if(a[p].lc){  //左子树存在 
             build(a[p].lc, x);
        }else{  //左子树不存在 
            a[p].lc=x;  //挂在树的右边 
            return;
        }
    }
}
void zhong(int x){  //中序遍历:左根右
    if(a[x].lc) zhong(a[x].lc);
    cout<<a[x].v<<' ';
    if(a[x].rc) zhong(a[x].rc);
}
void hou(int x){  //后序遍历：左右根 
    if(a[x].lc) hou(a[x].lc);
    if(a[x].rc) hou(a[x].rc);
    cout<<a[x].v<<' ';
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v;
        if(i==1) continue;  //根结点 
        build(1, i);  //建二叉排序树 
    }
    zhong(1);  //中序遍历,从根1开始 
    cout<<endl;
    hou(1);    //后序遍历 
    return 0;
}