中序，先序生成树算法

输入两个串：

 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<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; }