在二叉树中返回最小值

我试图编写代码，如果给定一棵树，将通过树并返回该树中的最小值，如果树为空，它将返回val。我现在编译的内容不会运行。任何帮助？在二叉树中返回最小值

minValue :: Ord a => a -> BTree a -> a 
minValue val Empty = val 
minValue val (BNode v left Empty) = minimum [minValue v left] 
minValue val (BNode v Empty right) = minimum [minValue v right] 
minValue val (BNode v left right) = minimum ([minValue v left]++[minValue v right])

来源

2015-04-02 tamais2

在二叉搜索树中排列了树的元素吗？在任何情况下，您都不需要使用列表或“最小”来执行此操作。在第二和第三个方程中，它们是多余的 - 单元素列表的最小值是列表的一个元素。 – 2015-04-02 20:56:33

树是有序的，是的。 – tamais2 2015-04-02 21:00:20

另外：我只是试过你的功能，它有这个bug：'minValue 17（BNode 22 Empty Empty）== 22' – 2015-04-02 21:08:41

我假设BTree被定义为

data BTree a = Empty | BNode a (BTree a) (BTree a) deriving (Eq, Show)

虽然以供将来参考请在你的问题的数据类型定义。

的关键，这里的解决方案是一个节点的最小值是其值的最小值和每个分支的分钟：

minValue :: Ord a => a -> BTree a -> a 
minValue val Empty = val 
minValue val (BNode v left right) = 
    let leftMin = minValue val left 
     rightMin = minValue val right 
    in ???

而是担心，如果左边或右边的是Empty，只是信任递归来处理它。如果left是Empty，那么minValue val left将只是val，并且类似地right。然后，您有4个要确定最小值的范围值，val，v,leftMin和rightMin。你会怎么做？

来源

2015-04-02 21:39:10 bheklilr

在二叉树中返回最小值

回答

相关问题