#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/
Posted on 2010-09-26 16:01 邹敏 阅读(729) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理