中序，先序生成树算法

输入两个串：

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_ti = midOrder.find(node);
size_tj = 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<T>* 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<T>* subroot = new Node<T>(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<T>* 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<int>* subroot = new TreeNode<int>(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;
}