九度OnlineJudge之1009:二叉搜索树

发布时间:2017-1-23 16:33:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"九度OnlineJudge之1009:二叉搜索树",主要涉及到九度OnlineJudge之1009:二叉搜索树方面的内容,对于九度OnlineJudge之1009:二叉搜索树感兴趣的同学可以参考一下。

题目描述:                        判断两序列是否为同一二叉搜索树序列 输入:                        开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。 输出:                        如果序列相同则输出YES,否则输出NO 样例输入:                        2 567432 543267 576342 0 样例输出:                        YES NO #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; } else if (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; }

上一篇:jquery操作cookie
下一篇:.net

相关文章

相关评论