在二叉树中查找值为x的叶子

Question

我有这个问题要做:

"定义一个函数findpath:: BTree a -> a -> Path(其中Btreea在前面的问题中定义),给定二叉树t和值x,返回从根t到叶子的路径(x如果有的话),Nothing否则返回值.运行时间您的程序应该是树中节点数的线性."

到目前为止,我有:

data Maybe a = Nothing | Just a
data BTree a = Leaf a | Fork (BTree a) (BTree a)
type Path = Maybe [Dir]
data Dir = Left | Right

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y) x = if y==x then ??? else Nothing
findpath (Fork l r) x = nodepath (findpath l x) (findpath r x) where
   nodepath :: Path -> Path -> Path
   nodepath Nothing Nothing = Nothing
   nodepath Nothing pathr = Just [R]
   nodepath pathl Nothing = Just [L]

我仍然无法工作如何在(Leaf y)案例中建立最终答案

Answer 1

你的语言,关于你认为该计划应该做什么,向我建议你需要帮助来摆脱命令式思维的陷阱.让我尝试提供一些帮助的基础上,思考什么事情是,没有什么事情做.

因为findpath (Leaf y) x,你正朝着正确的方向前进.你只需要提供if一个小写的i,想想正确的东西Path的Leaf必须.

现在,让我们考虑另一种可能性.你知道的不仅仅是它t.你知道你真的想弄明白什么

findpath (Node l r) x

是(=确实如此),因为这是另一种可能性BTree.想一想通过询问"这是BTree一个(Leaf y)还是一个(Node l r)？"来解决问题.作为程序设计的一个概念步骤.现在,为了弄清楚上面的左边是什么,你有权获得一些递归计算的信息,即什么

findpath l x

和

findpath r x

是.如果你知道Path了双方的信息l和r,你能说什么了Path整个Node l r是什么？让我通过在Haskell中编写它来重新解释这个问题:

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y)   x = if y==x then ??? else Nothing
findpath (Node l r) x = nodepath (findpath l x) (findpath r x) where
  nodepath :: Path -> Path -> Path
  nodepath ???

I have expressed my question by introducing a helper function nodepath which takes as arguments the recursively computed information. Now you can try to implement nodepath by pattern matching on those two paths for the left and right subtrees, respectively. If you know whether they are (Just p) or Nothing, then you should be able to say what the path for the whole node must be.

Lesson one, the useful thoughts are of the form: "If this is like such-and-such, then that must be so-and-so.". Being, not doing.

Lesson two, the basic method of programming over a datatype is: split into constructor cases (Leaf versus Node, Just versus Nothing); collect useful information from any substructures by recursive calls; say what the value for the whole structure must be.

如果您遵循我的建议并弄清楚nodepath应该是什么,您可能会发现它很简单,不值得单独命名.在这种情况下,只需nodepath用其含义替换调用并删除where-clause.但最好先介绍一下nodepath,因为它表达了解决问题的有用概念步骤.