在 Haskell Breadth-First 中构建二叉树（不是 BST）

Question

我最近开始使用 Haskell，它可能会持续短一段时间。只是被要求使用它来更好地理解 class 我正在大学学习的函数式编程。

现在我在尝试做的事情上遇到了一个小问题。我想构建它 breadth-first 但我认为我的条件搞砸了或者我的条件也有问题。

所以基本上如果我给它 [“A1-Gate”, “North-Region”, “South-Region”, “Convention Center”, “Rectorate”, “Academic Building1”, “Academic Building2”]和[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 应该是根，但它最终变成了一个 child，没有 children 如此混乱的条件。

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

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)

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

Answer 1

更新：下面的解决方案是 big-O 最优的，并且（我认为）很容易理解，所以我把它留在这里以防有人感兴趣。然而， is much more beautiful and, especially when optimized a bit，可以预期在实践中表现更好。更值得学习！

我现在要忽略假边缘标签，只关注正在发生的事情的核心。

算法设计中的一个常见模式是，有时更容易解决更一般的问题。因此，我不会尝试构建 tree，而是研究如何使用给定的 forest（树列表）树的数量。我将使节点标签具有多态性，以避免不得不考虑它们的外观；您当然可以使用与原始树类型相同的构建技术。

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

-- Built a tree from a breadth-first list
bft :: [a] -> Tree a
bft xs = case dff 1 xs of
  [] -> Empty
  [t] -> t
  _ -> error "something went wrong"

-- Build a forest of nonempty trees.
-- The given number indicates the (maximum)
-- number of trees to build.
bff :: Int -> [a] -> [Tree a]
bff _ [] = []
bff n xs = case splitAt n xs of
  (front, rear) -> combine front (bff (2 * n) rear)
  where
    combine :: [a] -> [Tree a] -> [Tree a]
    -- you write this

这是一个完整的、工业级的、最懒惰的实现。这是我能想出的最有效的版本，它尽可能地懒惰。一个轻微的变体不那么懒惰，但仍然适用于完全定义的无限输入；我还没有尝试测试哪个在实践中会更快。

bft' :: [a] -> Tree a
bft' xs = case bff 1 xs of
  [] -> Empty
  [t] -> t
  _ -> error "whoops"

bff' :: Int -> [a] -> [Tree a]
bff' !_ [] = []
bff' n xs = combine n xs (bff (2 * n) (drop n xs))
  where
    -- The "take" portion of the splitAt in the original
    -- bff is integrated into this version of combine. That
    -- lets us avoid allocating an intermediate list we don't
    -- really need.
    combine :: Int -> [a] -> [Tree a] -> [Tree a]
    combine 0 !_ ~[] = [] -- These two lazy patterns are just documentation
    combine _k [] ~[] = []
    combine k (y : ys) ts = Node y l r : combine (k - 1) ys dropped
      where
        (l, ~(r, dropped)) = case ts of  -- This lazy pattern matters.
          [] -> (Empty, (Empty, []))
          t1 : ts' -> (t1, case ts' of
            [] -> (Empty, [])
            t2 : ts'' -> (t2, ts''))

对于 less-lazy 变体，将 (!l, ~(!r, dropped)) 替换为 (!l, !r, dropped) 并相应地调整 RHS。

对于真正的工业强度，应使用严格包含其元素的列表来表示森林：

data SL a = Cons !a (SL a) | Nil

并且上面 (l, ~(r, dropped)) 中的对都应该使用类似

的类型来表示

data LSP a b = LSP !a b

这应该可以避免一些（相当便宜的）运行-时间检查。更重要的是，它可以更轻松地查看事物的位置和未被强制执行的位置。

Answer 2

您选择的方法似乎是反向构建树：从下到上，从右到左；从列表的最后一个元素开始。这使您的 buildBPT 函数看起来不错，但要求您的 insertElement 过于复杂。要以这种方式以广度优先方式构建二叉树，在前三步之后的每一步都需要一些困难的枢轴。

向树中添加 8 个节点需要执行以下步骤（查看节点是如何从后到前插入的）：

   .              4                                                                                                                                                                                          
                6   6                                                                                                                                                                                        
   8           7 8 . .                                                                                                                                                                                       
  . .                                                                                                                                                                                                           
                  3                                                                                                                                                                                          
   7            4   5                                                                                                                                                                                        
  8 .          6 7 8 .                                                                                                                                                                                       

   6              2                                                                                                                                                                                          
  7 8           3   4                                                                                                                                                                                        
               5 6 7 8                                                                                                                                                                                       
   5                                                                                                                                                                                                         
 6   7            1                                                                                                                                                                                      
8 . . .       2       3                                                                                                                                                                                  
            4   5   6   7                                                                                                                                                                                
           8 . . . . . . .

相反，如果您从左到右、从上到下插入节点，您最终会得到一个更简单的解决方案，不需要旋转，而是需要一些树结构自省。查看插入顺序；在任何时候，现有值都保持在原来的位置：

   .              1                                                                                                                                                                                               
                2   3                                                                                                                                                                                             
   1           4 5 . .                                                                                                                                                                                            
  . .                                                                                                                                                                                                             
                  1                                                                                                                                                                                               
   1            2   3                                                                                                                                                                                             
  2 .          4 5 6 .                                                                                                                                                                                            

   1              1                                                                                                                                                                                               
  2 3           2   3                                                                                                                                                                                             
               4 5 6 7                                                                                                                                                                                            
   1                                                                                                                                                                                                              
 2   3            1                                                                                                                                                                                           
4 . . .       2       3                                                                                                                                                                                       
            4   5   6   7                                                                                                                                                                                     
           8 . . . . . . .

插入步骤的渐近时间复杂度约为 O(n^2)，其中 n 是要插入的节点数，因为您是一个接一个地插入节点，然后迭代树中已经存在的节点。

当我们从左到右插入时，技巧是检查左子树是否完整：

如果是，且右子树不完整，则向右递归
如果是，且右子树也完整，则向左递归（另起一行）。
如果不是，则向左递归

这是我的（更通用的）解决方案：

data Tree a = Leaf | Node a (Tree a) (Tree a)
            deriving (Eq, Show)

main = do
    let l1 = ["A1-Gate", "North-Region", "South-Region", "Convention Center", 
              "Rectorate", "Academic Building1", "Academic Building2"]
    let l2 = [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2]
    print $ treeFromList $ zip l1 l2

mkNode :: a -> Tree a
mkNode x = Node x Leaf Leaf

insertValue :: Tree a -> a -> Tree a
insertValue Leaf y = mkNode y
insertValue (Node x left right) y
    | isComplete left && nodeCount left /= nodeCount right = Node x left (insertValue right y)
    | otherwise = Node x (insertValue left y) right
    where nodeCount Leaf = 0
          nodeCount (Node _ left right) = 1 + nodeCount left + nodeCount right
          depth Leaf = 0
          depth (Node _ left right) = 1 + max (depth left) (depth right)
          isComplete n = nodeCount n == 2 ^ (depth n) - 1

treeFromList :: (Show a) => [a] -> Tree a
treeFromList = foldl insertValue Leaf

编辑：更详细的解释：

这个想法是记住你插入节点的顺序：首先是从左到右，然后是从上到下 .我在实际功能中压缩了不同的情况，但你可以将它们扩展为三种：

左边完成了吗？如果没有，则插入到左侧。
右边和左边一样完整吗？如果不是，则插入到右侧。
两边都满了，所以我们从左边插入开始一个新的关卡。

因为函数从左到右和从上到下填充节点，所以我们总是知道（这是一个不变量）左侧必须先于右侧填充，而左侧side 永远不能比右边深一层（也不能比右边浅）。

随着第二组示例树的生长，您可以看到值是如何按照这个不变量插入的。这足以递归地描述该过程，因此它可以外推到任意大小的列表（递归是魔法）。

现在，我们如何判断一棵树是否'complete'？好吧，如果它是完美平衡的，或者如果——在视觉上——它的值形成一个三角形，它就是完整的。由于我们使用的是二叉树，因此三角形的底边（填充后）必须具有等于 2 的幂的多个值。更具体地说，它必须具有 2^(depth-1) 个值。在示例中为自己计数：

depth = 1 -> base = 1: 2^(1-1) = 1
depth = 2 -> base = 2: 2^(2-1) = 2
depth = 3 -> base = 4: 2^(3-1) = 4
depth = 4 -> base = 8: 2^(4-1) = 8

底座上方的节点总数比底座的宽度少一：2^(n-1) - 1。因此，完整树中的节点总数是基数以上的节点数加上基数的节点数，因此：

num nodes in complete tree = 2^(depth-1) - 1 + 2^(depth-1)
                           = 2 × 2^(depth-1) - 1
                           = 2^depth - 1

所以现在我们可以说，如果一棵树中恰好有 2^depth - 1 个非空节点，那么它就是完整的。

因为我们是从左到右，从上到下，当左边完成时，我们向右移动，当右边和左边一样完整时side（意思是它有相同的节点数，也就是因为不变量也是完整的），那么我们就知道整棵树是完整的，因此必须添加新的一行。

我最初在那里有三种特殊情况：当两个节点都为空时，当左节点为空时（因此右节点也为空）以及当右节点为空时（因此左节点不能为空） .这三个特殊情况被最后一个有警卫的情况所取代：

如果两边都是空的，那么countNodes left == countNodes right，所以我们再添加一行（左边）。
如果左边是空的，那么两边都是空的（见上一点）。
如果右边是空的，那么左边一定深度为1，节点数为1，表示完整，并且1 /= 0，所以我们在右边加

Answer 3

这是一个 corecursive 解决方案。

{-#  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是结果树的所有子树的广度优先枚举。树本身是顶级子树，即此列表中的第一个。我们从输入 xs 中的每个 x 创建 Nodes，当输入耗尽了我们通过使用不定数量的 Nothings 来创建 Emptys（Empty 叶子的真实长度是 length 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 的第 2 个和第 3 个参数时，两者就像 Prolog 伪代码 (*) 中的 尚未设置的变量 。但是，对于 xs 中的下一个 x，this lt 引用的节点变为 next 调用 g 的结果 .

然后轮到 rt，等等。当 xs 结束，我们点击 Nothings，g 停止从 pairs的输出一共。所以 pairs 也停止在 nodes 上前进，因此它永远不会结束，尽管它被定义为超过该点的 Empty 的无休止的流，只是为了安全起见。

(*) Prolog 的变量是显式 set-once：它们允许处于尚未分配状态。 Haskell的(x:xs)是Prolog的[X | Xs].

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

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

更新： @dfeuer came up with much simplified version of it which is much closer to the Prolog original (that one in the comment at the top of the post), that can be much clearer. Look for more efficient code and discussion and stuff in his post。使用简单的 [] 而不是 dfeuer 使用更高效的无限流类型 data 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 [] 总是 returns Empty。结果 t 是这个列表中的第一个，树的最顶层节点，即树本身。

此树节点列表由创建由 go 的递归调用以与消耗输入值列表 xs 相同的速度, 但被消耗为 input to go at twice that speed, 因为每个节点有 two 子节点.

因此还必须定义这些额外的节点，因为 Empty 离开了。我们不关心需要多少，只是简单地创建一个无限的列表来满足任何需要，尽管实际的空叶数将比 xs.

多一个

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

在 Haskell Breadth-First 中构建二叉树（不是 BST）

Building a Binary Tree (not BST) in Haskell Breadth-First

haskell

tree

binary-tree

breadth-first-search

construction