题目：二叉树遍历
题目详情：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）；
例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树；
建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果
输入描述：
输入包括1行字符串，长度不超过100
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行
示例1：
输入：abc##de#g##f###
输出：c b e g d f a
以上呢就是题目的介绍了，言之呢就是让我们用一组前序遍历字符串组成一颗二叉树，然后再用中序遍历打印出来；
那具体要怎么实现呢？我们且来分析一下！
我们首先得了解一下前序遍历字符串的构成，以及他们之间的关系；
我们知道用前序遍历来遍历树的访问顺序是：根结点-->左子树-->右子树
咱们看下前序遍历的代码：
//前序遍历 void PrevOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); }
就用上面那个示例为例，我们首先得用这组字符串逆推组成二叉树，这是必要的！那要怎么推呢？就根据它的访问顺序即可，下面我们就来推演一下；
前序遍历字符串是：abc##de#g##f###
首先访问的是根结点所以 a 为根结点：
前序遍历字符串是：abc##de#g##f###
然后访问 a 的左子树 b ；
前序遍历字符串是：abc##de#g##f###
然后访问 b 的左子树 c ；
前序遍历字符串是：abc##de#g##f###
然后访问 c 的左子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 c ；
然后访问 c 的右子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 c ；
然后对结点 c 访问结束返回到结点 b ；
然后访问 b 的右子树 d ；
前序遍历字符串是：abc##de#g##f###
然后访问 d 的左子树 e；
前序遍历字符串是：abc##de#g##f###
然后访问 e 的左子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 e ；
然后访问 e 的右子树 g ；
前序遍历字符串是：abc##de#g##f###
然后访问 g 的左子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 g ；
然后访问 g 的右子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 g ；
然后对结点 g 访问结束返回到结点 e ；
然后访问 e 的右子树 f ；
前序遍历字符串是：abc##de#g##f###
然后访问 f 的左子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 f ；
然后访问 f 的右子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 f ；
然后对结点 f 访问结束返回到结点 d；
然后对结点 d 访问结束返回到结点 b ；
然后对结点 b 访问结束返回到结点 a ；
然后访问 a 的右子树 #；
前序遍历字符串是：abc##de#g##f###
因为 # 代表 NULL 所以返回到结点 a ；
然后遍历也就结束了，就这么简单，思路捋清楚了，图画好了自然水到渠成；
树图示：
以上就是用这组字符串逆推组成二叉树的演绎了；
然后我们就要用代码来表示这一切了！
我们先完成主函数里的框架然后再逐步实现，首先我们创建一个数组，内容用 gets( ) 函数来输入，然后就是用字符串来构造二叉树，然后再中序遍历打印树就 ok 了；
int main() { char arr[100]={0}; //输出字符串 gets(arr); int i=0; //构造树 BTNode* root=Great(arr,&i); //中序遍历打印 PrevOrder(root); return 0; }
然后我们来实现构造树函数 Great（arr，&i）；
用前序遍历的方式（根结点-->左子树-->右子树）思路就是上述的图解，如果值为 # 就是 NULL ，直接返回 NULL ，不过 i i 要继续往后走，然后构造树结点，然后先让左子树也如此递归，然后就是右子树也递归构造结点，再返回根结点即可；
BTNode* Great(char* arr,int* i) { if(arr[(*i)]=='#') { (*i)++; return NULL; } BTNode* root=BuyNode(arr[(*i)++]); root->left=Great(arr,i); root->right=Great(arr,i); return root; }
首先简单搭建一下树的基本信息；
typedef char BTDataType; //二叉链 typedef struct BinaryTreeNode { BTDataType data; // 当前结点值域 struct BinaryTreeNode* left; // 指向当前节点左孩子 struct BinaryTreeNode* right; // 指向当前节点右孩子 }BTNode;
实现 BuyNode(arr[(*i)++])，动态创立新结点；
//动态创立新结点 BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); assert(newnode); newnode->data = x; newnode->left = NULL; newnode->right = NULL; return newnode; }
然后再中序遍历（PrevOrder(root)）打印树值即可；
void PrevOrder(BTNode* root) { if(root==NULL) { return; } PrevOrder(root->left); printf("%c ",root->data); PrevOrder(root->right); }
然后就。。。
源代码：
#include<stdio.h> #include<assert.h> #include<stdlib.h> typedef char BTDataType; //二叉链 typedef struct BinaryTreeNode { BTDataType data; // 当前结点值域 struct BinaryTreeNode* left; // 指向当前节点左孩子 struct BinaryTreeNode* right; // 指向当前节点右孩子 }BTNode; //动态创立新结点 BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); assert(newnode); newnode->data = x; newnode->left = NULL; newnode->right = NULL; return newnode; } BTNode* Great(char* arr,int* i) { if(arr[(*i)]=='#') { (*i)++; return NULL; } BTNode* root=BuyNode(arr[(*i)++]); root->left=Great(arr,i); root->right=Great(arr,i); return root; } void PrevOrder(BTNode* root) { if(root==NULL) { return; } PrevOrder(root->left); printf("%c ",root->data); PrevOrder(root->right); } int main() { char arr[100]={0}; gets(arr); int i=0; BTNode* root=Great(arr,&i); PrevOrder(root); return 0; }
加油加油，冲冲冲！
后面博主会陆续更新；
如有不足之处欢迎来补充交流！
完结。
