Обход в ширину - Prolog

Формулировка задачи:

Помогите ребята переделать эту код ! Обход дерева «в ширину» и вывод пути в виде последовательности элементов.

domains
     treetype = tree (integer, treetype, treetype); empty ()
 
    predicates
     print_all_elements (treetype)
 
    clauses
     print_all_elements (empty).
 
     print_all_elements (tree (X, Y, Z)):-
       write (X), nl,
       print_all_elements (Y),
       print_all_elements (Z).
 
    goal
      print_all_elements  (tree (1,   
                                tree (3,  
                                   tree (5, empty, empty),  
                                       tree (2, empty, empty)),
                             tree (4, 
                               tree (6, empty, empty),  
                                       tree (9, empty, empty)))),nl,fail;true.

Это обход дерева "сначала вглубь"

Решение задачи: «Обход в ширину»

Листинг программы

domains
     treetype = tree (integer, treetype, treetype); empty
     treelist = treetype*
 
predicates
     print_all_elements (treetype)
     print_list (treelist)
     append(treelist, treelist, treelist)
 
clauses
     print_all_elements (Tree) :-
          print_list([Tree]).
 
     print_list([]). 
     print_list([empty | Tail]) :-
          print_list(Tail).  
     print_list([tree (X, Y, Z) | Tail]) :-
          write (X), nl,
          append(Tail, [Y, Z], New),
          print_list(New).  
 
     append([H | T1], L2, [H | T]) :-
          append(T1, L2, T).
     append([], L, L).

Объяснение кода листинга программы

В представленном коде используется язык программирования Prolog. Всего в коде 20 элементов, которые можно разделить на следующие группы:

domains - определения типов данных. В данном случае определен тип данных treetype и тип данных treelist.
predicates - определения функций. В данном случае определены три функции: print_all_elements, print_list и append.
clauses - определения правил вывода. Здесь определены правила вывода для функций print_all_elements и print_list. Рассмотрим подробнее каждое из определений:
domains
- treetype = tree (integer, treetype, treetype) - здесь определен тип данных treetype, который может принимать значения tree, где integer - это целочисленное значение, а treetype - это еще один экземпляр типа данных treetype.
- empty - это пустое значение типа данных treetype.
predicates
- print_all_elements (treetype) - эта функция выводит все элементы, которые соответствуют типу данных treetype.
- print_list (treelist) - эта функция выводит список, который соответствует типу данных treelist.
- append(treelist, treelist, treelist) - эта функция добавляет один список к другому.
clauses
- print_all_elements (Tree) :- print_list([Tree]). - это правило вывода для функции print_all_elements. Здесь предполагается, что если передается экземпляр типа данных treetype, то это означает, что нужно вывести список, содержащий этот экземпляр.
- print_list([]). - это правило вывода для функции print_list. Если передается пустой список, то он просто выводится.
- print_list([empty | Tail]) :- print_list(Tail). - если в списке есть экземпляр типа данных treetype со значением empty, то он удаляется, и функция вызывается рекурсивно для оставшейся части списка.
- print_list([tree (X, Y, Z) | Tail]) :- write (X), nl, append(Tail, [Y, Z], New), print_list(New). - если в списке есть экземпляр типа данных treetype с целочисленным значением X, то это значение выводится, а затем вызывается функция append для объединения оставшейся части списка с новым списком, содержащим значения Y и Z.
- append([H | T1], L2, [H | T]) :- append(T1, L2, T). - это правило вывода для функции append. Если первый элемент списка T1 совпадает с первым элементом списка L2, то он добавляется в новый список, а затем вызывается функция append для объединения оставшейся части списка T1 с новым списком.
- append([], L, L). - если первый список пустой, то он просто заменяется вторым списком.