九度OnlineJudge之1009：二叉搜索树
题目描述： #include <iostream>#include <cstring>using namespace std;struct Node//二叉树结点结构体{Node *lchild;//左儿子指针Node *rchild;//右儿子指针int c;//结点字符信息}Tree[110];//静态内存分配数组int loc;//静态数组中已经分配的结点个数Node *create()//申请一个结点空间，返回指向其的指针{Tree[loc].lchild = Tree[loc].rchild = NULL;//初始化左右儿子为空return &Tree[loc++];//返回指针，loc自增}char stra[25],strb[25];//stra由原序列经过先序遍历和中序遍历所产生的序列，strb由待比较序列先序和中序遍历产生int k=0;//计数void preOrder(Node *T)//先序遍历{stra[k++] = T->c +'0';if (T->lchild!=NULL)preOrder(T->lchild);if (T->rchild!=NULL)preOrder(T->rchild);}void inOrder(Node *T)//中序遍历{if (T->lchild!=NULL)inOrder(T->lchild);stra[k++] = T->c +'0';if (T->rchild!=NULL)inOrder(T->rchild);}/*void postOrder(Node *T)//后序遍历{if (T->lchild!=NULL)postOrder(T->lchild);if (T->rchild!=NULL)postOrder(T->rchild); cout<<T->c<<" ";}*/Node* insert(Node* root,int value){if (root==NULL)//若当前树为空{root = create();root->c = value;return root;}elseif (root->c <value){root->rchild = insert(root->rchild,value);}else if(root->c > value){root->lchild = insert(root->lchild,value);}return root;}int main(){int n;while(cin>>n,n!=0){loc = 0;char str[25];//原序列cin>>str;int len = strlen(str);//长度 Node *root = NULL; for (int i=0;i<len;i++) root = insert(root,str[i]-'0'); k = 0; memset(stra,0,sizeof(stra)); preOrder(root); inOrder(root); strcpy(strb,stra); while(n--) { char str1[11];//待比较序列 cin>>str1; int len1 = strlen(str1); Node * T = NULL; for (int i=0;i<len1;i++) T = insert(T,str1[i]-'0'); k = 0; memset(stra,0,sizeof(stra)); preOrder(T); inOrder(T);if (strcmp(strb,stra)==0) cout<<"YES"<<endl; else cout<<"NO"<<endl; }} // system("pause");return 0;}
