Contents

• 话不多说，直接上代码，解释都在代码里

## 测试用例：
A B C # # D E # G # # F # # # 

                A
              /
            B
          /   \
        C       D
              /   \
            E       F
              \
                G

## 测试结果：
xianxu: 
A B C D E G F 
zhongxu:
C B E G D F A 
houxu:
C G E F D B A 
/////////////
ceng ci:
A 5
B 4
C 1
D 3
E 2
F 1
G 1



#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;

struct build_node{                      //二叉树节点
    char data;                          //用户数据
    build_node *lchild, *rchild;        //左孩子和右孩子
    int level;                          //高度
};

int creat_tree(build_node **T){         //要修改一级指针指向值，所以用二级指针
    char data;
    scanf("%c", &data);
    if(data == '#'){
        (*T) = NULL;                    //注意这里是二级指针里的值为NULL
        return 0;
    }
    else{
        (*T) = (build_node *)malloc(sizeof(build_node));
        (*T)->data = data;
        creat_tree(&(*T)->lchild);
        creat_tree(&(*T)->rchild);
    }
    return 0;
}

void visit(build_node *T)               //不修改里面的值，直接值传递{

    if(T->data != '#')
        printf("%c ", T->data);
}

////////////////////////////////////////////////////////

//1先序遍历
void preorder(build_node *T){

    if(T != NULL){
        visit(T);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

//2中序遍历
void inorder(build_node *T){

    if(T != NULL){
        inorder(T->lchild);
        visit(T);
        inorder(T->rchild);
    }
}

//3后序遍历
void postorder(build_node *T){

    if(T != NULL){
        postorder(T->lchild);
        postorder(T->rchild);
        visit(T);
    }
}

//4层次遍历,其实就是广度优先搜索
void levelorder(build_node *T){

    queue <build_node *> que;
    que.push(T);                        //根节点入队
    build_node *p = T;
    while(!que.empty()){                //如果队列不空
        p = que.front();                //对头元素出队
        printf("%c %d\n", p->data, p->level);         //访问内容
        que.pop();                      //退出队列
        if(p->lchild != NULL)           //左子树不空，将左子树入队
            que.push(p->lchild);
        if(p->rchild != NULL)           //右子树不空，将右子树入队
            que.push(p->rchild);
    }
}

//5二叉树节点的计数
int tree_node_size(build_node *T){

    if(T == NULL)
        return 0;
    else
        return 1 + tree_node_size(T->lchild) + tree_node_size(T->rchild);
}
//6计算二叉树的高度
int high(build_node **T)                //(如果二叉树为空那么高度为0，否则高度就是取左右子树中高的那个+根节点){

    if((*T) == NULL)
        return 0;
    else
    {
        int left = high(&(*T)->lchild);
        int right = high(&(*T)->rchild);
        return (*T)->level = left < right ? right + 1 : left + 1;
    }
}

//7二叉树的复制，返回复制后的根节点
build_node *Copy(build_node *T)         //不修改原树的数据，所以一级指针{

    if(T == NULL)
      return NULL;
   build_node *tmp = (build_node *)malloc(sizeof(build_node));
   tmp->data = T->data;
   tmp->lchild = Copy(T->lchild);
   tmp->rchild = Copy(T->rchild);
   return tmp;
}

//6判断两棵二叉树是否相等
bool isEqual(build_node *root1, build_node *root2){

    if(root1 == NULL && root2 == NULL)
        return true;
    if(root1 != NULL && root2 != NULL && root1->data == root2->data
       && isEqual(root1->lchild, root2->lchild)
       && isEqual(root2->rchild, root2->rchild)
       )
        return true;
    else
        return false;
}


//7二叉树的重建(节点编号从1~n)
//由先序序列和中序序列可以确定唯一二叉树
//由先序序列和中序序列构造二叉树（len是序列的长度，pre为先序序列 mid为中序序列，返回根节点）
                           //index  mid的index左边是左子树,右边是右子树,pre的index左边是左子树,跳过index距离后右边是右子树
// 中： C B E G D F A (左子树, 根, 右子树)
// 先： A B C D E G F (根, 左子树, 右子树)

build_node *rebuildtree_1(char *pre, char *mid, int len){

    if(!len)
        return NULL;
    int index = 0;
    while(mid[index] !=  pre[0])        //在中序序列找根节点,先序序列第一个就是根
        index++;                        //index记录在中序序列里经过了几个元素才找到的,重建左子树时就要在先序序列里跳过这几个元素再找
    build_node *root = (build_node *)malloc(sizeof(build_node));
    root->data = pre[0];
    root->lchild = rebuildtree_1(pre, mid, index);
    root->rchild = rebuildtree_1(pre+index+1, mid+index+1, len-index-1);//右边len-index-1个元素是右子树的,扣除根节点
    return root;
}


//8由后序序列和中序序列可以确定唯一二叉树
//由中序和后序建立二叉树(len是序列的长度，mid是中序序列，post是后序序列，返回根节点)
//重点是利用好 中序序列
                           //index  mid的index左边是左子树，右边是右子树,post的index左边是左子树,index后面是右子树
// 中： C B E G D F A (左子树, 根, 右子树)
// 后： C G E F D B A (左子树，右子树，根)
build_node *rebuildtree_2(char *mid, char *post, int len){

    if(len == 0)
        return NULL;
    int index = 0;                      //在中序序列中进行查找根节点，并用index记录在中序序列的索引
    while(mid[index] != post[len - 1])  //在中序序列中找根节点,后序序列的最后一个是根
        index++;
    build_node *root = (build_node *)malloc(sizeof(build_node));
    root->data = post[len - 1];
    root->lchild = rebuildtree_2(mid, post, index);
    //index在中序序列中左边是左子树,index在后序序列中,左边也是左子树,
    //index-1就是左子后右再根中的根,最后传过去index成len,len-1就是左子树的根
    root->rchild = rebuildtree_2(mid+index+1, post+index, len-index-1);
    //根序号的右边是右子树,所以是从这mid+index+1开始找右子树的根,
    //index在中序序列中的右边是右子树,后序序列是先左子树再右子树最后根节点,
    //所以index在后序序列中左边也是左子树，右边是右子树和根，而index不一定是根的
    //位置了,所以从post[index]开始找右子树的根
    return root;
}


int main(){

    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    build_node *T = NULL;
    creat_tree(&T);
    //////////////
    printf("preorder: \n");
    preorder(T);
    printf("\n");
    printf("inorder:\n");
    inorder(T);
    printf("\n");
    printf("postorder:\n");
    postorder(T);
    printf("\n/////////////\n");

    high(&T);
    printf("levelorder:\n");
    levelorder(T);

    printf("tmp Copy of T:\n");
    build_node *tmp = Copy(T);
    inorder(tmp);
    printf("\n\\\\\\\\\\\\\\\\\\\\\\\ \n");

    printf("tmp == T ?\n");
    if(isEqual(tmp, T))
        printf("YES\n");
    else
        printf("NO\n");

    return 0;
}