Courses of functional programming 2015

FP; Lab 2.hs

module Lab2 where  

data BinaryTree = Empty | Node BinaryTree Integer BinaryTree 

emptyTree :: BinaryTree-- создание пустого дерева 
emptyTree = Empty


insert :: BinaryTree -> Integer -> BinaryTree -- добавления элемента 
insert (Empty) a = Node Empty a Empty
insert (Node left x right) a
    | a > x = Node left x (insert right a)
    | a < x = Node (insert left a) x right
    | a == x = Node left x right

remove :: BinaryTree -> Integer -> BinaryTree -- удаление элемента
remove (Empty) a = Empty
remove (Node left x right) a
    | a > x = Node left x (remove right a)
    | a < x = Node (remove left a) x right
    | a == x =
        if isEmpty right
        then left
        else Node left leftmost right'
            where
                isEmpty Empty = True
                isEmpty _ = False
                (leftmost, right') = deleteleftmost right
                    where
                        deleteleftmost (Node Empty x right) = (x, right)
                        deleteleftmost (Node left x right) = deleteleftmost left


containsElement :: BinaryTree -> Integer -> Bool -- поиск элемента
containsElement (Empty) a  = False
containsElement (Node left x right) a 
    | a == x = True
    | a < x  = containsElement left a
    | a > x  = containsElement right a


nearestGE :: BinaryTree -> Integer -> Integer -- поиск в дереве наименьшего элемента, который больше чем заданный или равен заданному
nearestGE Empty x = error "No element which is equal to or greater!"
nearestGE (Node left x right) a
    | a == x = a
    | a > x = if isEmpty right then error "No element which is equal to or greater!" else nearestGE right a 
    | a < x = findMoreThenA'ButLessThenX left x a
        where
            isEmpty Empty = True
            isEmpty _ = False
            findMoreThenA'ButLessThenX (Node left b right) x a 
                | b < a = a
                | b > a = findMoreThenA'ButLessThenX left a b


treeFromList :: [Integer] -> BinaryTree -- создание дерева из списка
treeFromList [] = emptyTree
treeFromList (h : t) = insert (treeFromList t) h


listFromTree :: BinaryTree -> [Integer] -- создание списка из дерева
listFromTree Empty=[]
listFromTree (Node left x right) = (listFromTree left ++ [x]) ++ listFromTree right

-- проверка когда есть одинаковый элемент
--test = listFromTree (emptyTree `insert` 1 `insert` 2 `insert` 3 `insert` 10 `insert` 5 `insert` 7 `insert` 9 `remove`8 )
--a = treeFromList test
--b = nearestGE a 5
-- проверка когда есть элемент больше
--test = listFromTree (emptyTree `insert` 1 `insert` 2 `insert` 3 `insert` 10 `insert` 5 `insert` 7 `insert` 9 `remove`8 )
--a = treeFromList test
--b = nearestGE a 6
-- проверка когда выводится ошибка
alexTest = listFromTree (emptyTree `insert` 1 `insert` 2 `insert` 3 `insert` 10 `insert` 5 `insert` 7 `insert` 9 `remove`8 )
a = treeFromList test
res = nearestGE a 5

main = do
    putStrLn(show alexTest)
    putStrLn(show res)	

Task Lab 2.txt

Реализуйте структуру данных "бинарное дерево поиска" для целых чисел без балансировки. Реализация включает функции:

Добавления элемента: insert :: BinaryTree -> Integer -> BinaryTree
Удаления элемента: remove :: BinaryTree -> Integer -> BinaryTree
Создания пустого дерева: emptyTree :: BinaryTree
Поиска элемента в дереве: containsElement :: BinaryTree -> Integer -> Bool
Поиска в дереве наименьшего элемента, который больше или равен заданному: nearestGE :: BinaryTree -> Integer -> Integer
Создания дерева из списка: treeFromList :: [Integer] -> BinaryTree
Создания списка из дерева: listFromTree :: BinaryTree -> [Integer]
Операторы insert и remove должны поддерживать цепочки вызовов в инфиксной форме:

listFromTree (emptyTree `insert` 1 `insert` 2 `insert` 3) === [1,2,3]