逆順BST挿入

Question

BSTにリスト項目を右から左に挿入する方法があるかどうかは疑問でした。これまでのところ、左から右に項目を挿入できます。

コード：

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

しかし、私は逆の順序たい：

-- 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 

私は現在達成しています何

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

私はどのように本当にわからないがこれを行うにはfoldlを変更できます。このようなタスクのために再帰的アプローチが良いでしょうか？どんな種類の助けでも感謝します。

Answer 1

に送付する前にリストをreverseにするのは明らかです。 foldrを使用しても同じ効果が得られます。

insert命令自体を変更する方法を尋ねる場合、最後に挿入されたノードがルートになり、すでにツリーの下に移動していたものがあります。 so：

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