题目1009：二叉搜索树
从现在开始打算重启刷题征程。程序员的人生不需要解释！
这次撇开poj hoj等难度较大的oj系统，从九度入手（已经很长时间没写过代码了），主要先“叫醒” 沉睡依旧的大脑。唉~真的很长时间没写博客，没写代码了，只能加油吧！
题目如下
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：4310
解决：1921
题目描述： 判断两序列是否为同一二叉搜索树序列 输入： 开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。 输出：如果序列相同则输出YES，否则输出NO
样例输入： 2 567432 543267 576342 0 样例输出： YES NO 来源： 2010年浙江大学计算机及软件工程研究生机试真题
题目难度：水题
解题思路：
1.构建二叉排序树。(题目中叫做二叉搜索树，其时是一样的，就是对于二叉树的任何一个结点的所有左孩子结点都小于父结点，但是父节点都小于右孩子结点，好吧，我既然还能记得住，看来，大脑锈的不是很厉害)
2.对构建的二叉排序树尽心前序遍历，得到前序序列。（前序就是 前根序，后序就是 后根序，中序就是 中根序）
3.比较前根序列，一样就输出YES ，不一样就输出 NO
c++代码：
[cpp] view plain copy print? #include <iostream> #include <string.h> using namespace std; struct Node{ Node* left ; Node* right ; char data ; Node():left(NULL),right(NULL),data('*'){} }; //插入有序树 void insertSortTree(Node * root, char data){ Node * p = root ; Node * q = new Node ; q->data = data ; while(1){ if(p->data>data&&p->left)p=p->left; else if(p->data<data&&p->right)p=p->right; else if(p->data>data){ p->left = q ; return; } else if(p->data<data){ p->right = q ; return; } } } //销毁有序树 void destroySortTree(Node * root){ Node * p = root ; if(p->left!=NULL)destroySortTree(p->left); if(p->right!=NULL)destroySortTree(p->right); delete p ; } //创建有序树 Node * createSortTree(char * datas , int n){ if(n<=0)return NULL; Node * root = new Node ; root->data = datas[0]; Node * p = root ; for(int i = 1 ; i < n ;i++){ insertSortTree(root,datas[i]); } return root ; } //用到的变量 char x1[11];int ct1 = 0; char x2[11];int ct2 = 0; //前根序遍历 void pre_lst(Node * root,char* x,int* index){ if(root)x[(*index)++] = root->data ; if(root->left)pre_lst(root->left,x,index) ; if(root->right)pre_lst(root->right,x,index) ; } //比较前根序列 bool cmp(int n){ for(int i = 0 ; i < n ; i++){ if(x1[i]!=x2[i])return false; } return true ; } int main() { int T ; int n; Node * root1 = NULL; Node * root2 = NULL; int index1 ,index2 ; while(1){ cin>>T ;if(T==0)break; cin>>x1 ; ct1 = strlen(x1); root1 = createSortTree(x1,ct1); index1 = 0 ; pre_lst(root1,x1,&index1) ; for(int i = 0 ; i < T ; i++ ){ cin>>x2 ; ct2 = strlen(x2); root2 = createSortTree(x2,ct2); index2 = 0 ; pre_lst(root2,x2,&index2) ; if(cmp(ct1)){ cout<<"YES"<<endl; }else cout<<"NO"<<endl; destroySortTree(root2) ; } destroySortTree(root1) ; } return 0; }
好了，写代码的感觉来了。
转载于:https://www.cnblogs.com/yzm10/p/7227961.html
相关资源：二叉搜索树的c++实现