二叉树遍历（C语言版）

 前序遍历创建树，中序遍历把创建出来的二叉树的结点打印出来

题目链接：牛客网-二叉树遍历

    前序遍历创建树的思想：

    把每个结点看作是子树的根节点，以根左右的顺序创建一整棵二叉树

    1.空 返回空

    2.非空 先是malloc一个结点，作为根节点；然后让根的left指向左子树，让根的right指向右子树

    假设s为字符串，i为字符串数组下标；左子树可以通过root->left = Create(s, i)得到，右子树可以通过root->right = Create(s, i)得到，创建完整棵树（子树）以后，返回root（整棵树/整棵子树的根节点）；由于递归的特性，这边得到的不是单一左节点or右节点，而是一整个子树

typedef struct BintreeNode
{
    char val;
    struct BintreeNode* left;
    struct BintreeNode* right;
}Tnode;



Tnode* Create(char s[],int* i)
{
    if(s[*i] == '#') //空
        {
            (*i)++;
            return NULL;
        }
    
    //非空
    Tnode* root = (Tnode*)malloc(sizeof(Tnode));
    root->val = s[(*i)++];
    root->left = Create(s, i);
    root->right = Create(s, i);
    return root;
}

然后对创建出来的整棵树进行中序遍历（左根右），即能成功通过该题；此处需要注意的是，在主函数传参时，要传下标的地址，不然递归时会出现下标没有被保存下来的情况

全部代码：

#include <stdio.h>
#include<stdlib.h>
typedef struct BintreeNode
{
    char val;
    struct BintreeNode* left;
    struct BintreeNode* right;
}Tnode;



Tnode* Create(char s[],int* i)
{
    if(s[*i] == '#') //空
        {
            (*i)++;
            return NULL;
        }
    
    //非空
    Tnode* root = (Tnode*)malloc(sizeof(Tnode));
    root->val = s[(*i)++];
    root->left = Create(s, i);
    root->right = Create(s, i);
    return root;
}

void MidOrder(Tnode* root)//前序遍历
{
    if(root == NULL) return;
    MidOrder(root->left);
    printf("%c ",root->val);
    MidOrder(root->right);
}

int main()
{
    char s[100];
    scanf("%s",s);
    int i = 0;
    Tnode* root = Create(s,&i); // 创建树，返回根节点
    MidOrder(root);
    return 0;
}