0
我想知道他們是否是一種從右向左插入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
來做到這一點。遞歸方法對於這類任務會更好嗎?任何形式的幫助,將不勝感激。
最簡單的方法可能是'listToTree xs = foldl(\ acc x - > insert x acc)Empty $ reverse xs'。 –
@WillemVanOnsem謝謝。我也意識到你可以做'listToTree [] =空 listToTree(x:xs)=插入x(listToTree xs)' – RoadRunner
@WillemVanOnsem你可以把它作爲答案,我會很樂意接受它。 – RoadRunner