Хобрук: Ваш путь к мастерству в программировании

Поддеревья бинарных деревьев в диапазоне Haskell

У меня есть двоичное дерево, определенное следующим образом:

data BSTree = Void | BSNode BSTree Integer BSTree

и хотел бы написать функцию

subTree:: Integer -> Integer -> BSTree -> BSTree

который возвращает все подмножество деревьев с ключом ‹= ‹ b.

Я попробовал следующее

subTree:: Integer -> Integer -> BSTree -> BSTree
subTree a b Void = Void
subTree a b (BSNode leftTree key rightTree) 
    | key < a = BSNode Void key (subTree key b rightTree)
    | b < key = BSNode (subTree a key leftTree) key Void
    | a <= key && b > key = BSNode (subTree a key leftTree) key (subTree key b rightTree)

но не получить правильный вывод. Может ли кто-нибудь указать на ошибку в моей логике?

recursion tree haskell
09.10.2019

  • Подсказка: если key < a, вы все равно возвращаете BSNode, который содержит key. То же самое для b < key. 09.10.2019
  • при чем тут высота дерева? 09.10.2019
  • Извиняюсь, Мозг затухает в названии. @WillemVanOnsem Это правда, но я не уверен, что мне следует использовать вместо этого. 09.10.2019
  • @AdityaSubramanian: вы выполняете рекурсию по правому поддереву, без создания узла на этом уровне. 09.10.2019
  • Хорошо конечно! Благодарю вас! 09.10.2019

Ответы:


1

На каждом шаге рекурсии вы должны предоставить аргументы a и b:

data BSTree = Void | BSNode BSTree Integer BSTree deriving Show

subTree:: Integer -> Integer -> BSTree -> BSTree
subTree a b Void = Void
subTree a b (BSNode leftTree key rightTree) 
 | key < a = --your logic here
 | b < key = -- your logic here
 | a <= key && b > key = BSNode (subTree a b leftTree) key (subTree a b rightTree)

t1 = BSNode Void 5 Void
t2 = BSNode Void 6 Void
t3 = BSNode Void 7 Void
t4 = BSNode t1 8 (BSNode t1 7 t2)

В этом примере:

   subTree 6 10 t4
=> BSNode Void 8 (BSNode Void 7 (BSNode Void 6 Void))
09.10.2019
Новые материалы
Управление состоянием в микрофронтендах
Стратегии бесперебойного сотрудничества Микро-фронтенды — это быстро растущая тенденция в сфере фронтенда, гарантирующая, что удовольствие не ограничивается исключительно бэкэнд-системами..
Декларативное и функциональное программирование в стиле LINQ с использованием JavaScript с использованием каррирования и генератора ...
LINQ - одна из лучших функций C #, которая обеспечивает элегантный способ написания кода декларативного и функционального стиля, который легко читать и понимать. Благодаря таким функциям ES6,..
Структуры данных в C ++ - Часть 1
Реализация общих структур данных в C ++ C ++ - это расширение языка программирования C, которое поддерживает создание классов, поэтому оно известно как C с классами . Он используется для..
Как я опубликовал свое первое приложение в App Store в 13 лет
Как все началось Все началось три года назад летом после моего четвертого класса в начальной школе. Для меня, четвертого класса, лето кажется бесконечным, пока оно не закончится, и мой отец..
Что в лицо
Очерк о возвращении физиогномики и о том, почему мы должны это приветствовать. История начинается со странной науки. Р. Тора Бьорнсдоттир, Николас О. Рул. Видимость социального класса по..
Почему шаблоны проектирования и почему нет?
Сложность — мать всех проблем в программировании. Программное обеспечение должно быть разработано с точки зрения того, кто его поддерживает, а не того, кто его пишет, потому что программное..
Создание дизайна обуви с помощью машинного обучения
Обувь. Что подождать? Я думал, что речь пойдет о машинном обучении! Ну это так. Если бы вы пошли на Amazon, сколько обуви вы бы нашли? Наверное, много, не так ли? Но много ли в них..