NowCoder刷题(1)【树】二叉树的遍历(含图解)
二叉树的遍历(IO型)
题目描述
如图所示的这棵树
前序输出结果为
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+滚轮缩放查看)