数据结构实验之查找一：二叉排序树 （SDUT 3373）
2024-08-27 03:47:58
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
int data;
struct node *l, *r;
};
struct node *creat(struct node *root,int x)
{
if(root == NULL) // 如果 root 是空，表示当前是可以把这个点加进去的，就可以放进去了
{
root = new node;
root -> data = x;
root -> l = NULL;
root -> r = NULL;
}
else { //如果不是，考虑两种情况
if(x > root -> data) //如果比当前的根节点大，去右子树找
root -> r = creat(root -> r, x);
else
root -> l = creat(root -> l, x); // 否则去左子树找
}
return root; //别忘记了返回树根！
};
int ok(struct node *t1, struct node *t2) // 判断两个树是否相同
{
if(t1 == NULL && t2 == NULL) // 如果比较到最下层都没有发现不同的就返回 1
return 1;
else if(t1 != NULL && t2 != NULL) // 如果没有到最下层，继续向下找
{
if(t1 -> data != t2 -> data) // 如果一旦发现不同的，就不满足了
{
return 0;
}
else if((ok( t1 -> l , t2 -> l) && ok(t1 -> r, t2 -> r))){ // 分别的左子树、右子树都要满足
return 1;
}
}
else return 0;
}
int a[55];
int b[55];
int main()
{
int n,m;
while(scanf("%d",&n)!=EOF && n)
{
scanf("%d",&m);
struct node *root1,*root2; // 这里需要树根节点（指针）
for(int i = 0; i < n; i ++) { // 先输入
scanf("%d",&a[i]);
}
root1 = new node;
root1 -> data = a[0]; // 把根放进去
root1 -> l = root1 -> r = NULL; // 左右结点初始化
for(int i = 1; i < n; i ++){ // 建树
root1 = creat(root1,a[i]);
}
while(m --)
{
for(int i = 0; i < n; i ++){ // 相同的建树方法
scanf("%d",&b[i]);
}
root2 = new node;
root2 -> data = b[0];
root2 -> l = root2 -> r = NULL;
for(int i = 1; i < n; i ++)
{
root2 = creat(root2,b[i]);
}
int f = ok(root1,root2); // 比较
if(f)printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
改了一下建树的时候的不必要的步骤。（感谢wjh小哥哥）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
int data;
struct node *l, *r;
};
struct node *creat(struct node *root,int x)
{
if(root == NULL)
{
root = new node;
root -> data = x;
root -> l = NULL;
root -> r = NULL;
}
else {
if(x > root -> data)
root -> r = creat(root -> r, x);
else
root -> l = creat(root -> l, x);
}
return root;
};
int ok(struct node *t1, struct node *t2)
{
if(t1 == NULL && t2 == NULL)
return 1;
else if(t1 != NULL && t2 != NULL)
{
if(t1 -> data != t2 -> data)
{
return 0;
}
else if((ok( t1 -> l , t2 -> l) && ok(t1 -> r, t2 -> r))){
return 1;
}
}
else return 0;
}
int a[55];
int b[55];
int main()
{
int n,m;
while(scanf("%d",&n)!=EOF && n)
{
scanf("%d",&m);
struct node *root1,*root2;
for(int i = 0; i < n; i ++) {
scanf("%d",&a[i]);
}
root1 = NULL;
for(int i = 0; i < n; i ++){
root1 = creat(root1,a[i]);
}
while(m --)
{
for(int i = 0; i < n; i ++){
scanf("%d",&b[i]);
}
root2 = NULL;
for(int i = 0; i < n; i ++)
{
root2 = creat(root2,b[i]);
}
int f = ok(root1,root2);
if(f)printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
最新文章
- Oracle RAC安装部署文档
- rdlc报表DEMO
- 使用safe-rm替代rm
- C++11多态函数对象包装器
- 转载：iOS 推送的服务端实现
- phaser源码解析（一） Phaser.Utils类下shuffle方法
- UI和UE有什么区别呢？
- SSDB安装配置 ERROR! autoconf required! install autoconf first
- 第31月第19天 NV12
- VS2017 生成事件去除未修改项目
- python学习之第八篇——字典嵌套之字典中嵌套字典
- 34)django-上传文件,图片预览功能实现
- CSS3 傻傻分不清楚的transition, transform 和 animation
- COGS.1272.[AHOI2009]行星序列(线段树 区间加、乘、求和)
- spring boot (入门简介 demo)
- 通过 ulimit 改善系统性能
- 几个简单易懂的排序算法php
- vs ComboBox显示多行
- POJ 3273 Monthly Expense(二分答案)
- 【C语言】指向一维数组元素的指针