struct node{
    typename data;
    node* lchild;
    node* rchild;
}node[maxn];

//節(jié)點的動態(tài)生成可以變?yōu)殪o態(tài)指定：

int index = 0;
int newNode(int v){
    node[index].data = v;
    node[index].lchild = -1;
    node[index].rchild = -1;
    return index++;
} 

//二叉樹查找

void search(int root, int x, int newdata){
    if(root == -1){
        //用-1來代表空樹 
        return ;
        //空樹涡贱，死循環(huán)（遞歸邊界） 
    }
    if(node[root].data == x){
        node[root].data = newdata;
        //如果找到數(shù)據(jù)域為x的節(jié)點，把他修改為newdata 
    } 
    search(node[root].lchild, x, newdata);
    search(node[root].rchild, x, newdata); 
} 

//插入愕把，root為根節(jié)點在數(shù)組中的下標

void insert(int &root, int x){
    //記得加引用
    if(root == -1){
        //空樹拣凹，說明查找失敗,這里就是插入位置（遞歸邊界）
        root = newNode(x);
        return ; 
    } 
    if(由二叉樹性質x應插在左子樹)
        insert(node[root].lchild, x);
    else{
        insert(node[root].rchild, x);
    } 
}

//二叉樹的建立，函數(shù)返回根節(jié)點root的下標

int create(int data[], int n){
    int root = -1;
    for(int i = 0; i < n; i++){
        insert(root, data[i]);
        //將data[0]~data[n-1]插入二叉樹中恨豁； 
    }
    return root;
} 

二叉樹的前序中序后序層序遍歷

//前序
void preorder(int root){
    if(root == -1)
        return ;
        //到達空樹嚣镜，遞歸邊界
    //訪問根節(jié)點root，比如操作：將根節(jié)點輸出
    printf("%d\n", node[root].data);
    //訪問左子樹
    preorder(node[root].lchild);
    //訪問右子樹
    preorder(node[root].rchild); 
} 

//中序
void inorder(int root){
    if(root == -1){
        return ;
    }
    inorder(node[root].lchild);
    printf("%d\n", node[root].data);
    inorder(node[root].rchild);
} 

//后序
void postorder(int root){
    if(root == -1)
        return ;
    postorder(node[root].lchild);
    postorder(node[root].rchild);
    printf("%d\n", node[root].data);
} 

//層序遍歷

void layerorder(int root){
    queue<int> q;
    //此處隊列里放節(jié)點的下標 
    q.push(root);
    //將根節(jié)點地址入隊
    while(!q.empty()){
        int now = q.front();
        q.pop();
        printf("%d ", node[now].data);
        //取出隊首元素并訪問
        if(node[now].lchild != -1)
            q.push(node[root].lchild);
            //左子樹非空
        if(node[now].rchild != -1)
            q.push(node[root].rchild);
            //右子樹非空 
    } 
}