题解 | 二叉树遍历

#include <stdio.h>
#include <stdlib.h>

 typedef struct TreeNode
 {
    char val;
    struct TreeNode* left;//在结构体内部引用自身类型时，必须使用完整的结构体标签,所 以会有struct
    struct TreeNode* right;
 }TreeNode;

TreeNode* MakeTree(char* arr,int* count)//TreeNode*目的是为了定义函数的返回值类型必须为结指向构体TreeNode的指针
{
    if(arr[(*count)]=='#'||arr[(*count)]=='\0')
    {
        return NULL;
    }
    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));//动态分配大小为结构体TreeNode成员所需大小的新的内存空间，并将空间的类型强制转为TreeNode*，并将空间命名为newnode(新节点)
    newnode ->val=arr[(*count)++];//新节点的val=arr[*count],并让count++
    newnode ->left=MakeTree(arr,count);//新节点的左孩子开始递归（递归到返回Null的时候递归结束）
    (*count)++;//跳过值为Null的指针
    newnode ->right=MakeTree(arr,count);//新节点的右孩子开始递归（递归到Null结束）
    return newnode;//回到上一层递归的根节点
}

void zhongxu(TreeNode* root)//中序输出函数
{
    if(root==NULL)//如果节点为空返回空
    {
        return;
    }
    zhongxu(root ->left);//递归遍历左孩子
    printf("%c ", root->val);//左孩子遇到空值则返回上一个节点（上一层递归）的root的值
    zhongxu(root ->right);//递归遍历右孩子
}

int main() {
    char arr[101];
    int count=0;
    while (scanf("%s", &arr) != EOF) 
    { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
        TreeNode* Tree=MakeTree(arr, &count);
        zhongxu(Tree);
        
    }
    return 0;
}