首页 > 代码库 > 数据结构之二叉树 树结构练习---二叉排序树
数据结构之二叉树 树结构练习---二叉排序树
二叉排序树
Time Limit: 1000MS Memory limit: 65536K
题目描述
二叉排序树的定义是：或者是一棵空树，或者是 具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树
输入
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)
输出
示例输入
21234567899876543214321567890
示例输出
YESNO
排序二叉树的序列就是：二叉树的中序序列 ！
只需要把建立成的二叉排序树 进行先序和后序遍历， 看看给的序列序列是不是这两者之一，如果是就“YES”； else “NO”；
代码：
#include <iostream>#include <iomanip>#include <string>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>#include <vector>using namespace std;typedef struct node{ char data; struct node *ll; struct node *rr;}Binode, *Bitree;void Creat_Sort_Bitree(Bitree &root, int key ){ if(root==NULL) { root=new Binode; root->ll=NULL; root->rr=NULL; root->data=http://www.mamicode.com/key;"%s", a); int len=strlen(a); root=NULL; for(i=0; i<len; i++) { Creat_Sort_Bitree(root, a[i]); } e=0; Pre_order(root); s1[e]=‘\0‘; e=0; Post_order(root); s2[e]=‘\0‘; char s[50]; for(i=0; i<n; i++) { scanf("%s", s); if(strcmp(s1, s)==0 || strcmp(s2, s)==0 ) { cout<<"YES\n"; } else { cout<<"NO\n"; } } } return 0;}
数据结构之二叉树 树结构练习---二叉排序树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。