Вывести вершины на заданной высоте в дереве

      Комментарии к записи Вывести вершины на заданной высоте в дереве отключены

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

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

    questioner
    Участник

    Под высотой я имею ввиду количество дуг от вершины до корня дерева.

  • #1843

    Пусть узел дерева задается списком [Значение|Дочерние_узлы], т.е. работаем с N-арным деревом.
    Для обработки всех дочерних узлов нам потребуется функция, применяющая что-либо ко всем элементам списка. В SWI Prolog есть встроенный предикат apply(:Goal, +List), но если его нет в вашем диалекте – можно написать самому:

    apply(_Pred, []):-!.
    apply(Pred, [H|T]):-
      call(Pred, H), apply(Pred, T).

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

    tree_deep_out(0, [CurrentNode|_]):- 
      write(CurrentNode), write(' '), nl, !.
    tree_deep_out(Depth, [_CurrentNode|[Childs]]):-
      DepthChildNodes is Depth - 1,
      apply(tree_deep_out(DepthChildNodes), Childs).

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

    Пример описания дерева и работы правила:

      1
     / \
    2   3
       / \
      5   4
     /     \
    6       7
     
    ?- tree_deep_out(0,[1,[[2,[]],[3,[[5,[[6,[]]]],[4,[[7,[]]]]]]]]).
    1 true.
     
    ?- tree_deep_out(2,[1,[[2,[]],[3,[[5,[[6,[]]]],[4,[[7,[]]]]]]]]).
    5 4 true.

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