1、定义

typedef struct BiTNode {
    char data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
typedef BiTree ElemType;

2、二叉树的先中后序遍历

void visit(BiTNode* TN) {
    printf("%d", TN->data);
}
//先序遍历
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
//中序遍历
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}
//后序遍历
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

3、层次遍历

void levelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while (!IsEmpty(Q))
    {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild != NULL)
            EnQueue(Q, p->lchild);
        if (p->rchild != NULL)
            EnQueue(Q, p->rchild);
    }
}

4、二叉树的创建

1）先序+中序

void BuildPreInTree(BiTree &T, char* pre_str, char* in_str, int preL, int preR, int inL, int inR) {
    /*
        preL，preR是先序区间
        inL,inL是中序区间
        inRoot_index是根节点下标
    */
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = pre_str[preL];
    int inRoot_index = 0;
    if (inL == inR) {
        inRoot_index = inL;
    }
    for (int i = inL; i <= inR ; i++) {
        if (in_str[i] == pre_str[preL]) {
            inRoot_index = i;
            break;
        }
    }

    if (inRoot_index - inL > 0) {
        BuildPreInTree(T->lchild, pre_str, in_str, preL + 1, preL + inRoot_index-inL, inL, inRoot_index - 1);
    }
    else
    {
        T->lchild = NULL;
    }
    if (inR - inRoot_index > 0) {
        BuildPreInTree(T->rchild, pre_str, in_str, preL + inRoot_index -inL+1, preR, inRoot_index + 1, inR);
    }
    else {
        T->rchild = NULL;
    }
}

2)后序+中序

void BuildPostInTree(BiTree& T, char* post_str, char* in_str, int postL, int postR, int inL, int inR) {
    /*
    T 树的指针
    post_str 先序遍历的数组指针
    in_str 中序遍历的数组指针
    postL,postR 先序遍历数组的范围（左指针和右指针）
    inL,inR 中序遍历数组范围（左指针和右指针）
    */
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = post_str[postR];
    int inRoot_index = 0;
    if (inR == inL) {
        inRoot_index = inR;
    }
    for (int i = inR; i >= inL; i--) {
        in_str[i];
        if (post_str[postR] == in_str[i]) {
            inRoot_index = i;
            break;
        }
    }
    if (inRoot_index - inL > 0) {
        BuildPostInTree(T->lchild, post_str, in_str, postL, postR+inRoot_index-inR-1, inL, inRoot_index - 1);
    }
    else
    {
        T->lchild = NULL;
    }
    if (inR - inRoot_index > 0) {
        BuildPostInTree(T->rchild, post_str, in_str, postR - inR + inRoot_index, postR - 1, inRoot_index + 1, inR);
    }
    else
    {
        T->rchild = NULL;
    }
}