有序列表转ABB函数结果与预期不符，是否存在定义或编码问题？

你期望构建的二叉搜索树结构编码为：

Unir (Unir (Unir Vacio 1 Vacio) 2 Vacio) 5 (Unir Vacio 8 Vacio)

但通过list2ABB [1,2,5,8]得到的是左偏链状树，这并非函数或编码错误，而是插入顺序与逻辑导致的结果差异，具体分析如下：

差异原因 #

你的list2ABB函数是从列表尾部开始向前插入元素，对[1,2,5,8]的执行流程为：

• 先插入8，得到Unir Vacio 8 Vacio
• 插入5：因5 < 8，插入到左子树，得到Unir (Unir Vacio 5 Vacio) 8 Vacio
• 插入2：因2 < 5 < 8，继续插入到最左子树，得到Unir (Unir (Unir Vacio 2 Vacio) 5 Vacio) 8 Vacio
• 最后插入1：同样插入到最左子树，最终生成全左偏结构。

而你期望的结构以5为根，2（带左子树1）为左子树，8为右子树，这需要优先插入根节点5，再依次插入左右子树的元素。

函数正确性说明 #

你的insertABB是标准的二叉搜索树插入逻辑，list2ABB的实现也完全符合其定义——二者本身没有错误，只是它们的行为是生成与插入顺序对应的二叉搜索树，而非你期望的平衡树结构。

实现目标结构的方法 #

方法1：调整列表插入顺序 #

将列表调整为以根节点开头的顺序，比如：

list2ABB [5,2,1,8]

执行后会生成你想要的结构：先插入5作为根，再插入2到左子树，1到2的左子树，8到5的右子树。

方法2：实现平衡树构建函数 #

针对有序列表，可通过取中间元素作为根、递归构建左右子树的方式生成平衡二叉搜索树：

list2BalancedABB :: Ord a => [a] -> ABB a
list2BalancedABB [] = Vacio
list2BalancedABB xs = let
    midIdx = length xs `div` 2
    (leftNodes, root:rightNodes) = splitAt midIdx xs
    in Unir (list2BalancedABB leftNodes) root (list2BalancedABB rightNodes)

调用list2BalancedABB [1,2,5,8]时，会自动取5作为根，左子树由[1,2]生成（根为2，左子树为1），右子树由[8]生成，正好得到你期望的结构。

内容的提问来源于stack exchange，提问作者F. Zer