The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

已知先序+中序遍历求后序遍历

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///                                    Pre_in_to_pos class
///        此类封装了能够将树的先序遍历和中序遍历转化成后序遍历的操作(AC北大pku2255)
///                                                    -By abilitytao
///                                                            2009年5月24日
//////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM/////////////////////////////////////

class Pre_in_to_pos
{

private:
    
string pre;
    
string in;
    
string post;
    
void trans(string a,string b);
public:
    Pre_in_to_pos()
    
{

        pre.erase();
        
in.erase();
        post.erase();
    }

    
int inputpre();
    
int inputpre(string a)
    
{

        pre
=a;
        
return 1;
    }

    
int inputin();
    
int inputin(string a)
    
{

        
in=a;
        
return 1;
    }


    
void trans();
    
void output();
    
void clear();
}
;

int Pre_in_to_pos::inputpre()
{

    cin
>>pre;
    
return 1;
}


int Pre_in_to_pos::inputin()
{

    cin
>>in;
    
return 1;
}


void Pre_in_to_pos::trans(string a,string b)
{

    
int k=a.find(b.substr(0,1));
    
if(k>0)
        trans(a.substr(
0,k),b.substr(1,k));
    
if(k<a.length()-1)
        trans(a.substr(k
+1,a.length()-1-k),b.substr(k+1,b.length()-1-k));
    post
+=a[k];
}


void Pre_in_to_pos::trans()
{
    post.erase();
    trans(
in,pre);
}


void Pre_in_to_pos::output()
{

    cout
<<post;
}
//没有预置回车;


/**//////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM/////////////////////////////

posted on 2009-05-24 01:44 abilitytao 阅读(394) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理