Haskell 树的最左边最深节点

Question

假设我有一个二叉树结构定义为

data IntTree = Empty | Node Int IntTree IntTree

和树

Node 0 (Node 1 Empty Empty)(Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty))

如何提取最左边最深的节点（即Node 3 Empty Empty）？

Answer 1

您应该使用递归并定义一个辅助函数，该函数 return 是节点的深度，然后对于每个 innode，您是 select 最深的子节点。这样的函数看起来像：

leftmostDeep : IntTree -> IntTree
leftmostDeep = fst . go
    where go n@(Node _ Empty Empty) = (n, 0)
          go n@(Node _ Empty r) = let (nr, dr) = go r in (nr, dr+1)
          go n@(Node _ l Empty) = let (nl, dl) = go l in (nl, dl+1)
          go (Node l r) = …
              where (na, da) = go l
              where (nb, db) = go r

其中 … 留作练习。这应该确定哪个项目是最深的，并且作为决胜局，return 左子树。您还应该将该节点的深度增加一个。

Answer 2

[Node 0 (Node 1 Empty Empty)(Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty))]
[        Node 1 Empty Empty, Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty) ]
[               Empty,Empty,         Node 3 Empty Empty, Node 4 Empty Empty  ]
[                                           Empty,Empty,        Empty,Empty  ]
[                                                                            ]

建议

deepest :: IntTree -> [Int]
deepest  =  pure  >>>  iterate (>>= g)  >>>  takeWhile (not . null) 
                  >>>  reverse  >>>  drop 1  >>>  take 1
                  >>>  (>>= \ xs -> [i | Node i _ _ <- xs])
  where
  g (Node _ lt rt) = [lt, rt]
  g Empty = []

然后我们得到

> deepest $ Node 0 (Node 1 Empty Empty)
                   (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty))
[3,4]

所以剩下的就是take 1，如果你愿意的话。

Haskell 树的最左边最深节点

Haskell leftmost deepest node of tree

recursion

haskell

nested

list

nested-lists