中序，先序生成树算法
输入两个串：
string midOrder = “HDIBJEKALFMCNGO”;
string firstOrder = “ABDHIEJKCFLMGNO”;
输出一棵二叉树。
算法思想很简单，在先序中的第一个节点一定是根节点，此节点在中序中的位置可以将中序分为左右两棵子树。如：
根为A,中序分为：HDIBJEK A LFMCNGO,这两棵子树在使用同样的方法就生成一棵树。
//
核心算法
Node * SetTree( string & midOrder, string & firstOrder)
  … {
if (midOrder.length() == 1 )
  … {
return new Node(midOrder);
 }
string node = firstOrder.substr( 0 , 1 );
Node * n = new Node(node);
size_t i = midOrder.find(node);
size_t j = firstOrder.find(midOrder.substr(i - 1 , 1 ));
n -> left = SetTree(midOrder.substr( 0 ,i),firstOrder.substr( 1 ,i));
n -> right = SetTree(midOrder.substr(i + 1 ,midOrder.length() - i
- 1 ),firstOrder.substr(j + 1 ,firstOrder.length() - j - 1 ));
return n;
 }
中序遍历和后序遍历生成树的算法类似实现。
这里因为每次递归会生成多份string,也创建了大量的额外空间，所以改进此算法，只提供下标即可：
Node
char* in_order, int i_start, int i_end){ if(p_end < p_start || i_end <
i_start) return NULL; char subroot_data = pre_order[p_start]; int index =
find(in_order,i_start, i_end,subroot_data); index += i_start; Node
= new Node
这里用先序的第一个节点切分中序，中序的左部节点的个数再切分先序，将中序的左部和先序的去除第一个节点，切分后的部分出入递归。 subroot->left =
CreateTreeHelp(pre_order,p_start+1,p_start+index-
i_start,in_order,i_start,index-1); // 用先序的第一个节点切分中序，中序的右部传入，将前面切分先序的第二部分传入
subroot->right = CreateTreeHelp(pre_order,p_start+index-
i_start+1,p_end,in_order,index+1,i_end); return subroot; }
如果思考不清晰，这部分调试起来还是比较困难。需要打印每次递归的信息，最后先使用小数据量，然后打印出来，而不要用gdb调试。源程序是这样打印的：
TreeNode
const char* in_order, int i_start, int i_end, int tabs){ for(int i = 0; i <
tabs; i++){ cout << “.”; } cout <<endl; if(p_end < p_start || i_end < i_start)
return NULL; char subroot_data = pre_order[p_start]; int index =
find(in_order,i_start, i_end,subroot_data); index += i_start; TreeNode
subroot = new TreeNode
pre_order+p_start; while(*tmp != pre_order[p_end+1]){ cout << *tmp<<" “;
tmp++; } cout << endl; tmp = in_order+i_start; while(*tmp !=
in_order[i_end+1]){ cout << *tmp<<” “; tmp++; } cout << endl; cout <<
“index:”<<index<<endl; cout << “p_start:”<<p_start<<” p_end:“<<p_end<<”
i_start:“<<i_start<<” i_end:"<<i_end<<endl; subroot->left =
CreateTreeHelp(pre_order,p_start+1,p_start+index-
i_start,in_order,i_start,index-1,tabs+2); subroot->right =
CreateTreeHelp(pre_order,p_start+index-
i_start+1,p_end,in_order,index+1,i_end,tabs+2); return subroot; }
另外贴上其中的find函数，这里的count其实是找对于start来说的相对位置(师兄说下面这段代码写的很烂，但是烂的凑在一起，竟然没有错，这让我想到了独孤
九剑)：
int find(const char* str, int start, int end,const char& c){ int count = -1;
str = str+start; int len = end-start; while(‘/0’ != *str && count <=len){
count++; if(c == *str) return count; str++; } return -1; }
这是为什么呢？因为里面使用到多个判断标准…所以改为：
int find(const char* str, int start, int end,const char& c){ int count = -1;
str = str+start; const char* str_end = str+end+1; while(*str_end != *str){
count++; if(c == *str++) return count; } return -1; }