Поиск в ширину по двоичным деревьям в OCaml с использованием очередей - PullRequest
Новая
       33

Поиск в ширину по двоичным деревьям в OCaml с использованием очередей

0 голосов
/ 16 апреля 2019

Я хочу создать поиск в двоичном формате в двоичных деревьях в OCaml, используя очереди, но я не могу заставить его работать.

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

let rec enque v l = 
    match l with
        [] -> [v]
    |   h::t -> h::(enque v t)



let rec qhd l =
    match l with
        h::[] -> h
    |   h::t -> qhd t



let deque l =
    match l with
        [] -> []
    |   h::t -> t



let notempty l = (l != [])


let rec breadthFirstHelp l =
    if notempty l
    then
        let cur = qhd l in
            match cur with
                Empty -> []
           |   (Node(Empty, node, Empty)) -> node::(breadthFirstHelp (deque l))
           |   (Node(left, node, right)) ->
               let l = enque right l in
               let l = enque left l in 
                   node::(breadthFirstHelp (deque l))
    else []

Вот дерево, на котором я тестирую. 

[tree =
  Node
   (Node
     (Node (Empty, "A", Empty), "B",
      Node (Node (Empty, "C", Empty), "D", Empty)),
    "E", Node (Empty, "F", Node (Empty, "G", Node (Empty, "O", Empty))))]

С моим кодом: ["E";«В»;«А»;«А»;«A»]

Ожидаемый результат: [«E»;«В»;"F";«А»;«Д»;"Г";«С»;"O"]

1 Ответ

1 голос
/ 16 апреля 2019

В вашем коде есть три проблемы:

Во-первых, ваша qhd функция не совместима с вашими deque и enque функциями.Действительно, для непустой очереди q и значения any можно ожидать, что добавление элементов в конец очереди не изменит элемент вверху: 

 qhd q = qhd (enque any q)

, тогда как с вашимреализация для очереди q такая, что deque q не является пустой, у вас есть 

 qhd q = qhd (deque q)

Во-вторых, в вашей функции breadthFirstHelp пустой регистр всегда возвращает [], даже если в * есть ожидающие поддеревья1017 *.

Устранение этих двух проблем должно дать вам правильный результат, однако существует последняя проблема с производительностью: функция enque очень обширна, поскольку ей необходимо пройти всю очередь.

Простое решение состоит в том, чтобы разбить список на два 

  type 'a queue = { top: 'a list; bottom: 'a list }

, когда нижний список хранится в обратном порядке.Таким образом, добавление в очередь - это добавление вверху нижнего списка.Принимая во внимание, что для заполнения очереди требуется только взять первый элемент списка top, если он не пустой, или заполнить его из нижнего списка в противном случае.

...