二叉树的基本操作

1、二叉树的存储结构

struct node {
    typename data;//数据域
    node* lchild;//指向左子树根节点的指针
    node* rchild;//指向右子树根节点的指针
};

2、新建一个二叉树节点

node* newNode(int n) {
    node* Node = new node;//申请一个node型变量的地址空间
    Node->data = n;//节点权值为n
    Node->lchild = Node->rchild = NULL;//初始状态下左右孩子为空
    return Node;//返回新建节点的地址
}

3、查找二叉树中节点数据域为x的节点，并将他们的数据域修改为newdata

void search(node* root, int x, int newdata) {
    if (root == NULL) {
        return;//空树，死胡同(递归边界)
    }
    if (root->data == x) {
        root->data = newdata;
    }
    search(root->lchild, x, newdata);//往左子树搜索x
    search(root->rchild, x, newdata);//往右子树搜索x
}

4、二叉树节点的插入(二叉树节点的插入位置就是数据域在二叉树中查找失败的位置)

void insert(node* &root, int x) {
    if (root == NULL) {
        root = newNode(x);//空树，说明查找失败，也即插入的位置(递归边界)
        return;
    }
    if (由二叉树的性质，x应该插在左子树) {
        insert(root->lchild, x);//往左子树搜索(递归式)
    }
    else {
        insert(root->rchild, x);//往右子树搜索(递归式)
    }
}

这里的根节点指针root需要使用引用&，这样才能直接修改原变量的值。与search函数不同的是，search函数中修改的是指针root指向的内容，而不是root本身，而对指针指向的节点内容的修改是不需要加引用的。一般来说，如果函数中需要新建节点，即对二叉树的结构做出修改，就需要加引用；如果只是修改当前已有节点的内容，或仅仅是遍历树，就不需要加引用。

5、二叉树的创建(其实就是二叉树节点的插入过程)

node* create(int data[], int n) {
    node* root = NULL;//新建空根节点
    for (int i = 0;i < n;i++) {
        insert(root, data[i]);
    }
    return root;//返回根节点
}

6、二叉树的先序遍历(递归)

void preorder(node* root){
    if(root==NULL){
        return;//递归边界
    }
    cout<<root->data;//访问根节点
    preorder(root->lchild);//访问左子树
    preorder(root->rchild);//访问右子树
}

7、二叉树的中序遍历(递归)

void inorder(node* root){
    if(root==NULL){
        return;//递归边界
    }    
    inorder(root->lchild);//访问左子树
    cout<<root->data;//访问根节点
    inorder(root->rchild);//访问右子树
}

8、二叉树的后序遍历(递归)

void postorder(node* root){
    if(root==NULL){
        return;//递归边界
    }    
    postorder(root->lchild);//访问左子树
    postorder(root->rchild);//访问右子树
    cout<<root->data;//访问根节点
}

9、二叉树的层序遍历

void LayerOrder(node* root){
    queue<node*> q;//队列当中存储的是地址
    q.push(root);//将根节点地址入队
    while(!q.empty()){
        node* now=q.front();//取出队首元素
        q.pop();
        cout<<now->data;//访问队首元素
        if(now->lchild!=NULL) q.push(now->lchild);//左子树非空
        if(now->rchild!=NULL) q.push(now->rchild);//右子树非空
    }
}

如果需要计算每个节点所处的层次，二叉树节点的定义如下：

struct node{
    typename data;//数据域
    int layer;//层次
    node* lchild;//左指针域
    node* rchild;//右指针域
}

此时的层序遍历为：

void LayerOrder(node* root){
    queue<node*> q;//队列当中存储的是地址
    root->layer=1;//根节点的层数为1
    q.push(root);//将根节点地址入队
    while(!q.empty()){
        node* now=q.front();//取出队首元素
        q.pop();
        cout<<now->data;//访问队首元素
        if(now->lchild!=NULL){//左子树非空
            now->lchild->layer=now->layer+1;//左孩子的层数为当前层数加1
            q.push(now->lchild);
        }
        if(now->rchild!=NULL){//右子树非空
            now->rchild->layer=now->layer+1;//右孩子的层数为当前层数加1
            q.push(now->rchild);
        }
    }
}