#include <iostream>
#include <string>
using namespace std;
//重構二叉樹
struct NODE
{
NODE *pLeft;
NODE *pRight;
char value;
};
NODE* Rebuild(string preOrder,string inOrder)
{
if (preOrder.size()==0)
{
return NULL;
}
NODE* pRoot=new NODE;
(pRoot)->value=preOrder[0];
int root_pos=inOrder.find_first_of(preOrder[0]);//找根節點的位置
if (root_pos==-1)
{
return NULL;
}
int left_ele_num=root_pos;
int right_ele_num=preOrder.size()-left_ele_num-1;//length是字符序列的長度
pRoot->pLeft=Rebuild(preOrder.substr(1,1+left_ele_num),inOrder.substr(0,left_ele_num));
pRoot->pRight=Rebuild(preOrder.substr(root_pos+1,right_ele_num),inOrder.substr(root_pos+1,right_ele_num));
return pRoot;
}
void preOrder(NODE *root)
{
if (!root)
{
return;
}
cout<<root->value<<" ";
preOrder(root->pLeft);
preOrder(root->pRight);
}
void main()
{
string preorder="abdcef";
string inorder="dbaecf";
NODE *root=Rebuild(preorder,inorder);
preOrder(root);
cout<<endl;
}
Homepage:
http://www.zoumin.org/