时间戳

首页 > 解决方案 > 在 Haskell 广度优先中构建二叉树（不是 BST）

haskell - 在 Haskell 广度优先中构建二叉树（不是 BST）

问题描述

我最近开始使用 Haskell，可能会持续一段时间。只是被要求使用它来更好地理解我在 Uni 上的一门课程的函数式编程。

现在我有一个小问题，我目前正在尝试做的事情。我想以广度优先构建它，但我认为我的条件搞砸了，或者我的条件也错了。

所以基本上如果我给它 [“A1-Gate”, “North-Region”, “South-Region”, “Convention Center”, “Rectorate”, “Academic Building1”, “Academic Building2”]and [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2]，我的树应该像

我试图实现的树布局

但是我的试运行结果不是我预期的哈哈。因此，Haskell 的一位特别敏锐的专家可能会帮助我发现我做错了什么。输出：

*Main> l1 = ["A1-Gate", "North-Region", "South-Region", "Convention Center", 
             "Rectorate", "Academic Building1", "Academic Building2"]
*Main> l3 = [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2]
*Main> parkingtree = createBinaryParkingTree l1 l3
*Main> parkingtree
Node "North-Region" 0.5 
   (Node "A1-Gate" 0.0 EmptyTree EmptyTree) 
   (Node "Convention Center" 0.3 
     (Node "South-Region" 0.7 EmptyTree EmptyTree) 
     (Node "Academic Building2" 1.4 
       (Node "Academic Building1" 1.2 EmptyTree EmptyTree) 
       (Node "Rectorate" 0.6 EmptyTree EmptyTree)))

A-1 Gate 应该是根，但它最终成为一个没有孩子的孩子，所以条件非常混乱。

如果我能得到一些指导，那会有所帮助。以下是我到目前为止所写的内容：

data Tree = EmptyTree | Node [Char] Float Tree Tree deriving (Show,Eq,Ord)

insertElement location cost EmptyTree = 
   Node location cost EmptyTree EmptyTree
insertElement newlocation newcost (Node location cost left right) = 
   if (left == EmptyTree && right == EmptyTree)
   then Node location cost (insertElement newlocation newcost EmptyTree) 
                           right
   else if (left == EmptyTree && right /= EmptyTree)
        then Node location cost (insertElement newlocation newcost EmptyTree) 
                                right
        else if (left /= EmptyTree && right == EmptyTree)
             then Node location cost left 
                                (insertElement newlocation newcost EmptyTree)
             else Node newlocation newcost EmptyTree
                                (Node location cost left right)

buildBPT [] = EmptyTree
--buildBPT (xs:[]) = insertElement (fst xs) (snd xs) (buildBPT [])
buildBPT (x:xs) = insertElement (fst x) (snd x) (buildBPT xs)

createBinaryParkingTree a b = buildBPT (zip a b)

感谢您提供的任何指导。是的，我已经查看了一些类似的问题，但我确实认为我的问题有所不同，但如果您认为某个帖子有一个明确的答案，这将有助于我愿意去看看它。

标签： haskelltreebinary-treebreadth-first-searchconstruction

解决方案

这是一个核心递归解决方案。

{-#  bft(Xs,T) :- bft( Xs, [T|Q], Q).    % if you don't read Prolog, see (*) 

     bft(     [],    Nodes ,      [])  :-  maplist( =(empty), Nodes).
     bft( [X|Xs], [N|Nodes], [L,R|Q])  :-  N = node(X,L,R), 
        bft( Xs,     Nodes,       Q).
#-}

data Tree a = Empty | Node a (Tree a) (Tree a) deriving Show

bft :: [a] -> Tree a
bft xs = head nodes    -- Breadth First Tree
  where
  nodes = zipWith g (map Just xs ++ repeat Nothing)  -- values and
                                                     --   Empty leaves...
                    (pairs $ tail nodes)             -- branches...
  g (Just x) (lt,rt)  =  Node x lt rt
  g Nothing  _        =  Empty
  pairs ~(a: ~(b:c))  =  (a,b) : pairs c
{-
  nodes!!0 = g (Just (xs!!0)) (nodes!!1, nodes!!2)            .
  nodes!!1 = g (Just (xs!!1)) (nodes!!3, nodes!!4)        .       .
  nodes!!2 = g (Just (xs!!2)) (nodes!!5, nodes!!6)      .   .   .   .
  ................                                    .................
-}

nodes是结果树的所有子树的广度优先枚举。树本身是顶部子树，即此列表中的第一个子树。我们从input 中的Node每个创建 s ，当输入用尽时，我们通过使用不定数量的s 来创建 s （叶子的真实长度是，但我们不需要关心）。xxsEmptyNothingEmptylength xs + 1

而且我们根本不需要计算。

测试：

> bft [1..4]
Node 1 (Node 2 (Node 4 Empty Empty) Empty) (Node 3 Empty Empty)

> bft [1..10]
Node 1 
   (Node 2 
      (Node 4 
         (Node 8  Empty Empty) 
         (Node 9  Empty Empty)) 
      (Node 5 
         (Node 10 Empty Empty) 
         Empty)) 
   (Node 3 
      (Node 6 Empty Empty) 
      (Node 7 Empty Empty))

它是如何工作的：关键是g' 的懒惰，它不会强制lt' 和rt' 的值，而元组结构很容易由 - 本身非常懒 - 提供服务pairs。因此，当作为g. 但是，对于下一个xin ，由thisxs引用的节点成为下一个调用's result。 ltg

然后rt轮到 ，等等。当xs结束时，我们点击Nothings，完全停止从 ' 的输出g中提取值。pairs所以也pairs停止前进nodes，因此永远不会完成，尽管它被定义为超过那个点的无休止的Emptys 流，只是为了安全起见。

(*) Prolog 的变量被明确 设置一次：它们被允许处于尚未分配的状态。Haskell(x:xs)是 Prolog 的[X | Xs].

伪代码：维护一个队列；入队“未分配的指针”；对于每个xin xs: { 将当前队列头中的指针设置到Node(x, lt, rt)where lt，rt是未分配的指针；入队lt；入队rt；弹出队列}; 将队列中剩余的所有指针设置为Empty；在队列的原始头部找到结果树，即原始第一个“未分配指针”（或“空框”而不是“未分配指针”是另一种选择）。

这个 Prolog 的“队列”当然是完全持久的：“弹出”不会改变任何数据结构，也不会改变对队列前头的任何未完成的引用——它只是将当前指针推进到队列中。所以在所有这些排队之后剩下的是构建树节点的bfs 枚举，树本身是它的头元素 - 树是它的顶部节点，两个子节点完全实例化到底部叶子枚举完成的时间。

更新： @dfeuer提出了它的简化版本，它更接近 Prolog 原版（帖子顶部评论中的那个），可以更 清晰。在他的帖子中寻找更有效的代码和讨论等内容。使用 simple[]而不是 dfeuerdata IS a = a :+ IS a对子树队列使用更有效的无限流类型，它变成

bftree :: [a] -> Tree a
bftree xs = t
    where
    t : q  =  go xs q
    go []       _              =  repeat Empty
    go (x:ys) ~(l : ~(r : q))  =  Node x l r : go ys q

      ---READ-- ----READ----      ---WRITE---

{-
   xs    =  [ x  x2  x3  x4  x5  x6  x7  x8   … ]
   (t:q) =  [ t  l   r   ll  lr  rl  rr  llr  …  Empty Empty  … … ]
-}

为了比较，树的广度优先枚举的相反操作是

bflist :: Tree a -> [a]
bflist t = [x | Node x _ _ <- q]
    where
    q  =  t : go 1 q
    go 0  _                =          []
    go i (Empty      : q)  =          go (i-1) q
    go i (Node _ l r : q)  =  l : r : go (i+1) q

         -----READ------     --WRITE--

工作原理bftree：t : q是树的子树的广度优先顺序列表。go (x:ys)使用的特定调用l和r 在它们之前由随后的调用定义go，或者与另一个x更进一步的调用，ys或者go []总是返回Empty。结果t是这个列表中的第一个，树的最顶层节点，即树本身。

这个树节点列表是通过递归调用创建go的，其速度与消耗输入值列表的速度相同，但作为输入xs消耗的速度是该速度的两倍，因为每个节点都有两个子节点。go

因此，这些额外的节点也必须定义为Empty叶子。我们不在乎需要多少，只是创建一个无限的列表来满足任何需求，尽管实际的空叶子数量会比原来的多一个xs。

这实际上与几十年来计算机科学中用于数组支持树的方案相同，其中树节点以广度优先顺序放置在线性数组中。奇怪的是，在这样的设置中，两种转换都是无操作的——只有我们对相同数据的解释是什么发生了变化，我们对它的处理，我们如何与之交互/使用它。

推荐阅读