代码之家  ›  专栏  ›  技术社区  ›  Dipesh Desai

在二叉树haskell中搜索值

  •  3
  • Dipesh Desai  · 技术社区  · 7 年前

    我刚刚开始学习Haskell,我正在尝试编写一个代码,用于在二叉树中搜索特定值,如果存在,则返回true,否则返回false 这就是我的树结构

    data Tree = Leaf Int | Node Tree Int Tree
    

    我不知道如何继续使用函数遍历树并返回值。我确实尝试过BFS和DFS,但我不确定一旦获得价值后如何返回。

    函数外观示例

    Search 5 (Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9))) 
    
    2 回复  |  直到 7 年前
        1
  •  4
  •   Haleemur Ali    7 年前

    二进制搜索可以编写如下。该类型可以更通用,因为我们只需要可以排序的项目就可以在二叉树中存储/搜索。

    我们访问每个节点,要么返回true,要么搜索其中一个子节点。

    示例节点

       5
     /   \
    3     7
    

    让我们搜索7。

    我们首先访问根。自5!=我们测试了一个子节点。自7日起>5,我们在右节点中搜索,因为7不能出现在左子节点中(左子节点上的所有值都保证小于5)

    如果我们找到一片叶子,我们只需检查它是否包含搜索词。

    search :: Ord a => a -> BinaryTree a -> Bool
    search a (Leaf b) = compare a b == EQ
    search a (Node left b right) 
      case compare a b of 
        EQ -> True
        LT -> search a left
        GT -> search a right
    
        2
  •  1
  •   Regis Kuckaertz    7 年前

    我不知道如何继续使用函数遍历树并返回值。

    从这句话中,我了解到您自己编写遍历不会有任何问题,但要理解Haskell的工作原理,您需要进行一次思维上的飞跃。

    你看,你从来没有 回来 哈斯克尔的任何事。回归基本上是 命令性陈述 Haskell是一种声明性语言,意思是 编写程序是通过陈述事实来完成的 。这种细微差别可能会让人不舒服,尤其是如果你是通过学习命令式语言(如C、Java、JavaScript等)来学习编程的。但一旦你真正理解了它,你就会发现声明式编程是多么的富有表现力和简单。

    由于其强大的数学根源,在Haskell中,事实以方程的形式陈述,即表达式中 = 符号字面上意味着左侧和右侧是相等的(而在命令式语言中,它可能意味着为变量赋值——Haskell中不存在)。

    Haleemur Ali编写的程序与您的写作方式有1:1的对应关系 search 使用数学符号:

    search(x, t) = { x == y       if t = Leaf y
                   , true         if t = Node l y r and x == y
                   , search(x, l) if t = Node l y r and x < y
                   , search(x, r) if t = Node l y r and x > y
                   }
    

    事实上,很多时候,至少作为初学者,写Haskell只是一个翻译的问题,从数学符号到Haskell符号。Haskell程序的另一种解释是作为定理的证明。你的搜索是一个定理 如果你有一棵树和一个整数,你总是可以知道整数是否在树的某个地方 “。这就是您在编写函数签名时告诉编译器的内容:

    search :: Int -> Tree -> Bool
    

    只有当你为这个定理写一个证明时,编译器才会高兴。。。你可能猜到上面的算法就是证明。

    一个有趣的观察结果是,算法几乎是由数据类型的形状决定的。假设您想对树中的所有值求和:

    sum(t) = { x                   if t = Leaf x
             , x + sum(l) + sum(r) if t = Node l x r
             }
    

    每当您想在二叉树上编写算法时,您都会编写类似于上面的内容。这是相当机械和重复的。如果以后你扩展你的计划来处理玫瑰树呢?尝试?您不想编写相同的算法并冒着出错的风险。我们可以尝试提出一个函数,该函数可以遍历树并组合其值(从现在起使用Haskell表示法):

    walk :: (Int -> b) -> (b -> b -> b) -> Tree -> b
    walk f g (Leaf x) = f x
    walk f g (Node l x r) =
      let a = walk f g l
          b = walk f g r
      in g (g (f x) a) b
    

    仅使用此函数,就可以在树上编写所有方式的遍历:

    sum t      = walk id (+) t
    search x t = walk (== x) (||) t
    

    walk 是一种反复出现的模式,它已经被抽象了。所有公开相同递归模式的数据结构都被称为 可折叠的 ,并且实现通常非常明显,您可以要求编译器为您编写它,如下所示:

    {-# LANGUAGE DeriveFoldable #-}
    
    data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving (Foldable)
    

    甚至还有 a definition of sum for any foldable data structure