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

//

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

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); //

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

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 <

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

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

• 本文作者： 帐前卒
• 本文链接： http://chillyc.info/2007/1957075/
• 版权声明： 本博客所有文章除特别声明外，只能复制超链接地址，且必须注明出处！