二叉树的构造

【序列的异同】

在先序中序、后序中序、层序这三种情况的任意一种下，可唯一确定一颗二叉树

对于非空二叉树来说，当给出前中后序序列中任意两种，根据其相反或相同，有以下判断：

1.前序和中序

• 若相同，则二叉树为右斜树
• 若相反，则二叉树为左斜树

2.前序和后序

• 若相同，则二叉树仅有根结点
• 若相反，则每层仅有一个结点，即二叉树高度为结点个数

3.中序和后序

• 若相同，则二叉树为左斜树
• 若相反，则每层仅有一个结点，即二叉树高度为结点个数

【前序与中序确定二叉树】

前序序列中，第一个结点一定是根结点

在中序序列中，根结点将中序序列分割成左右两个子序列：

• 左子序列：根结点的左子树的中序序列
• 右子序列：根结点的右子树的中序序列

根据这两个序列，在前序序列中找出对应的序列，然后如此递归下去，即可确定唯一的一棵二叉树

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
BiTree createPreInTree(char pre[], char in[], int inStart, int inEnd) { //前序中序构造二叉链表
    static int preIndex = 0; //注意此处为静态变量

    if (inStart > inEnd)
        return NULL;

    BiTNode *root = (BiTNode *)malloc(sizeof(BiTNode));
    root->data = pre[preIndex++]; //取出前序序列第1个结点作为根结点
    root->lchild = NULL;
    root->rchild = NULL;

    if (inStart == inEnd) //结点没有孩子则返回
        return root;

    //查找根结点在中序序列中的位置
    int inIndex;
    for (inIndex = inStart; inIndex <= inEnd; inIndex++)
        if (in[inIndex] == root->data)
            break;

    //利用中序序列递归构造左子树与右子树，注意先左后右
    root->lchild = createPreInTree(pre, in, inStart, inIndex - 1);
    root->rchild = createPreInTree(pre, in, inIndex + 1, inEnd);
}
int main() {
    char pre[6] = {'A', 'B', 'D', 'E', 'C'};
    char in[6] = {'D', 'B', 'E', 'A', 'C'};
    int n = 5;
    BiTree root = createPreInTree(pre, in, 0, n - 1);
    //do something
    system("pause");
    return 0;
}

【后序与中序确定二叉树】

后序序列中，最后一个结点一定是根结点

在中序序列中，根结点将中序序列分割成左右两个子序列：

• 左子序列：根结点的左子树的中序序列
• 右子序列：根结点的右子树的中序序列

根据这两个序列，在后序序列中找出对应的序列，然后如此递归下去，即可确定唯一的一棵二叉树

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
BiTree createPostInTree(char post[], char in[], int inStart, int inEnd, int n) { //后序中序构造二叉链表
    static int postIndex = n - 1; //注意此处为静态变量

    if (inStart > inEnd)
        return NULL;

    BiTNode *root = (BiTNode *)malloc(sizeof(BiTNode));
    root->data = post[postIndex--]; //取出后序序列最后1个结点作为根结点
    root->lchild = NULL;
    root->rchild = NULL;

    if (inStart == inEnd) //结点没有孩子则返回
        return root;
    
    //查找根结点在中序序列中的位置
    int inIndex;
    for (inIndex = inStart; inIndex <= inEnd; inIndex++)
        if (in[inIndex] == root->data)
            break;

    //利用中序序列递归构造左子树与右子树，注意先右后左
    root->rchild = createPostInTree(post, in, inIndex + 1, inEnd, n);
    root->lchild = createPostInTree(post, in, inStart, inIndex - 1, n);
}
int main() {
    char in[6] = {'D', 'B', 'E', 'A', 'C'};
    char post[6] = {'D', 'E', 'B', 'C', 'A'};
    int n = 5;
    BiTree root = createPostInTree(post, in, 0, n - 1, n);
    //do something
    system("pause");
    return 0;
}

【层序与中序确定二叉树】

层序序列中，第一个结点一定是根结点，之后的结点从左到右从上到下按顺序编号

在中序序列中，根结点将中序序列分割成左右两个子序列：

• 左子序列：根结点的左子树的中序序列
• 右子序列：根结点的右子树的中序序列

根据这两个序列，在层序序列中找出对应的序列，然后如此递归下去，即可确定唯一的一棵二叉树