Шаблон программы для работы с деревьями на Prolog

      Комментарии к записи Шаблон программы для работы с деревьями на Prolog отключены

Помечено: ,

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #3358

    Напишем программу, которая позволяет вводить, выводить дерево, а также удалять заданные поддеревья.

    domains
      treetype = tree(integer, treetype, treetype); empty
    predicates
      print_tree(treetype, integer)
      print_spaces(integer)
      
      select_subtree_and_insert(treetype, integer, treetype)
      insert_into_subtree(treetype, integer, integer, treetype)
      
      remove_subtree(treetype, treetype)
      
      menu(integer, treetype)
    clauses
      print_tree(empty, _Depth):-!.
      print_tree(tree(TopValue, Left, Right), Depth):-
        SubtreesDepth = Depth + 1,
        print_tree(Left, SubtreesDepth),
        print_spaces(Depth), write(TopValue), write("<"), nl,
        print_tree(Right, SubtreesDepth).
        
      print_spaces(SpaceNumber):-
      	SpaceNumber <= 0, !;
      	write("\t"),
      	TailSpaceNumber = SpaceNumber - 1,
      	print_spaces(TailSpaceNumber).
        
      select_subtree_and_insert(empty, Value, tree(Value, empty, empty)):-!.
      select_subtree_and_insert(Tree, Value, TreeWithValue):-
        print_tree(Tree, 0),
        write("enter: \n\t0 to insert node into left subtree\n\t1 - into right subtree\n: "), 
        readint(LeftOrRight), 
        insert_into_subtree(Tree, LeftOrRight, Value, TreeWithValue).
      	
      insert_into_subtree(tree(TopValue, Left, Right), 0, Value, tree(TopValue, LeftWithValue, Right)):-
        select_subtree_and_insert(Left, Value, LeftWithValue), !.
      insert_into_subtree(tree(TopValue, Left, Right), 1, Value, tree(TopValue, Left, RightWithValue)):-
        select_subtree_and_insert(Right, Value, RightWithValue), !.
      insert_into_subtree(Tree, _BadSubtree, Value, TreeWithValue):-
        write("you select wrong number"), nl,
        select_subtree_and_insert(Tree, Value, TreeWithValue).
        
      remove_subtree(empty, empty):-!.
      remove_subtree(tree(_TopValue, empty, empty), empty):-!.
      remove_subtree(Tree, empty):-
      	print_tree(Tree, 0),
      	write("remove this subtree? (0/other value): "), readint(Select),
      	Select = 1, !.
      remove_subtree(tree(TopValue, Left, Right), tree(TopValue, LeftWithoutSubtree, Right)):-
      	write("select subtree for remove (left = 0, right = other value): "),
      	readint(Select), Select = 0, !, 
      	remove_subtree(Left, LeftWithoutSubtree).
      remove_subtree(tree(TopValue, Left, Right), tree(TopValue, Left, RightWithoutSubtree)):-
        	remove_subtree(Right, RightWithoutSubtree).
      
      menu(0, Tree):-
      	write("enter:\n"),
      	write("\t1 - print tree\n"),
      	write("\t2 - add node into tree\n"),
      	write("\t3 - remove subtree:\n"),
      	write("\t4 - clear tree\n"),
      	write("\t0 - exit"), nl,
      	write(": "),
      	readint(Select), !,
      	Select <> 0, menu(Select, Tree).
      menu(1, Tree):-
      	print_tree(Tree, 0), nl,
      	!, menu(0, Tree).
      menu(2, Tree):-
      	write("enter value for insert: "), readint(Value), !,
      	select_subtree_and_insert(Tree, Value, TreeWithValue),
      	menu(0, TreeWithValue).
      menu(3, Tree):-
      	remove_subtree(Tree, TreeWithoutSubtree), 
      	!, menu(0, TreeWithoutSubtree).
      menu(4, _Tree):-
      	menu(0, empty), !.
      menu(_, Tree):-
      	write("you enter bad menu point"), nl,
      	!, menu(0, Tree).
        
    goal
      menu(0, empty).

    Функция menu позволяет пользователю выбрать номер пункта и выполнить добавление узла, удаление поддерева или вывод дерева. Подробно эта функция описана в теме «Реализация меню на Prolog«.

    Функция вывода дерева описан в теме «Вывод дерева на Prolog«.

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

    Для вставки узла программа также, в интерактивном режиме, предлагает выбрать позицию, перемещаясь от корня вправо или влево. Поиск позиции продолжается до тех пор, пока очередное поддерево не окажется пустым. На каждом шаге на экран выводится текущее поддерево. Функция select_subtree_and_insert осуществляет ввод числа (добавляемого в дерево значения) и вызывает функцию insert_into_subtree, выполняющую навигацию по дереву и вставку.

Для ответа в этой теме необходимо авторизоваться.