将排序列表转换为二叉树

Convert a sorted list to a binary tree

提问人：F. Zer 提问时间：7/28/2023 最后编辑：F. Zer 更新时间：7/29/2023 访问量：95

问：

我已经对以下树进行了编码：

enter image description here

如

Unir （Unir （Unir Vacio 1 Vacio） 2 Vacio） 5 （Unir Vacio 8 Vacio）

使用以下代数数据类型：

data ABB a = Vacio | Unir (ABB a) a (ABB a)

但是，我定义了以下函数：

list2ABB :: Ord a => [a] -> ABB a
list2ABB [] = Vacio
list2ABB (x:xs) = insertABB x (list2ABB xs)

当我执行时：

list2ABB [1,2,5,8]

我得到不同的结果：

Unir （Unir （Unir （Unir Vacio 1 Vacio） 2 Vacio） 5 Vacio） 8 Vacio

我的定义或编码有问题吗？

编辑：

谢谢大家的回答。在回答其中一个查询时，我发布了我对以下方面的定义：insertABB

insertABB :: Ord a => a -> ABB a -> ABB a
insertABB x Vacio = Unir Vacio x Vacio
insertABB x (Unir ti y td)
    | x < y     = Unir (insertABB x ti) y td
    | x > y     = Unir ti y (insertABB x td)
    | otherwise = Unir ti y td
列出 Haskell 递归 binary-search-tree

评论

0赞 willeM_ Van Onsem 7/28/2023
两者是等价的，可能你只是执行二进制搜索并插入到叶子中，所以这意味着它以 开头，每次都将项目添加到左侧子列表中，从而创建一个非常倾斜的树。因此，树中没有平衡。insertABBVacio
3赞 chi 7/28/2023
通常，多个不同的树可以生成相同的列表。因此，从数学上讲，不可能在所有情况下都从列表中重建原始树。
0赞 Noughtmare 7/28/2023
我猜目标是创建一个平衡的二叉树。特别是从左到右填充底行的多余节点。我认为这唯一地定义了应该生成的树，并与问题中的示例树相匹配。
1赞 Noughtmare 7/28/2023
@f-zer 是你自己写的？如果是这样，你能说明你是如何定义它的吗？也许应该改变这一点以保持生成的树平衡。insertABB
1赞 willeM_ Van Onsem 7/28/2023
@F.Zer：它很有道理，但它不会平衡树，因为列表是有序的，因此每次都会将其作为最左边的元素插入，因此总是在树的左侧，产生一个类似链接列表的树，其中所有节点的右子树总是空的。

答：

1赞 willeM_ Van Onsem 7/28/2023 #1

您的函数每次都会在不平衡的情况下定位项目的插入方式。insertABB

由于列表是排序的，并且您以类似的方式插入它，因此它将从右到左插入项目。因此，它将从一棵空树开始，然后插入最右边的元素。这意味着根元素将是列表中最大的项。foldr

接下来，我们插入一个小于根元素的元素，因此它将是根树左子树的根元素。接下来又是一个较小的元素，即根的左子树的左子树。

如果该过程完成，这意味着所有节点的所有正确子树都将为空，并且数据将以类似链接列表的方式插入。

如果你想生成一个平衡树，你可以使用一个平衡树，比如一个 AVL 树 [wiki]。

由于列表已经排序，我们可以构建一个完整的树。为此，我们首先将项目定位在列表的中间，将其作为根元素，然后将子列表作为子树插入。

例如，我们可以用兔子和的方法工作：

hareTortoise :: [a] -> ([a], [a])
hareTortoise xs = go xs xs
  where
    go [] ts = ([], ts)
    go [_] ~(t : ts) = ([t], ts)
    go (_ : _ : hs) ~(t : ts) = let ~(ya, yb) = go hs ts in (t : ya, yb)

然后，我们可以使用它来构造树：

constructSorted :: [a] -> ABB a
constructSorted [] = Vacio
constructSorted [x] = Unir Vacio x Vacio
constructSorted xs = let ~(ls, ~(r:rs)) = hareTortoise xs in Unir (constructSorted ls) r (constructSorted rs)

评论

1赞 F. Zer 7/28/2023
惊人的解释。非常感谢。
0赞 F. Zer 7/28/2023
我遵循了你上一段中的最后一个建议：haskell list2ABB' :: [a] -> ABB a list2ABB' [] = Vacio list2ABB' xs = Unir (list2ABB' ys) z (list2ABB' zs) where n = length xs `div` 2 m = xs !! n (ys, z:zs) = splitAt n xs
0赞 F. Zer 7/28/2023
这对你有意义吗？我正在尝试在数据声明之后构建一个完整的树。ABB a
0赞 Chris 7/29/2023
注释对 Haskell 代码来说是一个糟糕的地方，因为它是对空格敏感的。
0赞 F. Zer 7/30/2023
谢谢你的野兔和方法。什么意思？~

上一个：在 Haskell 中加入 NonEmpty 类型

下一个：如何同时返回已处理的列表和修改的对象？