Функциональное программирование Двоичное дерево поиска Домашнее задание - PullRequest
Новая
       11

Функциональное программирование Двоичное дерево поиска Домашнее задание

0 голосов
/ 19 марта 2019

Так что мне нужно написать функцию вставки для двоичного дерева, чтобы сделать его двоичным деревом поиска, но у меня возникли некоторые проблемы. Все есть функции, поэтому я понимаю, что нет понятия государства. Поэтому мне нужно рекурсивно создавать дерево снова и снова при вставке. У меня проблемы с тем, чтобы обернуть голову вокруг этой идеи. 

treenode -> procedure(val, left, right) procedure(some) if some then -(some, 1) then right else left else val

Это позволяет мне создавать узлы и получать доступ к значению, левому поддереву и правому поддереву следующим образом (0 обозначает пустое дерево): 

.treenode(4, 0, 0)

чтобы создать более сложное дерево, я могу сделать: 

.treenode(4, .treenode(3, 0, 0), .treenode(6, .treenode(2, 0, 0), 0))

Я дошел до того, что вставлял в пустое дерево: 

insert -> procedure(root, value) if empty(root) then .treenode(value, 0, 0) else insert_recursive(root, .treenode(value, 0, 0)

Здесь я не могу понять, как вставить в дерево, как это. В этом языке нет концепции состояния, поэтому мне нужно каким-то образом рекурсивно добавить новый узел со значением в текущее дерево. Если бы кто-то мог дать мне подсказку, я был бы очень признателен. Вот как я должен это называть: 

tree = empty
tree = insert(tree, 4)
tree = insert(tree, 6)
....
and so on

1 Ответ

2 голосов
/ 19 марта 2019

Я никогда раньше не видел эту грамматику, так что терпите меня, если я неправильно понял синтаксис.Надеемся, что код демонстрирует, что нужно сделать -

  1. , если дерево пустое, нет значения для сравнения, создайте одноэлементный узел со значением.Это часть, которую вы уже завершили.
  2. В противном случае дерево не пусто, поэтому у нас есть значение для сравнения.Если значение для вставки меньше значения корня, создайте новый узел, состоящий из значения корня, вставьте значение в левую ветвь корня и оставьте правую ветвь корня нетронутой
  3. , если значение больше чемзначение корня, сделайте то же самое, что и выше, но вставьте новое значение в ветку вправо корня, вместо left
  4. значение не меньше, чеми не больше, чем значение корня, поэтому оно равно значению корня и нечего вставить.В этом случае верните неизмененный корень

Точки маркера соответствуют нумерованным комментариям ниже - 

insert -> procedure(root, value)
  if empty(root) then           #1
    .treenode(value, 0, 0)
  else if value < root.value    #2 
    .treenode (root.value, insert(root.left, value), root.right)
  else if value > root.value    #3
    .treenode (root.value, root.left, insert(root.right, value))
  else                          #4
    root

StackOverflow позволяет нам запускать фрагменты JavaScript непосредственно в сообщениях с ответами.Вот функциональный фрагмент, который позволяет вам увидеть эту концепцию в действии - 

const empty =
  {}

const treenode = (value, left = empty, right = empty) =>
  ({ value, left, right })

const insert = (t, value) =>
  t === empty
    ? treenode (value, empty, empty)
: value < t.value
    ? treenode (t.value, insert (t.left, value), t.right)
: value > t.value
    ? treenode (t.value, t.left, insert (t.right, value))
: t

const print = (t, pre = '', child = '') =>
  t === empty
    ? pre + '∅\n'
    : print
        ( t.right
        , child + '┌── '
        , child + '.   '
        )
    + pre + String (t.value) + '\n'
    + print
       ( t.left
       , child + '└── '
       , child + '.   '
       )

let tree = empty
tree = insert (tree, 4)
tree = insert (tree, 6)
tree = insert (tree, 9)
tree = insert (tree, 3)
tree = insert (tree, 5)
tree = insert (tree, 1)

console.log (print (tree))

Программа печатает построенное tree.Символ ∅ представляет пусто - 

.   .   .   ┌── ∅
.   .   ┌── 11
.   .   .   └── ∅
.   ┌── 9
.   .   └── ∅
┌── 6
.   .   ┌── ∅
.   └── 5
.   .   └── ∅
4
.   ┌── ∅
└── 3
.   .   ┌── ∅
.   └── 1
.   .   └── ∅
...