F # как отразить двоичное дерево - PullRequest
Новая
       12

F # как отразить двоичное дерево

0 голосов
/ 07 сентября 2018

новичок в F # Я пытаюсь перевернуть поддеревья на ветках.

мы должны использовать следующие типы данных 

 type btree = Empty | Node of btree * int * btree
 type finding = NotFound | Found of int

пример дерева 

 let s = Node (Node(Empty, 5, Node(Empty, 2, Empty)), 3, Node (Empty, 6, Empty))
 (*
      (3)
     /    \
    (5)   (6)
    / \   |  \
   () (2) () ()
      / \
     () ()
 *)

вот мой код: 

 let rec mirror t = function
     | Node(Empty, t, Empty) -> t 
     | Node (t1, t, t2) ->  
     | _ -> failwith "Empty"

пример ввода и вывода: 

 mirror (Node (Node (Empty, 1, Empty), 3, Node (Empty, 4, Node (Empty, 7, Empty)))

вернется 

 Node (Node (Node (Empty, 7, Empty), 4, Empty), 3, Node (Empty, 1, Empty))

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

Интересно, должен ли я реализовать другую функцию для удаления / вставки узлов? Любая помощь с благодарностью!

Ответы [ 2 ]

0 голосов
/ 07 сентября 2018

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

let rec mirror t = function
    | Node(Empty, t, Empty) -> t 
    | Node (t1, t, t2) ->  
    | _ -> failwith "Empty"

Вы начинаете с того, что позволяете своей функции вызывать себя рекурсивно, добавляя ключевое слово rec. Вы правы в этом, и на самом деле очень важно осознать, что для решения этой задачи необходимо создать рекурсивную функцию. Потому что, действительно, что значит «отражать» дерево? Зеркальное отображение означает, что в каждом узле, переверните порядок поддеревьев и отразите каждое поддерево.

Это рекурсивное определение, поскольку для зеркального отражения узла вам необходимо отразить поддеревья. Итак, вы правы в добавлении ключевого слова rec. Однако в вашем коде вы неправильно обрабатываете состояние терминала Empty. Используя ваше определение btree, вы в конечном итоге увидите дерево Empty, что означает, что вы в конечном итоге сгенерируете исключение (используя failwith). Это явно не желаемое поведение. Как выглядит зеркало пустого дерева? Пустое! Способ обработки этого случая - заменить | _ -> failwith "Empty" на | Empty -> Empty.

Теперь в F # let foo = function | ... является просто синтаксическим сахаром для let foo <arg> = match <arg> with | ..., что означает, что ваша функция на самом деле принимает два параметра: t и один, который скрыт сахаром function. Я предполагаю, что это не то, что вам нужно, поэтому вы должны либо удалить неиспользуемый в данный момент параметр t, либо заменить function на match t with.

Причина, по которой параметр t в настоящее время не используется, заключается в том, что t возвращается в целочисленное значение узла в случаях совпадения | Node(..., t, ...). Это также означает, что на данный момент лучшим предположением для компиляторов является то, что тип возвращаемого значения mirror должен быть int, а не btree, поскольку в первом случае вы возвращаете int.

И последнее замечание: нет никакой причины напрямую обращаться с делом с пустыми поддеревьями, поскольку это также просто btree с.

Имея в виду все вышесказанное, я надеюсь, что имеет смысл, почему мое решение проблемы 

let rec mirror = function
    | Empty -> Empty
    | Node(t1, i, t2) -> Node(mirror t2, i, mirror t1)
0 голосов
/ 07 сентября 2018

Зеркальное отображение означает создание левой ветви правой ветви, а правой ветви левой ветви. Так что в вашей рекурсивной функции сделайте это. Например, если вы начинаете с базового дерева из 3 узлов: 

   1
2     3

затем зеркалирование, которое будет 

    1
  3   2

Итак, в коде это означает: 

let rec mirror t = function
     | Node(Empty, t, Empty) -> t 
     | Node (left, value, right) -> Node (right, value, left)

За исключением того, что это не будет работать для больших деревьев, но это только начало. Что вам действительно нужно, так это зеркало правого и левого узлов. Вы должны иметь возможность завершить вышеописанную функцию, добавив 2 вызова для зеркала в правильном месте в последней строке предложения соответствия.

...