NowCoder刷题(1)【树】二叉树的遍历(含图解)

二叉树的遍历(IO型)

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目描述

如图所示的这棵树

前序输出结果为

A-B-D-#-#-E-#-#-C-#-#

还原过程

示例1

示例2

——前序遍历还原

代码实现：

#include<stdio.h>
//定义一棵树的结构
typedef struct TreeNode
{
  struct TreeNode* left;
  struct TreeNode* right;
  char val;
}TreeNode;
//根据前序遍历还原这棵树
TreeNode* CreatBackTree(char* a, int* i)
{
  if (a[*i] == '#')
  {
    //井号说明该结点为空
    ++(*i);
        return NULL;
  }
  TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  if (root == NULL)
  {
    printf("malloc is fail");
    exit(-1);
  }
  root->val = a[*i];
  (*i)++;
  root->left = CreatBackTree(a, i);//构建子树的时候还是从这个结点开始
  root->right = CreatBackTree(a, i);
  return root;
} 
//中序遍历
void InOrderTree(TreeNode* root)
{
  if (root == NULL)
  {
    return;
  }
  InOrderTree(root->left);
  printf("%c ", root->val);
  InOrderTree(root->right);
}
int main(void)
{
  //输入一个字符数组
  char arry[100];
  scanf("%s", arry);//输入字符串不用取地址符
  int i = 0;
  TreeNode* root = CreatBackTree(arry, &i);
  InOrderTree(root);
  return 0;
}

图解:

(点击放大，配合ctrl+滚轮缩放查看)