Question

根据先序序列和中序序列得到其顺序存储的C语言算法

我想用c语言图形函数写一个通过输入先序序列和中序序列，得到一个用顺序存储的二叉树，然后程序画出这个二叉树。我知道怎么通过这两个序列求二叉树，不过这几天想用算法实现，发现真没办法，我对递归的算法太不熟悉了。希望有大神能帮我写一个算法，输入这两个序列，得到一个数组存储的二叉树。C语言实现， 我现在只学了C语言，C++不大看得懂。谢谢了！

Answer 1

写了一个代码，你去试试

#include <stdio.h>
#include <string.h>
#define MAXSIZE 127
bool fun(char *Pre, char *Indor, char *Seq, int n, int R)
{
    int i, root;
    if(n <= 0)
        return 1;
    for(root = 0; (root < n) && (Indor[root] != Pre[0]); root++);
    if(root >= n)
        return 0;
    Seq[R] = Pre[0];
    for(i = 0; i < R; i++)
        if(Seq[i] == 0)
            Seq[i] = '0';
    bool b1 = fun(Pre + 1, Indor, Seq, root, 2 * R + 1);
    bool b2 = fun(Pre + 1 + root, Indor + root + 1, Seq, n - root - 1, 2 * R + 2);
    return b1 && b2;
}

int main(void)
{
    char Pre[20], Indor[20], Seq[MAXSIZE], n, i;
    bool bCreatOk;
    printf("请输入前序序列:\n");
    scanf("%s", Pre);
    printf("请输入中序序列:\n");
    scanf("%s", Indor);

    n = strlen(Pre);

    for(i = 0; i < MAXSIZE; i++)
        Seq[i] = 0;

    bCreatOk = fun(Pre,Indor, Seq, n, 0);

    if(bCreatOk) {
        printf("构造二叉树成功!其顺序二叉树为:\n");
        for(i = 0; Seq[i]; i++)
            printf("%3c", Seq[i]);
    }
    else printf("不是一棵有效的二叉树!");
    printf("\n");
}

运行结果

Answer 2

网上有严蔚敏数据结构教材里所有算法的实现。可以直接运行的。

Answer 3

请加164403642详谈，写好之后麻烦给分。