haskell - Haskell：带列表的二叉搜索树

Question

我正在尝试构建一个二叉搜索树，但它没有按预期工作。例如，treeListInsert [7,12,6,4,8]给我Node 8 (Node 4 Nil (Node 6 Nil (Node 7 Nil Nil))) (Node 12 Nil Nil)，这是错误的。是不是我做错了什么？谢谢。

-- the tree structure should be
--       7
--      / \
--     6   12
--    /   /
--   4   8

-- but results
--       8
--      / \
--     4  12
--    / \
--   6   7

-- define the data structure
-- deriving Show to show Node in GHCI
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

-- | treeInsert takes any number and
--   and return a Node
treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert x Nil = Node x Nil Nil -- build a Node
treeInsert x (Node root left right)
  | x == root = Node root left right -- avoid duplicate
  | x < root = Node root (treeInsert x left) right -- insert a node on a left
  | x > root = Node root left (treeInsert x right) -- insert a node on the right

-- | treeListInsert takes a list of numbers
--   and return a tree using treeInsert function
treeListInsert :: (Ord a) => [a] -> Tree a
treeListInsert [] = Nil -- empty list return Nil
treeListInsert (x:xs) = treeInsert x (treeListInsert xs) -- iterate through the list and insert x to tree repeatedly

标签： haskellbinary-search-tree

Answer 1

您的插入功能很好，但treeListInsert相当于foldr treeInsert Nil. 基本情况是列表的结尾，而不是开头。你得到的树看起来错了（4 有 6 个作为左孩子），但那是因为你画错了，而不是因为 Haskell 给了你一个糟糕的结果。