反向訂購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插入

回答

相關問題