刚点开这道题以后，我的反应是：
1.打开老师发的PPT：DS-Chap6，然后翻到第70页；
2.跟着图解，自己照着画了三四遍（其实是抄了三四遍；
3.然后自己出了一个比较简单的题：
先序：ABDCE
中序：BDACE
因为这个简单，用的步骤少，反复做几次用的时间少，容易出思路，所以我就以它为例，自己想着构建了一棵二叉树。
4.把3.中的二叉树画了十来遍之后，心里大概有了个谱，然后在二叉树上每一次笔动一下，都问自己两个问题：1.为什么这样做？2.下一步该怎么做？每一次问完自己后，就把这2个问题的答案按顺序和层次写下来。（我发现，对于这2个问题的答案，就是代码直接翻译过来以后的结果
5.接着我回头看4.中写下来的答案，找出相同答案部分，这相同的部分就是递归函数的函数体。然后整理4.中写下来的答案。
6.然后，我在纸上把5.整理后的答案直接翻译成C代码
7.下面是惯例的一步：我在Dev上，用了10分钟把代码照着纸上写的敲了进去，然后又用了10分钟写了下主函数中的输入输出部分。
8.用了下面这个思路简单，步骤很少的例子测试，发现黑框框里没反应：
9.然后一步步调试，发现原因呢，是因为一级指针不够用，所以引入了二级指针。
10.修改成二级指针后，反反复复又改了很多遍（改的都是些带不带*，带不带&，然后变量名是不是对应上了这些问题，而递归思路却是正确的，所以没有改递归思路）。
11.最后再去提交，就成功AC啦！
好了，现在分享源码啦：
#include#include #include #include typedef char DataType; typedef struct BinTreeNode{ DataType info; struct BinTreeNode* lchild; struct BinTreeNode* rchild; }BinTreeNode,*PBinTreeNode; void InitializeBinTreeNode(PBinTreeNode PNode){ //初始化二叉树中的单个结点 PNode->info='0'; PNode->lchild=NULL; PNode->rchild=NULL; } PBinTreeNode CreateBinTreeNode(){ //创建二叉树中的单个结点 PBinTreeNode PNode=(PBinTreeNode)malloc(sizeof(BinTreeNode)); if(PNode==NULL){ printf("out of space!"); }else{ InitializeBinTreeNode(PNode); return PNode; } } PBinTreeNode Recursion(char **pp_pre,char *begin,char *end){ //根据先序和中序，创建一棵完整二叉树 PBinTreeNode cur=CreateBinTreeNode(); cur->info=**pp_pre; char *temp; for(temp=begin;((*temp)!=(**pp_pre))&&(temp<=end);temp++); if(begin!=temp){ (*pp_pre)++; cur->lchild=Recursion(pp_pre,begin,temp-1); }else{ cur->lchild=NULL; } if(temp!=end){ (*pp_pre)++; cur->rchild=Recursion(pp_pre,temp+1,end); }else{ cur->rchild=NULL; } return cur; } void PostOrderOutput(PBinTreeNode ptr_node){ //后序遍历一棵二叉树 if(ptr_node->lchild){ PostOrderOutput(ptr_node->lchild); } if(ptr_node->rchild){ PostOrderOutput(ptr_node->rchild); } printf("%c",ptr_node->info); } int main(){ char pre[1000]={0}; char in[1000]={0}; scanf("%s%s",pre,in); char *p_pre=pre; //因为要确保递归过程中，所有函数都用同一个p_pre //所以设置一个二级指针pp_pre char **pp_pre=&p_pre; //下面指针begin和end都只用在数组in中 char *begin=in; char *end=begin+1; for(;*(end+1)!=' 00';end++); //递归构建一棵二叉树 PBinTreeNode tree=Recursion(pp_pre,begin,end); //后序输出一棵二叉树 PostOrderOutput(tree); return 0; }
