Haskell 在描述这些数据结构的时候,非常符合直觉,符合到一下子难以适应。
data BSTree a = Nil|Node{
content::a,
left::BSTree a,
right::BSTree a
} deriving Show
insertData :: Ord a => a -> BSTree a -> BSTree a
insertData a Nil = Node a Nil Nil
insertData a (Node c l r) = if a >= c then Node c l (insertData a r) else Node c (insertData a l) r
toTree :: Ord a => [a] -> BSTree a -> BSTree a
toTree [] _ = Nil
toTree arr tree = foldl (\tree a ->insertData a tree) tree arr
delNode :: Ord a => a -> BSTree a -> BSTree a
delNode a Nil = Nil
delNode a (Node c l r)
| a < c = Node c (delNode a l) r
| a > c = Node c l (delNode a r)
| otherwise = combine l r
where combine Nil t = t
combine (Node c ll rr) x= Node c ll (combine rr x)
测试
-- .........................................................................
-- toTree [1,3,2,4356,22,56] Nil
-- .........................................................................
-- Node {content = 1,
-- left = Nil,
-- right = Node {content = 3,
-- left = Node {content = 2,
-- left = Nil,
-- right = Nil},
-- right = Node {content = 4356,
-- left = Node {content = 22,
-- left = Nil,
-- right = Node {content = 56,
-- left = Nil,
-- right = Nil}},
-- right = Nil}}}
-- .........................................................................
-- 1
-- 3
-- 2 4356
-- 22
-- 56
-- .........................................................................
-- after delNode
-- 1
-- 3
-- 2 22
-- 56
-- .........................................................................