Arhn - архитектура программирования

Алгоритм предварительного порядка двоичного дерева поиска в OCaml

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

Алгоритм выглядит следующим образом:

BEGIN
   WRITE ( "(" )
   IF (NOT EMPTY tree) THEN 
      IF (NOT EMPTY (left_leaf tree)) OR (NOT EMPTY (right_leaf tree)) THEN BEGIN
        WRITE (" ", root tree, " ")
        preorder (left_leaf tree)
        WRITE (" ")
        preorder (right_leaf tree)
      END ELSE
        WRITE (" ", root tree, " ")
   WRITE ( ")" ); {this has to be always executed}
END

Это моя неудачная попытка в OCaml:

let rec preorderParenthesed tree = 

   print_string "(" in
   if not (isEmptyTree tree) then (
      if not (isEmptyTree(leftLeaf tree)) || not (isEmptyTree(rightLeaf tree)) then begin
        print_string " ";
        print_string (string_of_root (root tree));
        print_string " ";
        preorderParenthesed (leftLeaf tree);
        print_string " ";
        preorderParenthesed (rightLeaf tree);
      end else
        print_string " ";
        print_string (string_of_root (root tree));
        print_string " "; 
    ) 
    else if true then print_string ")\n";;

Любая помощь будет оценена

type bst = 
Empty   
| Node of (key * bst * bst);;
algorithm binary-search-tree ocaml
18.09.2017

  • Можете ли вы привести простой пример с ожидаемым результатом? Кроме того, можете ли вы показать нам, как вы определяете свою древовидную структуру? 18.09.2017
  • Да. 1) Пустое дерево -> ( ) 2) Дерево A, Пустые листья -> (A) 3) Дерево A, B левый лист, C правый лист -> ( A ( B ) ( C ) ) 4) Дерево A, B левый лист, Пустой лист -> ( A ( B ) ( ) ) Пожалуйста, проверьте вопрос еще раз, чтобы увидеть структуру типа. 18.09.2017

Ответы:


1

Ваша функция может стать намного проще, используя сопоставление с образцом:

type 'a bst = Empty | Node of ('a * 'a bst * 'a bst)

let rec string_of_tree ~f = function
| Empty ->
  "()"
| Node (value, Empty, Empty) ->
  Printf.sprintf "(%s)" (f value)
| Node (value, left, right) ->
  Printf.sprintf "(%s %s %s)"
    (f value)
    (string_of_tree ~f left)
    (string_of_tree ~f right)

val string_of_tree : f:('a -> string) -> 'a bst -> string = <fun>

f — это просто функция string_of_*.

Паттерны описывают следующие случаи:

  1. The tree is empty
    • ()
  2. The tree is not empty, but both sub-trees are
    • (value)
  3. The tree is not empty, and case 2. didn't check
    • (value left_subtree right_subtree)
18.09.2017
  • Это восхитительно. Не мог и подумать о чем-то подобном, увидев структуру алгоритма. Спасибо. 18.09.2017
  • Это только вопрос тренировки. Как только вы привыкнете к такому образу мышления, такие вещи станут естественными. Вас могут заинтересовать 99 проблем в OCaml. 19.09.2017

    • 2

    Я подозреваю, что вы пропустили начало/конец в ветке else:

      end else
    print_string " ";
    print_string (string_of_root (root tree));
    print_string " ";
    18.09.2017
  • Привет, Пьер Г., будучи искренним с вами, я не знаком с началом и концом в ocaml, так как я впервые пытаюсь выполнить функцию, используя их, а также используя строки, заканчивающиеся на ; что я до сих пор не уверен, как это работает. 18.09.2017
  • если вы не инкапсулируете 3 print_string выше в начало/конец, ветвь else if/then/else будет выполнять только print_string . Но то, что вы хотите, это выполнить последовательность 3 print_string как уникальный блок - это то, что делает начало/конец (или, как вы делали в другом месте вашего кода: открывающая и закрывающая скобки делают то же самое, что и начало/конец). 18.09.2017

    • 3

    Обход предварительного заказа может быть немного запутанным, но вот небольшой обзор того, как он работает:

    1. Посетите текущий узел
    2. Обход левого поддерева
    3. Обход правого поддерева

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

    let rec traversePreOrder node cb =
  match node with
  | Empty  -> "()"
  | Node (value, left, right) ->
      cb value; 
      traversePreOrder left cb; 
      traversePreOrder right cb;

    Где вы можете перемещаться по узлам, используя описанные выше шаги, и вызывать обратный вызов (функция, которая может печатать значение узла) при посещении узла.

    18.09.2017
    Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..