数据结构实验之查找一:二叉排序树

简介: 数据结构实验之查找一:二叉排序树 Time Limit: 400MS Memory Limit: 65536KB Problem Description 对应给定的一个序列可以唯一确定一棵二叉排序树。

数据结构实验之查找一:二叉排序树

Time Limit: 400MS  Memory Limit: 65536KB

Problem Description

对应给定的一个序列可以唯一确定一棵二叉排序树。然而,一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树,都得到一样的结果。你的任务书对于输入的各种序列,判断它们是否能生成一样的二叉排序树。

Input

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (n < = 10)和L,分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列生成一颗二叉排序树。随后L行,每行给出N个元素,属于L个需要检查的序列。
简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。

Output

对每一组需要检查的序列,如果其生成的二叉排序树跟初始序列生成的二叉排序树一样,则输出"Yes",否则输出"No"。

Example Input

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

Example Output

Yes
No
No

Code realization

#include <iostream>
using namespace std;
struct node
{
	int data;
	struct node *left,*right;
};
void creat(node *&root,int num)
{
	if(root == NULL)
	{
		root = new node;
		root->data = num;
		root->left = NULL;
		root->right = NULL;
	}
	else
	{
		if(num > root->data)
			creat(root->right,num);
		else
			creat(root->left,num);
	}
}
int compare(node *&root1,node *&root2)
{
	if(root1==NULL && root2==NULL)
		return 1;
	else if(root1->data == root2->data)
		return compare(root1->left,root2->left)&&compare(root1->right,root2->right);
	else
		return 0;
}
int main()
{
	
	int n,l;
	while(cin>>n)
	{
		node *root1,*root2;
		if(n==0)
			break;
		else
		{
			root1 = NULL;
			cin>>l;
			int i;
			for(i=0;i<n;i++)
			{
				int a;
				cin>>a;
				creat(root1,a);
			}
			while(l--)
			{
				root2=NULL;
				for(i=0;i<n;i++)
				{
					int a;
					cin>>a ;
					creat(root2,a);
				}
				if(compare(root1,root2))
					cout<<"Yes"<<endl;
				else
					cout<<"No"<<endl;
			}
		}

	}
	return 0;
}


目录
相关文章
|
2月前
|
存储 算法 编译器
数据结构实验之矩阵的运算器(二维数组)
本实验旨在通过团队合作,掌握数组和矩阵相关运算的代码实现,包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中,成员们需分工协作,解决编程难题,最终实现一个功能完备的矩阵计算器。通过本实验,不仅锻炼了编程能力,还加深了对数学概念的理解,同时培养了团队合作精神。
68 4
|
2月前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术,通过创建文本文件、实现单词计数与定位功能,最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单,以增强对字符串处理的理解与应用能力。
61 4
|
2月前
|
算法
数据结构实验之最长公共子序列
本实验旨在通过编程实践帮助学生理解串的基本概念及求解最长公共子序列的算法。实验内容包括使用动态规划方法设计并实现算法,以找出给定两序列的最大公共子序列。示例代码展示了如何通过构建状态矩阵和回溯路径来找到解决方案。实验总结指出,`memset()`函数用于内存初始化,且对于特定输入,程序能正确输出最长公共子序列之一。
60 4
|
2月前
|
算法
数据结构实验之操作系统打印机管理器问题
本实验旨在通过实现操作系统中的打印机管理器问题,掌握队列的基本操作如入队、出队等,利用队列的先进先出特性解决先申请先打印的问题。实验包括队列的初始化、入队、出队、打印队列内容等功能,并通过菜单式界面进行交互。实验结果显示基本功能可正常执行,但在连续操作时存在执行失败的情况,需进一步优化。
48 4
|
2月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
65 4
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
97 4
|
2月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
60 4
|
3月前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
59 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
7月前
|
存储 算法 数据挖掘
数据结构实验||约瑟夫环
数据结构实验||约瑟夫环
|
3月前
|
算法
计科一二班算法数据结构实验9答案
计科一二班算法数据结构实验9答案
22 0