Построение дерева в Haskell

Question

Я новичок в Haskell, и я пытаюсь построить дерево, которое содержит целые числа, а каждый элемент в левом поддереве - < = значение узла. Это код, который я написал до сих пор, но я не знаю, как сделать рекурсию внутри. Буду признателен, если бы вы могли дать мне несколько советов.

data Tree = Leaf | Node Int Tree Tree 
    deriving (Eq, Show, Read, Ord) 

insert :: Int -> Tree -> Tree 
insert x (Tree n i t1 t2) = 

Из того, что я понимаю, что я должен проверить каждый узел дерева и посмотреть, если есть ИНТ к нему, а затем рекурсивно искать поддеревьев. Пожалуйста, помогите

благодаря

EDIT:

мне удалось сделать что-то, но это, кажется, что новые узлы не будут созданы или я проверяю это неправильно, это новый код:

data Tree = Leaf | Node Int Tree Tree 
    deriving (Eq, Show, Read, Ord) 

insert :: Int -> Tree -> Tree 
insert x Leaf = Node x Leaf Leaf 
insert x (Node i t1 t2) 
       | x <= i = insert x t1 
       | otherwise = insert x t2 

Чтобы проверить это, я пишу:

let tree = insert 5 (insert 10 (insert 11 (insert 12 (insert 15 tree)))) 

Но когда я пишу в GHCI:

tree 

я получаю:

Node 5 Leaf Leaf 

Answer 1

Когда вы insert ИНГ в узел, вы возвращаете, что будет insert ред в одну сторону Node, а не новый Node с данными insert эд в одну сторону. Только на уровне Leaf вы создаете новый узел.

insert :: Int -> Tree -> Tree 
insert x Leaf = Node x Leaf Leaf 
insert x (Node i t1 t2) 
      | x <= i = Node i (insert x t1) t2 
      | otherwise = Node i t1   (insert x t2) 

Answer 2

Проблемы с рекурсивными случае для Node является то, что, хотя вы называете insert сделать новый подраздел дерево либо на левом или справа, после этого вы не перестраиваете родительское дерево, вы просто возвращаете новое вспомогательное дерево.

Например, первый случай должен быть Node i (insert x t1) t2, и аналогичным образом для второго случая.