hdu3791二叉搜索樹

 
又是二叉搜索樹的前序遍歷。
 
1.建樹會順序影響整棵樹的形狀
2.記得釋放資源
3.可以用雙重指針和引用優化程序。。
 
代碼某些printf() 是之前設置的斷點，，可以無視之
[cpp] 
#include<iostream> 
using namespace std; 
 
struct BST 
{ 
    char ch; 
    BST *lson,*rson; 
    BST() 
    { 
        ch=0;                   //不可能的字符  
        lson=rson=0; 
    } 
} *root; 
 
BST *insert(BST *p,char x)       //一,p不存在; 二,p存在,1.x==p->ch 2.x< 3.x>   
{//printf("x=%c p==%d\n",x,p);; 
    if(p==NULL) 
    { 
        p=new BST; 
        p->ch=x; 
        return p; 
    } 
//  printf("~"); 
    if(x<p->ch)   p->lson=insert(p->lson,x); 
    if(x>p->ch)   p->rson=insert(p->rson,x); 
    return p; 
} 
 
char RE[11];int nRE; 
void pre_order(BST *p) //一,p存在 二,p不存在 
{ 
    if(p)   RE[nRE++]=p->ch; 
//  cout<<"RE="<<RE<<endl; 
    if(p->lson) pre_order(p->lson); 
    if(p->rson) pre_order(p->rson); 
} 
 
void Free(BST *p) 
{ 
    if(p->lson) Free(p->lson); 
    if(p->rson) Free(p->rson); 
    delete p; 
} 
 
int main() 
{ 
    int n,i,j,len; 
    char t[11],model[11]; 
    while(scanf("%d",&n),n) 
    { 
        root=0; 
        scanf("%s",t); 
        len=strlen(t); 
        for(i=0;i<len;i++) root=insert(root,t[i]); 
         
        nRE=0;pre_order(root);RE[nRE]='\0'; 
        strcpy(model,RE); 
         
        for(i=1;i<=n;i++) 
        { 
            BST *p=0;//printf("~"); 
            scanf("%s",t);len=strlen(t);// printf("!!%s\n",t); 
            for(j=0;j<len;j++) p=insert(p,t[j]); 
             
            nRE=0;pre_order(p);RE[nRE]='\0'; 
            if(strcmp(model,RE)==0) printf("YES\n"); 
            else    printf("NO\n"); 
            Free(p); 
        } 
    //  printf("@"); 
        Free(root); 
    } 
    return 0; 
}