洛谷

洛谷_P1305 新二叉树_data_x_y_node1_is_root

//
#include
using namespace std;
#define T char
#define EF '*'

const int N=111;
T ans[N];
int pos;

struct node
{
    T data;
    node *x,*y;
    node( T in=0,node *xx=NULL,node *yy=NULL ):data(in),x(xx),y(yy) {}
}*rr;

node* new_node( T data )
{   
    if( data==EF ) return NULL;                     // EF
    return new node( data );
}

node* find_node( T data,node *root=rr )
{
    if( root->data==data ) return root;
    node *ans=NULL;
    if( root->x ) ans=find_node( data,root->x );    // find_xx
    if( ans ) return ans;                           // ans!=NULL
    if( root->y ) ans=find_node( data,root->y );    // find_yy
    return ans; 
}

void AA( node *root )
{
    if( root==NULL ) return ;
    ans[pos++]=root->data;
    AA( root->x );
    AA( root->y );
}

void BB( node *root )
{
    if( root==NULL ) return ;
    BB( root->x );
    ans[pos++]=root->data;
    BB( root->y );
}

void CC( node *root )
{
    if( root==NULL ) return ;
    CC( root->x );
    CC( root->y );
    ans[pos++]=root->data;
}

void DD( node *root )
{
    if( root==NULL ) return ;

    queue q; node *tt=NULL;
    q.push( root );						// init
    while( !q.empty() )
    {
        tt=q.front(); q.pop();
        ans[pos++]=tt->data;
        if( tt->x ) q.push( tt->x );	// push not front
        if( tt->y ) q.push( tt->y );
    }
}

void delete_tree( node *root )
{
    if( root==NULL ) return ;
    delete_tree( root->x );
    delete_tree( root->y );
    delete root;
}

int main()
{
    int n,i;
    T data,x,y;                         // T
    while( cin>>n )
    {
    	cin>>data>>x>>y;                // init must
        rr=new node( data ); 
		rr->x=new_node( x );
        rr->y=new_node( y );
        
		while( --n )
        {
            cin>>data>>x>>y;
            node *tt=find_node( data );
            tt->x=new_node( x );
            tt->y=new_node( y );
        }
        pos=0; AA( rr );
        for( i=0;i