haskell - 在 Haskell 中，如何生成完美平衡的二叉搜索树？

Question

该函数应该接受一个列表 xs 并构造一个平衡的二叉搜索树，该树由与 xs 完全相同的元素集组成。

结果应该是这样的:
(如果列表是 [1,2,3,4,5,6,7,8])

节点(节点(节点(节点空1空)2空)4(节点空4空))5(节点(节点空6空)7(节点空8空))

也就是说树应该是这样的:

                5
               / \
              3   7
             / \ / \
            2  4 6  8
           /
          1

而不是这个:

                5
               / \
              4   6
             /     \
            3       7
           /         \
          2           8
         /
        1

谁能告诉我如何做到这一点？我发现我可以做不完全平衡的第二棵树，但不知道如何做第一棵树。

我感谢任何帮助!
先感谢您!

Answer 1

对输入列表进行排序。现在创建一棵树，其根节点是列表的中间元素，其左右子树是通过将这个过程分别应用于中心左侧和右侧的子列表而生成的子树。

在 haskell :

buildBalanced []   = Empty
buildBalanced elts = Node (buildBalanced $ take half elts) 
                          (elts !! half) 
                          (buildBalanced $ drop (half+1) elts)
    where half = length elts `quot` 2

main = putStrLn $ show $ buildBalanced [1,2,3,4,5,6,7,8]
-- prints Node (Node (Node (Node Empty 1 Empty) 2 Empty) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node Empty 8 Empty))