中序，先序生成树算法

输入两个串：

string midOrder = “HDIBJEKALFMCNGO”;
string firstOrder = “ABDHIEJKCFLMGNO”;

输出一棵二叉树。

算法思想很简单，在先序中的第一个节点一定是根节点，此节点在中序中的位置可以将中序分为左右两棵子树。如：

根为A,中序分为：HDIBJEK     A   LFMCNGO,这两棵子树在使用同样的方法就生成一棵树。

//
核心算法

Node * SetTree( string & midOrder, string & firstOrder)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/
ContractedBlock.gif) … {

if (midOrder.length() == 1 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

return new Node(midOrder);
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

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;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kEnd.gif) }

中序遍历和后序遍历生成树的算法类似实现。

这里因为每次递归会生成多份string,也创建了大量的额外空间，所以改进此算法，只提供下标即可：

Node* CreateTreeHelp(const char* pre_order, int p_start, int p_end, const
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* subroot
= new Node(subroot_data); //
这里用先序的第一个节点切分中序，中序的左部节点的个数再切分先序，将中序的左部和先序的去除第一个节点，切分后的部分出入递归。 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* CreateTreeHelp(const char* pre_order, int p_start, int p_end,
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(subroot_data); const char * tmp =
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; }