这是一个经常遇到的问题，今天再次遇到了，重新把它写一下。
（该图来自http://baike.baidu.com/view/1898358.htm）
如上图所示为一棵二叉树，其三种遍历的顺序依次为：
先序遍历：ABDECF
中序遍历：DBEAFC
求后序遍历。
思路：根据先序遍历，可以确立A为其根节点，中序遍历的序列中A左边的为其左子树，右边为其右子树，可以根据这一思路来进行二叉树的构建
关键点：左子树在中序遍历中为DBE在先序遍历中为BDE，即长度相等
可以结合字符串处理等相关的函数不难写出程序。
二叉树的数据结构：
1 typedef char ElementType; 2 struct NodeType; 3 typedef struct NodeType * TreePoint; 4 5 struct NodeType 6 { 7 ElementType nodeid; 8 TreePoint leftnode; 9 TreePoint rightnode; 10 };
处理函数：
1 void premidBuildtree(char* pre, char * mid, TreePoint root) 2 { 3 int len = strlen(pre); 4 5 if(len == 0) 6 { 7 return; 8 } 9 10 char *p = strchr(mid,pre[0]); 11 int pos = (int)(p-mid+1); 12 root->nodeid = pre[0]; 13 if(pos != 1) 14 { 15 TreePoint childleft = new NodeType; 16 root->leftnode = childleft; 17 childleft->nodeid = pre[1]; 18 childleft->leftnode = NULL; 19 childleft->rightnode = NULL; 20 char * leftprechar = new char[pos]; 21 char * leftmidchar = new char[pos]; 22 strncpy(leftprechar,pre+1,pos-1); 23 leftprechar[pos-1]=' '; 24 strncpy(leftmidchar,mid,pos-1); 25 leftmidchar[pos-1]=' '; 26 premidBuildtree(leftprechar,leftmidchar,childleft); 27 } 28 29 if(pos != len) 30 { 31 TreePoint childright = new NodeType; 32 root->rightnode = childright; 33 childright->nodeid = pre[pos]; 34 childright->leftnode = NULL; 35 childright->rightnode = NULL; 36 char * rightprechar = new char[len - pos +1]; 37 char * rightmidchar = new char[len - pos +1]; 38 strncpy(rightprechar,pre+pos,len-pos); 39 rightprechar[len - pos] = ' '; 40 strncpy(rightmidchar,mid+pos,len-pos); 41 rightmidchar[len - pos] = ' '; 42 premidBuildtree(rightprechar,rightmidchar,childright); 43 44 } 45 46 }
这个代码的实现，参考了http://www.cnblogs.com/zhangchaoyang/articles/2008434.html这篇文章，在这里，谢谢作者提供的清晰的思路和详细的注释！
我实现的过程主要遇到的问题：
- strncpy()函数，并不会在拷贝结束的字符串后面默认添加‘ ’，这个过程需要自己来做，否则在vs2010当中编译会产生问题，该函数的描述请见：http://www.cplusplus.com/reference/cstring/strncpy/
- strlen()函数取得的C风格字符串的长度值不包含最后' '的长度
- 该版本是实现的递归算法，该问题有非递归算法，随后整理