二叉树的构建以及遍历

来自牛客的一道OJ题：

问题描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存

储）。 例如如下的先序遍历字符串：ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空

树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括一行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符

串后面都有空格，每个输出占一行。

示例1:

问题分析：

这道题目难的不在中序遍历，难的是如何去构建这颗二叉树，问题描述中提到"#"代表NULL，而且

输入的是二叉树的先序遍历，所以，我们要通过递归先序遍历的方法，来将这段字符串构建成二叉

树，后面的中序遍历就不是问题了，那么如何写先序遍历呢？大家都知道先序遍历的顺序是先跟，

后左子树再右子树，所以我们也通过这种方式来进行递归存储，方法与前序遍历类似，我们先看代

码，再进行分析：

1.创建二叉树代码：

struct Bitree* CreatTree(char* a,int* pi)
{
    if(a[*pi] == #)
    {
        (*pi)++;
        return NULL;
    }

    struct Bitree* root = (struct Bitree*)malloc(sizeof(struct Bitree));

    root->data = a[(*pi)++];
    root->left = CreatTree(a,pi);
    root->right = CreatTree(a,pi);
    return root;
}

可能单看代码我们不能理解递归的本质，接下来我们画图理解：

这应该是你们能看到的递归遍历二叉树的最详细的图了，其中红色线代表向下遍历，绿色代表向上

返回 ，看到这幅图我们就会一目了然，包括每一次遍历和返回，我在画这个图的时候，没有省略

任何一个节点，每一个序号表示的是先后顺序，相信大家看完这个图之后会对二叉树的递归遍历有

更深的理解。

中序遍历相信大家应该都会了，我这里就不过多赘述了，就是先左子树，再跟最后右子树，递归遍

历就可以了

2.中序遍历代码：

void InOrder(struct Bitree* root)
{
    if(root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}

因为这道题需要自己写main函数，自己写输入输出，结构体也要自己写，所以整体代码如下:

#include <stdio.h>
#include<stdlib.h>
struct Bitree
{
    struct Bitree* left;
    struct Bitree* right;
    char data;
};

struct Bitree* CreatTree(char* a,int* pi)
{
    if(a[*pi] == #)
    {
        (*pi)++;
        return NULL;
    }

    struct Bitree* root = (struct Bitree*)malloc(sizeof(struct Bitree));

    root->data = a[(*pi)++];
    root->left = CreatTree(a,pi);
    root->right = CreatTree(a,pi);
    return root;
}

void InOrder(struct Bitree* root)
{
    if(root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}

int main() 
{
    char a[100];
    scanf("%s",a);
    int i =0;
    struct Bitree* ret = CreatTree(a,&i);
    InOrder(ret);     
    return 0;
}