反向订购BST插入

我想知道他们是否是一种从右向左插入BST列表项的方式。到目前为止，我可以从左至右插入项目。反向订购BST插入

代码：

-- Type constructor 
data Tree a = Empty | Node a (Tree a) (Tree a) 
    deriving (Eq, Show) 

-- inserts into BST 
insert :: (Ord a) => a -> Tree a -> Tree a 
insert x Empty = Node x Empty Empty 
insert x (Node y l r) 
    | y == x = Node y l r 
    | y < x = Node y l (insert x r) 
    | y > x = Node y (insert x l) r 

-- Converts list to a BST 
listToTree :: (Ord a) => [a] -> Tree a 
listToTree xs = foldl (\acc x -> insert x acc) Empty xs

什么我目前正在实现：

Prelude> listToTree [4,2,6] 
Node 4 (Node 2 Empty Empty) (Node 6 Empty Empty)

但我希望相反的顺序：

Node 6 (Node 2 Empty (Node 4 Empty Empty)) Empty

我真的不知道怎么样我可以修改foldl来做到这一点。递归方法对于这类任务会更好吗？任何形式的帮助，将不胜感激。

来源

2017-08-12 RoadRunner

最简单的方法可能是'listToTree xs = foldl（\ acc x - > insert x acc）Empty $ reverse xs'。 –

@WillemVanOnsem谢谢。我也意识到你可以做'listToTree [] =空 listToTree（x：xs）=插入x（listToTree xs）' – RoadRunner

@WillemVanOnsem你可以把它作为答案，我会很乐意接受它。 – RoadRunner

显然要做的事情是将reverse列表送到foldl。使用foldr可以达到同样的效果。

如果你问如何修改insert指令本身，你想要的是插入的最后一个节点是根，以及任何已经在树中移动的节点。所以：

insert x (Node y l r) -- Note: x is the new value and y the existing root. 
    | y == x = Node y l r -- Don't insert a dup (per original) 
    | y > x = Node x l (insert y r) -- make x the new root and y goes in the left tree 
    | y < x = Node x (insert y l) r -- make x the new root and y goes in the right tree

来源

2017-08-12 17:55:26

反向订购BST插入

回答

相关问题