二叉树遍历（牛客网）

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

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

输出描述：

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

个字符后面都有一个空格。 每个输出结果占一行。

输入：abc##de#g##f###  输出：c b e g d f a

这一题很多人其实连题目都没有读懂到底是什么意思？它是要我们表达什么，或者是要我们干什么。其实它就是说给我们一组字符串，然后要我们把这个字符串先构建成一个二叉树，然后在把这个二叉数用中序遍历来输出结果就可以了。

我们一步一步的来解决这个问题

一.初始化

我们先要有个大局观，先把主函数写了，先把一个主要的思路完成，这个题目我们的思路就是

int main() { char str[100];//创建字符数组 scanf("%s",str); int i=0; TNode*root=CreateTree(str,&i);将字符数据变成二叉树 Inorder(root);中序遍历 return 0; }

当然我们还需要先初始化一个二叉树

typedef struct TreeNode { struct TreeNode* left; struct TreeNode* right; char val; }TNode; 二.创建二叉树

TNode*CreateTree(char*a,int*pi)；

首先先把char*a,int*pi传过去，一个是数组名，一个是下标

然后就是第一个判断，如果在字符中出现了#，说明是空，所以我们要下标++，直接返回NULL，这个也为后面的递归做了条件

if(a[*pi]=='#') { (*pi)++; return NULL; }

首先我们要为根节点开辟空间，如果是空，就要报错，如果不是空，我们就把数组的数据存放到这个根节点里面，然后要它向后走，进入递归，先左在右，进入左了之后，原左孩子变成了根节点，就继续走。知道把字符数据都遍历到二叉树中去

TNode*root=( TNode*)malloc(sizeof(TNode)); if(root==NULL) { printf("mallco fail\n"); exit(-1); } root->val=a[*pi]; (*pi)++; root->left=CreateTree(a,pi); root->right=CreateTree(a,pi); 整体 TNode*CreateTree(char*a,int*pi) { if(a[*pi]=='#') { (*pi)++; return NULL; } TNode*root=( TNode*)malloc(sizeof(TNode)); if(root==NULL) { printf("mallco fail\n"); exit(-1); } root->val=a[*pi]; (*pi)++; root->left=CreateTree(a,pi); root->right=CreateTree(a,pi); return root; } 三.中序遍历 void Inorder(TNode*root) { if(root==NULL) return; Inorder(root->left); printf("%c ",root->val); Inorder(root->right); }

---

总结

然后就结束了

我认为这个题目难就难在创建二叉树，和题目的意思，只有意思理解了就好做了