Как найти узел, содержащий минимальный элемент в двоичном дереве в Haskell?

Question

Я пытаюсь решить аналогичную проблему (найти кратчайший список в дереве списков), и я думаю, что решение этой проблемы было бы хорошим началом.

Учитывая тип данных, как

data (Ord a, Eq a) => Tree a = Nil | Node (Tree a) a (Tree a) 

Как найти узел, который содержит минимальный элемент в бинарном дереве выше? Пожалуйста, не то, чтобы это не двоичное дерево поиска.

Я пытаюсь думать рекурсивно: минимум - это минимум между левым, правым поддеревьями и текущим значением. Тем не менее, я изо всех сил пытаюсь перевести это на код Haskell. Одна из проблем, с которыми я сталкиваюсь, заключается в том, что я хочу вернуть дерево, а не только значение.

Answer 1

У вас есть правильное понимание. Я думаю, вы должны быть хорошо, если вы можете доказать следующее:

• Может дерево с мин быть Nil
• Дерево с мин, вероятно, имеет минимальное значение не в корне

Таким образом, вместо просто сравнивая значения, вам может потребоваться сопоставить образцы поддеревьям, чтобы получить значение корневого узла.

Вы не указали, каков тип функции. Итак, давайте предположим, что это выглядит так:

findmin :: Tree a -> Tree a 

Теперь предположим, что у вас уже есть функция, которая находит мин дерева. Что-то вроде:

findmin Nil = Nil -- no tree - no min 
findmin (Node l x r) = case (findmin ..., findmin ...) of 
     -- like you said, find min of the left, and find min of the right 
     -- there will be a few cases of what the min is like on the left and right 
     -- so you can compare them to x 
         some case -> how to find the min in this case 
         some other case -> how to find min in that other case 

Возможно, вам понадобятся ответы на первые два вопроса.

Очень сложно дать ответ, не передавая действительный код, так как ваше мышление уже правильно.

Answer 2

Примечание: ограничения класса в объявлениях типов данных больше не поддерживаются в Haskell 2010 и обычно не рекомендуются. Так что вместо этого:

data Tree a = Nil 
       | Node (Tree a) a (Tree a) 

Подумайте рекурсивно:

getMinTree :: Ord a => Tree a -> Maybe (Tree a) 
getMinTree = snd <=< getMinTree' 

getMinTree' :: Ord a => Tree a -> Maybe (a, Tree a) 
getMinTree' Nil = ??? 
getMinTree' (Node Nil value Nil) = ??? 
getMinTree' (Node Nil value right) = ??? 
getMinTree' (Node left value Nil) = ??? 
getMin' (Node left value right) = ??? 

Примечание также: нет необходимости в Eq ограничения. Поскольку Eq является суперклассом Ord, ограничение Ord подразумевает ограничение Eq. Я не думаю, что вы, вероятно, будете использовать для этого ==.

Answer 3

Вот подсказка:

Вы можете начать с определения, в качестве вспомогательной функции, как минимум только между двумя деревьями. Node s сравниваются по значению the, игнорируя поддеревья, а сравнение Nil с любым деревом t составляет t минимум (в смысле, мы считаем Nil «самым большим» деревом).Кодирование это может быть сделано случаями:

binaryMin :: Ord a => Tree a -> Tree a -> Tree a 
binaryMin Nil t = t 
binaryMin t Nil = t 
binaryMin (Node l1 v1 r1) (Node l2 v2 r2) = ??? 

Тогда минимальное поддерево следует рекурсия, используя binaryMin:

treeMin :: Ord a => Tree a -> Tree a 
treeMin Nil = Nil 
treeMin (Node left value right) = ??? 
    where l = treeMin left 
     r = treeMin right