Двоичные функции дерева поиска в Haskell

Мне нужна помощь в 3 задачах. Я действительно новичок в Haskell и функциональном программировании.Двоичные функции дерева поиска в Haskell

data Tree = Node Int Tree Tree | Nil

Определить с помощью функции collapse
```
collapse :: Tree -> [Int] 
collapse Nil = [] 
collapse (Node x y z) = (collapse y) ++ [x] ++ (collapse z) 
```
Haskell-Function check :: Tree -> Bool, которая проверяет, является ли дерево является бинарное дерево поиска.
Я проверяю это на дерево и получаю 2 4 7 8 10 | 5 6 10 12. Здесь вы можете увидеть, что все значения в середине отсортированы, но я не знаю, как я должен это кодировать.
Определение Haskell-Function insert :: Int -> Tree -> Tree который добавляет целочисленное значение в дерево и вернуться также бинарное дерево поиска.
Определить с помощью функции insert (2) Haskell-Function merge :: Tree -> Tree -> Tree, которая объединяет два дерева к другому бинарного дерева поиска.

источник

2013-06-08 Chryb

'collapse' является обходным путем. Какое свойство взаимного обхода бинарных деревьев характеризует двоичные деревья поиска? –

Значение левого узла (int) двоичного дерева меньше родительского узла, а значение правого узла больше родительского узла и для каждого дочернего узла. – Chryb

Бинарное дерево является деревом двоичного поиска тогда и только тогда, когда его обход в порядке ...? –

Хорошо, я не буду отвечать на все эти вопросы, но я могу предоставить некоторую помощь.

Если мы на самом деле попробовать collapse на дереве, которое выглядит как этот
```
  a 
     /\ 
     / \    
     b  c 
    /\ /\ 
    d e f g 
```
мы получим [d, b, e, a, f, c, g]. Обратите внимание, что если элемент появляется «слева» элемента в дереве, он «находится слева от» этого элемента в нашем плоском списке. Мы знаем, что если элемент, a, находится слева от элемента, c, в двоичном дереве поиска, то a < c. Поэтому нам просто нужно проверить, что это свойство принадлежит нашему списку.
Вставка элемента в дерево. У нас есть 4 случая, чтобы иметь дело с
```
insert newVal (Node treeVal left right) | newVal < treeVal = <1> 
             | newVal > treeVal = <2> 
             | otherwise  = <3> 
insert newVal Nil = <4> 
```
< где 1> вставляет в узел со значением больше, чем в узле. < 2> - противоположное: узел имеет большее значение, чем новое значение. В 3 они равны, и в 4 мы вставляем в базовый регистр Nil. Вы можете в значительной степени перевести определение бинарного дерева поиска, чтобы заполнить здесь отверстия.
Поскольку мы не пытаемся иметь сбалансированное двоичное дерево, если у нас есть 2 дерева, A и B. Все, что нам нужно сделать, это найти местоположение, в которое будет вставлен корень B, и вставьте туда все дерево.

источник

2013-06-08 17:36:28 jozefg

Двоичные функции дерева поиска в Haskell

ответ

Смежные вопросы