利用二叉树的前中序遍历序列再次创建二叉树

前情提要

当时学习class="superseo">数据结构的时候，只是知道如何根据前中序列、后中序列或者层次遍历和中序遍历序列来人工画出一颗二叉树，但是并没有用代码去实现这个过程。

接下来介绍这个代码的思想，先放出全部的代码。

代码

#include 
#define maxsize 100

// 利用前序遍历生成二叉树 并且获得前中序遍历的序列之后，再利用这两个序列生成二叉树！！！

typedef struct node
{
    char data;
    struct node *lchild, *rchild;
} node;
typedef node *bitree;
typedef struct
{
    bitree a[maxsize];
    int top;
} seqstack;
typedef struct
{
    char ch[maxsize];
    int low, high;
} seqlist;

bitree buildtree() // 前序遍历创建二叉树
{
    char c;
    node *p;
    c = getchar();
    if (c == '0')
        return (0);
    p = new (node);
    p->data = c;
    p->lchild = buildtree();
    p->rchild = buildtree();
    return (p);
}

bitree buildtreebyseq(seqlist s1, seqlist s2) // 根据前中序遍历序列创建二叉树
{
    int rt, j, l1, l2, h1, h2;
    l1 = s1.low;
    l2 = s2.low;
    h1 = s1.high;
    h2 = s2.high;
    char c;
    node *p;
    if (s1.low > s1.high || s2.low > s2.high)
        return (0);
    c = s1.ch[s1.low];
    p = new (node);
    p->data = c;
    for (j = s2.low; j <= s2.high; j++)
        if (c == s2.ch[j])
        {
            rt = j;
            break;
        }
    s1.low = l1 + 1;
    s1.high = l1 + rt - l2;
    s2.low = l2;
    s2.high = rt - 1; // s2 用左半段
    p->lchild = buildtreebyseq(s1, s2);
    s1.low = l1 + rt - l2 + 1;
    s1.high = h1;
    s2.low = rt + 1;
    s2.high = h2; // s2用右半段
    p->rchild = buildtreebyseq(s1, s2);
    return (p);
}

void preorder(bitree t, seqlist &spreoder) // 前序遍历非递归
{
    spreoder.low = 0;
    int i = 0;
    seqstack s;
    s.top = -1; //置栈空
    while ((t) || (s.top != -1))
    {
        while (t)
        {
            printf("%c", t->data);
            spreoder.ch[i] = t->data;
            i++;
            s.top++;
            s.a[s.top] = t;
            t = t->lchild;
        }
        if (s.top > -1)
        {
            t = s.a[s.top];
            s.top--;
            t = t->rchild;
        }
    }
    spreoder.high = i - 1;
}

void DLR(node *root) // 前序遍历递归
{
    if (root != NULL) //非空二叉树
    {
        printf("%c", root->data); //访问D
        DLR(root->lchild);        //递归遍历左子树
        DLR(root->rchild);        //递归遍历右子树
    }
}

void midorder(bitree t, seqlist &smidoder) // 中序遍历非递归
{
    smidoder.low = 0;
    int i = 0;
    seqstack s;
    s.top = -1; //置栈空
    while ((t) || (s.top != -1))
    {
        while (t)
        {
            s.top++;
            s.a[s.top] = t;
            t = t->lchild;
        }
        t = s.a[s.top];
        smidoder.ch[i] = t->data;
        i++;
        printf("%c", t->data);
        s.top--;
        t = t->rchild;
    }
    smidoder.high = i - 1;
}

void LDR(node *root) // 中序遍历递归
{
    if (root != NULL)
    {
        LDR(root->lchild);
        printf("%c", root->data);
        LDR(root->rchild);
    }
}

void postorder(bitree t) //非递归后序实现
{
    bitree lastvist;
    seqstack s;
    lastvist = 0;
    s.top = -1; //置栈空
    while (t || s.top != -1)
    {
        while (t)
        {
            s.top++;
            s.a[s.top] = t;
            t = t->lchild;
        }
        t = s.a[s.top];
        if (t->rchild == lastvist || t->rchild == NULL)
        {
            printf("%c", t->data);
            s.top--;
            lastvist = t;
            t = 0;
        }
        else
            t = t->rchild;
    }
}

void LRD(node *root) // 后序遍历递归
{
    if (root != NULL)
    {
        LRD(root->lchild);
        LRD(root->rchild);
        printf("%c", root->data);
    }
}

int main()
{
    seqlist s1, s2;
    bitree t1, t2;
    t1 = buildtree(); //  测试用例：abc00d00e0fg000
    printf("\n第一次生成的二叉树非递归前序遍历结果,并生成前序序列s1\n");
    preorder(t1, s1);
    printf("\n第一次生成的二叉树非递归中序遍历结果,并生成中序序列s2\n");
    midorder(t1, s2);
    t2 = buildtreebyseq(s1, s2);
    printf("\n第二次生成的二叉树前序遍历\n");
    DLR(t2);
    printf("\n第二次生成的二叉树中序遍历\n");
    LDR(t2);
}

思路分析

利用前中序遍历序列来创建二叉树，重点肯定是放在两个序列上。

前序序列是用来找根节点的，根节点都在前序序列的前部分。

中序序列是用来根据前面找到的根节点来划分左右子树的。

所以我们可以通过下标low和high来对两个序列的左右部分进行划分，从而用递归的方法构建出整个二叉树。

过程

1. 第一个for循环，是确定根节点在中序序列的位置，然后用rt记录下来。

2. 然后开始调整s1和s2的大小。s1的low比较好理解，第一个根节点访问过了，所以跳过，直接+1即可。但是s1的high比较难。l1 + rt - l2这个值代表着分界线，把左子树的所有根节点 和 右子树的所有根节点分开来

3. 然后s2.low = l2 s2.high = rt - 1代表只用s2的左边段，因为s2的左半段是左孩子的全部。然后进入p的左孩子的递归创建。

4. 同理下面s1.low只是+1，往后移了一位，画了图就知道为啥只加1。同理s2，同理递归创建