#include<iostream>
using namespace std;
//定义结构体
struct BT{
int data;
BT *lc;//指向左子树根节点的指针
BT *rc;//指向右子树根节点的指针
};
//建立二叉树
//创建节点
BT* root=NULL;
BT* createBTnode(int data){
BT *node=new BT;
node->data=data;
node->lc=NULL;
node->rc=NULL;
return node;
}
//插入节点
void insert(BT *&root,int x){
if(root==NULL){//空树，也是插入位置（递归边界）
    root=createBTnode(x);
    return ;
}
if(x<=root->data){
    insert(root->lc,x);
}
else{
    insert(root->rc,x);
}

}
//从数组创建
BT* Create(int arry[],int n){
if(n<1){//数组为空
    return NULL;
}
BT* root=NULL;
for(int i=0;i<n;i++){
    insert(root,arry[i]);
}
return root;//返回根节点

}
//先序遍历
void preorder(BT* root){
if(root==NULL){
    return ;
}
cout<<root->data<<" ";
preorder(root->lc);
preorder(root->rc);
}
//中序遍历
void inorder(BT* root){
    if(root==NULL){
        return ;
    }
    inorder(root->lc);
    cout<<root->data<<" ";
    inorder(root->rc);
}

int main(){
int Arry[10]={6,2,3,4,5,1,7,8,11,9};
BT *p=Create(Arry,10);
preorder(p);
cout<<endl;
inorder(p);
    return 0;
}