二叉树

//---指针
struct node{
    int data;  //数据域
    int layer;      //层次
    node* lchild;   //指向左子树根结点的指针
    node* rchild;   //指向右子树根结点的指针
};
//---数组
#define maxn 100
struct node{
    int data;
    int lchild;
    int rchild;
}Node[maxn];

//---指针
node* newNode(int v)
{
    node* Node=new node;   //申请node型变量地址空间
    Node->data=v;
    Node->lchild=Node->rchild=NULL;
    return Node;           //返回新建结点的地址
}
//---数组
int index=0;
int newNode(int v)
{
    Node[index].data=v;
    Node[index].lchild=-1;
    Node[index].rchild=-1;
    return index++;
}

//---指针
void search(node* root,int x,int newdata)
{
    if(root==NULL) return;   //空树，递归边界
    if(root->data==x) root->data=newdata;
    search(root->lchild,x,newdata);   //递归往左子树搜索
    search(root->rchild,x,newdata);   //递归王右子树搜索
}
//---数组
void search(int root,int x,int newdata)
{
    if(root==-1) return;  //用-1替代NULL
    if(Node[root].data==x) Node[root].data=newdata;
    search(Node[root].lchild,x,newdata); //往左子树搜索，递归
    search(Node[root].rchild,x,newdata); //往右子树搜索，递归
}

//insert函数在二叉树中插入一个数据域为x的新结点
//根结点指针root要使用引用，否则插入不成功
//---指针
void insert(node* &root,int x)
{
    if(root==NULL){
        root=newNode(x);
        return;
    }
    if(...){
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}
//---数组
//root为根结点在数组中的下标
void insert(int &root,int x)   //要加引用
{
    if(root==-1){
        rot=newNode(x);
        return;
    }
    if(...){
        insert(Node[root].lchild,x);
    }else{
        insert(Node[root].rchild,x);
    }
}

//---指针
node* Create(int data[],int n)
{
    node* root=NULL;   //根结点地址设为空
    for(int i=0;i<n;i++){
        insert(root,data[i]);
    }
    return root;
}
//---数组
int Create(int data[],int n)
{
    int root=-1;  //新建根结点
    for(int i=0;i<n;i++)
    {
        insert(root,data[i]);
    }
    return root;    //返回二叉树的根结点下标
}

/*
root=NULL和*root=NULL区别
遍历到子树时，若子树为空，则子树不存在根结点，此时root自然为空，即root=NULL;
*root是指获取地址root指向的空间的内容，但无法说明地址root是否为空
即结点地址为NULL与结点内容为NULL区别，也相当于结点不存在与结点存在但没有内容的区别
*/