Haskell:带有列表的二叉搜索树
Haskell: binary search tree with a list
我正在尝试构建一个二叉搜索树,但它没有按预期工作。例如,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
您的插入函数没问题,但 treeListInsert
等同于 foldr treeInsert Nil
。基本情况是列表的结尾,而不是开头。你得到的树看起来不对(4 左边有 6 child),但那是因为你画错了,而不是因为 Haskell 给了你一个糟糕的结果。
我正在尝试构建一个二叉搜索树,但它没有按预期工作。例如,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
您的插入函数没问题,但 treeListInsert
等同于 foldr treeInsert Nil
。基本情况是列表的结尾,而不是开头。你得到的树看起来不对(4 左边有 6 child),但那是因为你画错了,而不是因为 Haskell 给了你一个糟糕的结果。