热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

判断两棵二叉搜索树是否结构相同

在解决此问题时,最初对输入格式的理解存在困惑,导致编写代码过程中出现多次错误。通过参考他人代码,最终明白输入包含两个测试案例:一个案例中有4个节点,需要进行两次结构对比;另一个案例有2个节点,只需进行一次对比。输出结果应为“是”或“否”,以表明两棵树的结构是否相同。

在写这题的时候,一开始对输入和输入并不是很理解,自己写出来后,也各种报错,后来看了别人的程序才理解 输入 是包含了两次例子,一次是4个节点,判别2次,一次是2个节点,判别1次。Yes和No可以在待判别树输入后马上输出,不用放到最后一起输入。


一开始看到这题,我的策略是比较笨的,把被判别树构造好之后,每次都去把待判别树构造一边,然后层序遍历两棵树,比较其结构。写出来之后,测试例子是正确的,但放到网页上判定,总是出现 段错误。 改了一晚上改不出来,看了别人的程序之后,用另一个方法开始写了。


另一种判定方法不需要将待判定树构造出来,只需要在被判定树的每一个节点上加一个标识位,初始为0,同时创建一个公共标识位,初始值为0;构造完被判定树后,逐一输入待判定的树的节点值。第一个值与根节点比较,相同在将被判定树的标志位写1;不同,则将公共标识位写0;之后的每一位的插入都与构造时一样,大就往右走,小则往左走,只是停下来的条件不同。构造时,是到下一处为NULL时停下;判定时,则是当遇到节点的标志位为0时就停下。然后再进行判定,相同将该节点的标志位写1,不同则将公共标识位写1.


有几点收获:1、与其花时间在改一个不好的方法上,还不如将时间花在寻找一个巧妙的方法上。2、递归的思想要逐渐熟悉起来。


下面附上对应解决程序

#include 
#include

typedef struct _node{
int data;
int flag;
struct _node *left;
struct _node *right;
}Node;



Node* creat_node();
Node* add_tree(Node *root,int number);
Node* creat_tree(int number);
void byfloor_tree(Node *root,int times);
void free_tree(Node *root);
void reset_flag(Node *root);
int check(Node *root,int tmp);


int main(int argc, char const *argv[]){

int times;
int number;
Node *root=NULL;
int i;
int j=0;
scanf("%d",×);
while(times){
scanf("%d",&number);
root=creat_tree(times);
int flag=0;
for(i=0;ibyfloor_tree(root,times);
reset_flag(root);
}
free_tree(root);
scanf("%d",×);
}
return 0;
}

void byfloor_tree(Node *root,int times){
int flag=0;
int i=0;
int tmp;
scanf("%d",&tmp);
if(tmp==root->data){
root->flag=1;
}
else{
flag=1;
}
for(i=1;iscanf("%d",&tmp);
if(check(root,tmp)){
flag=1;
}
}
if(flag){
printf("No\n");
}
else
{
printf("Yes\n");
}
}

int check(Node *root,int tmp){ //
Node *p=root;
int flag=0;
while(p->flag){
if(tmp>p->data){
p=p->right;
}
if(tmpdata){
p=p->left;
}
}
if(p->data!=tmp){
flag=1;
}else
{
p->flag=1;
}
return flag;
}

void reset_flag(Node *root){
if(root->left){
reset_flag(root->left);
}
if(root->right){
reset_flag(root->right);
}
root->flag=0;
}

void free_tree(Node *root){
if(root->left)
free_tree(root->left);
if(root->right)
free_tree(root->right);
free(root);
}

Node* creat_tree(int times){
int number;
Node *root=NULL;
int i=0;
for(i=0;iscanf("%d",&number);
if(root==NULL){
root=creat_node();
root->data=number;
}
else
{
add_tree(root,number);
}
}
return root;
}

Node* creat_node(){
Node *p=(Node*)malloc(sizeof(Node));
p->data=0;
p->flag=0;
p->left=NULL;
p->right=NULL;
return p;
}

Node* add_tree(Node *root, int number){

if(!root){
root = creat_node();
root->data=number;
}
else{
if(number > root->data)
root->right = add_tree(root->right, number);
else
root->left = add_tree(root->left, number);
}
return root;
}



楼下是题目

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

04-树4 是否同一棵二叉搜索树   (25分)

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

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (10)和L,分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列。最后L行,每行给出N个插入的元素,属于L个需要检查的序列。

简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。

输出格式:

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

输入样例:

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

输出样例:

Yes
No
No

推荐阅读
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本文深入探讨了二叉搜索树(Binary Search Tree, BST)及其操作,包括查找、插入和删除节点。同时,文章还介绍了平衡二叉树(AVL树)的概念及调整方法,并详细讨论了如何判断两个序列是否构成相同的二叉搜索树。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • Linux设备驱动程序:异步时间操作与调度机制
    本文介绍了Linux内核中的几种异步延迟操作方法,包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务,而无需阻塞当前线程,从而提高系统的响应性和效率。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
author-avatar
li永不言败ly_608
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有