首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

测试两棵树是否相等并在Haskell中对树进行二进制搜索

在Haskell中,可以使用递归的方式来测试两棵树是否相等,并对树进行二进制搜索。

首先,我们需要定义一个树的数据结构。在Haskell中,可以使用代数数据类型来表示树:

代码语言:haskell
复制
data Tree a = Empty | Node a (Tree a) (Tree a)

这个数据类型定义了一个树,它可以是空的(Empty),或者是一个节点(Node),节点包含一个值和两个子树。

接下来,我们可以实现一个函数来测试两棵树是否相等:

代码语言:haskell
复制
isEqual :: Eq a => Tree a -> Tree a -> Bool
isEqual Empty Empty = True
isEqual (Node x left1 right1) (Node y left2 right2) =
  x == y && isEqual left1 left2 && isEqual right1 right2
isEqual _ _ = False

这个函数使用模式匹配来处理不同的情况。当两棵树都为空时,它们是相等的。当两棵树都是节点时,它们相等当且仅当它们的值相等,并且它们的左子树和右子树也相等。其他情况下,两棵树不相等。

接下来,我们可以实现一个函数来对树进行二进制搜索:

代码语言:haskell
复制
binarySearch :: Ord a => Tree a -> a -> Bool
binarySearch Empty _ = False
binarySearch (Node x left right) value
  | value == x = True
  | value < x = binarySearch left value
  | otherwise = binarySearch right value

这个函数也使用模式匹配来处理不同的情况。当树为空时,搜索失败。当树是一个节点时,如果要搜索的值等于节点的值,则搜索成功。如果要搜索的值小于节点的值,则在左子树中继续搜索。如果要搜索的值大于节点的值,则在右子树中继续搜索。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

相同的(java)

二、题目描述: 题目:        给你两棵二叉的根节点  ​​​p​​​ 和  ​​q​​​ ,编写一个函数来检验这两棵树是否相同。        ...p 的左子树和 q 的左子树比较。 p 的右子树和 q 的右子树比较。        这还不简单么。最暴力的解法就是递归。优化思路就上升到了​​深度优先​​或者广度优先搜索法。...其中 m 和 n 分别是两个二叉的节点数。两个二叉同时进行深度优先搜索,只有当两个二叉的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉的节点数。...两个二叉同时进行深度优先搜索,只有当两个二叉的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉的节点数。 空间复杂度:O(min(m,n))。...都是是运用递归思想,连枚举方式都是一样的,先枚举排除特殊性,然后再递归对比左右子数是否相等

28520

【数据结构】二叉专题

这道题有两种思路,一种是最简单的也是最常见的思路,遍历,就是把每个节点遍历一遍,看是否相等(代码过于简单就不写了),还有一种思路就是递归,通过递归,判断孩子与父亲是否相等,若相等进行下次递归,直到节点为空...,就代表是单值二叉,我们写下递归方式的代码 代码如下 2.检查两棵树是否相同 这道题我们可以让两颗子树分别遍历,直到双方节点同时都为空,就相等若是一方节点先为空则两棵树相等,若遍历的同时值不相等,...那两棵树也不相等,代码如下 3.对称二叉 这个对称二叉就判断左子树与右子树是否相等就行了,也就是说把根节点的左右子树放到上面那道题函数里判断就行了 /** * Definition for a...,所以传参的时候注意下 4.二叉的前序遍历 前序遍历我们上篇博客说过,但是这个前序遍历将所有根节点的数据,存储到数组,以数组的形式返回,我们先开辟一个动态数组的空间, 将数组首地址与首下表,传入函数...5.另一棵的子树 相当于直接通过前序遍历把所有子树找到,然后依次导入我们上边说的判断两棵树是否相等的函数里就行了 ,前提俩子树数据相等 代码如下 结束语 典型的二叉有关习题总结完了,二叉主要是遍历

5310
  • 【算法】四叉并集

    请你返回一个表示 n * n 二进制矩阵的四叉,它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。...由四叉所表示的二进制矩阵也已经给出。 如果我们这两个矩阵进行按位逻辑或运算,则可以得到下面的二进制矩阵,由一个作为结果的四叉表示。...然后求,两棵树各自形成的小格子做逻辑或运算,最终将结果保存到同样的四叉并返回。 这个逻辑或运算是当前两棵树相同位置的值的或运算。 题目讲解完毕,那就是怎么来计算了。...即当前的两棵树所访问到的当前节点有一个是叶子节点时,终止分的操作,通过计算 quadTree1|quadTree2操作来进行计算并返回值 合:通过两棵树的四个子节点计算结果来计算当前节点的值,即是当前节点的最后结果...分的操作:将两棵树的四个节点进行拆分,并将最终结果分别放到quadTree1的四个子节点上。

    45410

    纯函数式堆(纯函数式优先级队列)part two ----斜二项堆

    上图解释rank为r + 1的斜二项的3种情况: ? 从上图可以看出当r=0时,A型和B型斜链接是相等的。...而对于合并操作,首先两个要合并的堆做一些处理, 就是如果堆rank最小的存在两棵,则将这两棵树做个简单链接,然后才进行两个堆的合并,接下来的 合并的过程和二项堆的就一样了,如果找到两个rank相同的...,就将这两棵树做一个简单链接 (在合并过程中都是用简单链接),然后再将结果合并到由剩下的合并而成的堆时间复杂度也是O(log n)。      ...在插入一个新的元素时,首先新建一棵rank为0的,然后我们察看堆的rank最小两棵斜二项, 如果这两棵树的rank值相同,则将这两棵树和新建的做一个斜链接(是A型或B型链接看具体的情况), 得到的...如果rank最小的两棵树的rank值不相同,则我们只需把新建的节点加入堆即可,无需其他操作,因为 这时堆中最多可能存在一棵rank为0的

    79950

    【Leetcode -872.叶子相似的 -993.二叉的堂兄弟节点】

    [1, 200] 范围内 给定的两棵树上的值在 [0, 200] 范围内 思路:创建两个数组 a1,a2 分别存放两棵树的叶子节点,最后依次比较两个数组的值是否相等相等返回 true,否则返回 false...= Size2) return false; //遍历两个数组,比较对应的叶子节点的值是否相等,不相等就返回false for (int i = 0;...-993.二叉的堂兄弟节点 题目:在二叉,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k + 1 处。...如果二叉的两个节点深度相同,但 父节点不同 ,则它们是一堂兄弟节点。 我们给出了具有唯一值的二叉的根节点 root ,以及两个不同节点的值 x 和 y 。...//三个参数分别为根节点,深度,当前节点的父节点(假设第一个节点的父节点为NULL) dfs(root, 0, NULL); //最后判断 x 和 y 节点的深度是否相等

    9810

    Leetcode【700、872、897、965、1022】

    Search in a Binary Search Tree 解题思路: 这道题是给一棵二叉搜索(BST),查找给定的结点。结点不存在返回 NULL。 利用 BST 的特点,进行二分查找即可。...Leaf-Similar Trees 解题思路: 这道题是给两棵树,判断它们的叶子序列(从左到右)是否相同。 将两棵树的叶子序列保存在 list ,判断二者是否相同即可。...Univalued Binary Tree 解题思路: 这道题是给一棵二叉,判断其是否是单值二叉(所有结点值都相同)。...方法1(回溯法): 第一种容易想到的方法就是 DFS 回溯法,进行深度优先搜索,将每条路径 path 保存在 paths 列表,每次找到一条路径的出口是遇到叶子结点。...最后, paths 进行遍历,将每条路径 path 二进制转化为十进制数进行累加(如 int("0101", 2) = 5)。这样做的空间复杂度为 O(n)。

    50210

    刚学完二叉,来试试这些oj题练练手吧!

    c语言实现:单值二叉,相同的,对称二叉 金句分享: ✨总不能一生碌碌无为,还安慰自己平凡可贵吧.✨ 前言 二叉 主要就是玩递归,相信大家学完 二叉 以后,递归有了更加深层的理解...不相等返回false 判断根节点的值与右子树的值是否相等. 不相等返回false 返回递归遍历这颗的逻辑值....=root->left->val) { return false; } //判断根节点的值与右子树的值是否相等....声明: 题目来源于–力扣 题目链接: 传送门 题目介绍: 给你两棵 二叉 的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。...例如: 示例2,第一颗的左子树是值为2的结点,但是第二棵的左子树是NULL. 两棵树都为NULL,返回true 判断两颗的结点值是否相等.

    14620

    【数据结构】翻转、平衡、对称二叉,最大深度、判断两棵树是否相等、另一棵的子树

    检查两棵树是否相同 100....,则这两棵树不一样 若两个跟节点的值相同,则左右两棵子树进行递归判断 代码解析 /** * 时间复杂度为:O(min(m,n)) * @param p m个节点 * @param...另一棵的子树 - 力扣(LeetCode) 思路解透 注意: 当两棵树相同时,也返回 true 首先判断两棵树是否相同,若相同,返回 true(需要调用上面一题的方法) 若不相同,判断是否是左子树的子树...递归左右子节点的左右子节点进行交换 返回 root 代码解析 /** * 翻转二叉 * @param root * @return */ public TreeNode...若要让时间复杂度为O(n),则需要在判断的过程,只要发现左右俩高度相差大于 1,就直接 return -1,不再进行后续判断了 /** * 获取最大深度 * @param root

    9310

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

    给定一个插入序列就可以唯一确定一棵二叉搜索。然而,一棵给定的二叉搜索却可以由多种不同的插入序列得到。...例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索。...输出格式: 每一组需要检查的序列,如果其生成的二叉搜索跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。...2、使用迭代的方式构建树,每输入一个新结点后,4种情况的判断(见代码) 3、比较两是否相等,通过比较两中值(vector下标)相同的两个的结点的左右孩子是否相同,每一对应结点都相同则两棵树相同...下一次输入数字也从根结点开始比较 break; } } } } } //比较两棵二叉搜索是否相同的函数

    57510

    【初阶数据结构】——二叉OJ练习

    遍历对比 首先第一种思路,就非常简单粗暴,我们可以记录一下根结点的值,然后,遍历这棵二叉,去拿每个结点的值与根结点做对比,如果都相等,那就证明它是一棵单值二叉,返回true; 一旦有一个不相等,...代码实现 写代码的时候呢,我们也有两种方式: 第一种就是按照上面的思想写出相等的情况,进行判断 bool isUnivalTree(struct TreeNode* root){ if(root...我们可以遍历第一棵,将第一棵每一个结点对应的子树都与第二棵进行比较,如果有一个相同的,那就说明第二棵是第一棵的子树。...我们拿到的是一棵二叉的根,那我们是不是只需判断它的左右子树是否对称就行了啊。 所以呢,我们再搞一个子函数出来,专门用来判断两棵树是否对称。...那接下来就来实现判断两棵树是否对称的子函数_isSymmetric就行了: 首先如果两棵树都为空,那这棵二叉就只有一个根结点嘛,那也算对称的: 如果其中有一个不为空,另一个为空,那肯定就不对称了

    12110

    【初阶数据结构篇】二叉算法题

    给你两棵二叉的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。...(root不为空) 二叉是否对称,即左右子树是否对称 把左右子树当做单独的两棵树来比较 在上面一道相同的,我们是通过同时递归两棵树的左子树判断是否相等右子树同理 而本题则是对称,即判断一棵的左子树和右子树...(以及右子树和左子树)是否相等 所以我们同时递归一棵的左子树和另一棵的右子树(以及前者的右子树和后者左子树)即可 将上面代码略微修改即可 /** * Definition for a binary...检验 root 是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。...subRoot是否相等 判断相等还是使用上面的isSameTree方法 /** * Definition for a binary tree node

    10810

    C语言每日一题(51)相同的

    力扣网100 相同的 题目描述 给你两棵二叉的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个在结构上相同,并且节点具有相同的值,则认为它们是相同的。...输出:true 示例 2: 输入:p = [1,2], q = [1,null,2] 输出:false 示例 3: 输入:p = [1,2,1], q = [1,1,2] 输出:false 提示: 两棵树上的节点数目都在范围...[0, 100] 内 -104 <= Node.val <= 104 涉及知识点:二叉、递归 思路分析 还是基于递归的思想,但我们需要考虑一些特殊情况,递归过程,如果碰到两个结点为空的情况,说明此时已经递归到两棵树的叶子结点了...,而中途没有进行返回,说明两颗相同。...当两棵树有一个结点不相等的话,此时就要返回false了,除此之外,如果存在其中一个结点为空而另外一个结点不为空,也是要返回false的。

    9510

    ​LeetCode刷题实战572:另一棵的子树

    给你两棵二叉 root 和 subRoot 。检验 root 是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。...示例 解题 这道题就是在 root 的每个子节点上,判断由该子节点构成的子树是否和 subRoot 这颗相等。...判断两颗相等需要同时满足三个条件:当前两颗的根节点值相等;两颗的左子树相等两棵树的右子树相等。...而判断 一棵 是否为 另一颗 的子树只需满足以下条件的一个:当前两棵树相等;或 一棵 是 另一颗 的左子树;或 一棵 是 另一棵 的右子树。此题采用递归法求解。...上期推文: LeetCode1-560题汇总,希望你有点帮助!

    19910

    相同的

    相同的 2. 描述 给定两个二叉,编写一个函数来检验它们是否相同。 如果两个在结构上相同,并且节点具有相同的值,则认为它们是相同的。...思路 利用二叉刷题递归遍历框架,先根节点进行操作,然后再递归左右子节点即可。...当两棵树的当前节点都为 null 时返回 true 当其中一个为 null 另一个不为 null 时返回 false 当两个都不为空但是值不相等时,返回 false 以上三步完成对根节点的操作...,接下来左右子节点进行递归即可 // 递归访问 void traverse(TreeNode root){ // 前序遍历,先操作根节点 traverse(root.left);...// 序遍历,操作左子节点 traverse(root.right); // 后序遍历,操作右子节点 } 4.

    11110

    相同的

    相同的[1] 2. 描述 给定两个二叉,编写一个函数来检验它们是否相同。 如果两个在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: ? 示例 2: ?...思路 利用二叉刷题递归遍历框架,先根节点进行操作,然后再递归左右子节点即可。...当两棵树的当前节点都为 null 时返回 true 当其中一个为 null 另一个不为 null 时返回 false 当两个都不为空但是值不相等时,返回 false 以上三步完成对根节点的操作,接下来左右子节点进行递归即可...// 递归访问 void traverse(TreeNode root){ // 前序遍历,先操作根节点 traverse(root.left); // 序遍历,操作左子节点...// 两者均为 null,说明相等 if (p == null && q == null) { return true; } // 其中一个为 null,说明不相等

    27520

    JDK1.8HashMap源码解析

    不同的元素取模之后发生碰撞,比如3016取模也等于14,这样也需要放入14的位置,于是就会在这个桶形成链表。...查看对应位置是否有元素 如果没有,直接插入;如果有,进行hash碰撞的处理 hash碰撞三种情况,一是碰撞的元素与要插入的元素hash值和key都相等,直接进行value的更新;二是结点类型是结点直接...转移的过程 在转移的过程中会进行结点类型的判断,如果是结点,那么会进行树节点的修剪操作(修剪操作主要就是将一颗分成两棵树分别挂到table[j]和table[j+oldCap],如果树结点小于6,则转换为链表...但hashmap实现并没有这么做,我们上边说到将分为两棵树,将链表分为两个链表,这两者分类方法都是一样的,其实就是结点进行了一个判断:如果这个结点hash&oldCap==0为真那么他位置不变,仍然住到...用二进制表示更能够看清楚这个过程,大家可以用下边的表进行一下位与操作: ? 但如果table还没有初始化,就会进行初始化。

    33320

    Python 刷题笔记:深度优先搜索专题

    沿着的深度遍历的节点,尽可能深的搜索的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。...如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。...但倘若采用深度优先搜索,与比较两棵树是否相同类似,我们要设计下如何复用设计的函数来通过子节点来继续比较是否对称。 本题中我们只输入一个根节点、一棵完整的,但检查其是否对称,则要根据其子树是否对称。...在检查子树是否对称的过程,子树的根节点位置是要相等的,再下层的子树又要继续与对应位置上的子树对称,这样我们便可以通过检测两棵子树是否对称的函数实现递归。...结论 明明昨天结束了二叉题型的,结果今天由于算法的特性三道题目又都是二叉的。在学习和理解这算法的过程深度优先搜索可能只是概念上增强,反倒递归的应用更熟练了。

    2.5K10

    不可变的状态

    可变与状态 在过程式的编程,例如使用 C 语言,我们的工作是不断地以副作用的形式状态进行修改,然后产生结果。...同时,这个方式也对调试带来了困难,如果一个函数依赖了一个外部的可变状态,一旦需要测试这样的函数的正确性,就需要先构建状态,才能进行测试。...但如果我们的需求就是要给两棵树打上连续的标签,那我们应该如何用这个版本的 labelTree 来实现呢?...但是,共享可变变量的实现还有一个灵活之处,就是它可以很方便地获取和修改状态,例如,在给多棵打连续的标签的过程,我们可能需要在两棵树之间隔开一个标签,也就是说我们想在给一棵打上标签后先令标签 +...在工程实践,除非必要,否则尽量使用不可变,这样可以使得程序更加可靠,也更利于测试与调试。

    98520

    Algorithms_二叉&二分搜索初探

    } 特征 和链表一样,是动态数据结构 每个节点最多只能分出来两棵树 (同样类比多叉) 二叉具有唯一的根节点 ?...二叉不一定是“满”的 ---- 二分搜索 Binary Search Tree 特征 二分搜索是二叉,二叉的特征全部适用于二分搜索 二分搜索的每个节点的值 大于其左子树的所有节点的值...其实是为了特定的场景,我们使用二分搜索查询数据的话,这两个数可以比较的话,那么就可以明确的知道这个数据在左边还是在右边了,查询效率高。 所以什么样的数据存到二分搜索才能搜索呢?...但代码量还是有点长 我们Root节点做了特殊的非空判断处理,逻辑上不统一 每次插入都有判断节点必须为null的判断 e.compareTo(node.e)进行了两次的操作才能插入 终止条件臃肿 空本身就是一颗二叉...return node; } ---- 查找 数据 /** * * * @Title: contains 供外部调用 * * @Description: 判断元素e是否存二分搜索

    34410
    领券