Путь в двоичном дереве - Пролог

Question

У меня проблема с этой домашней работой. Я должен написать код в прологе, который покажет мне самый глубокий путь к листу дерева.

Дерево представлено как:

tree([ [ [],r,[[],u,[[],t,[]]] ], a , [ [], c, [] ]]) 

Где [], как ноль и является корнем.

Он должен показать мне что-то вроде этого: PATH = [a, r, u, t]

я буду очень благодарен.

Решение:

deepest(T,D) :- aggregate(max(L,P),(path(T,P),length(P,L)),max(_,D)). 

path([],[]). 
path([L,K,R],[K|P]) :- path(L,P) ; path(R,P). 

Тест:

?- tree(T),deepest(T,P). 
T = [[[], r, [[], u, [[], t|...]]], a, [[], c, []]], 
P = [a, r, u, t]. 

Answer 1

Я знаю, мы не должны делать ТТВ ... но это решение - как это - вероятно, не будет adeguate для вашего класса. В любом случае, надеюсь, что это поможет вам справиться с такими проблемами в Prolog.

deepest(T,D) :- aggregate(max(L,P),(path(T,P),length(P,L)),max(_,D)). 

path([],[]). 
path([L,K,R],[K|P]) :- path(L,P) ; path(R,P). 

тест:

?- tree(T),deepest(T,P). 
T = [[[], r, [[], u, [[], t|...]]], a, [[], c, []]], 
P = [a, r, u, t]. 

Примечание: после того, как вы усвоили основные из этого языка, как правило, не требуется отладить. Решение достаточно декларативно ...

Answer 2

Поскольку это домашнее задание, я не дам вам решение сразу.

Прежде всего, давайте посмотрим на вашу древовидную структуру. Когда вы смотрите на дерево, вы можете увидеть один из двух вариантов: либо это будет нуль, представленный как [], либо он будет узлом со значением и двумя поддеревьями [LeftSubTree, Value, RightSubTree]. Следовательно, ваш предикат должен иметь два положения для этих двух случаев.

В этих двух случаях, что является самым глубоким путем? Ну, для nil ответ прост: нет узлов, поэтому самый длинный путь на самом деле пустой список.

Для узла дерева, который не является нипом, каким будет самый длинный путь? Он начнется со значения в текущем узле и продолжит либо левое, либо правое поддерево, в зависимости от того, что глубже. Таким образом, чтобы получить самый глубокий путь от узла, вычислите самый глубокий путь рекурсивно в левом и правом поддереве, возьмите с них больше времени и значение plop из текущего узла спереди.

Чтобы реализовать это таким образом, вы обнаружите, что очень удобно иметь вспомогательный предикат longer(List1, List2, LongerList), который поместит больше из List1 и List2 в LongerList.

Answer 3

Вот чистый вариант, который не требует мета-предикатов всех решений, таких как aggregate/3.

Во-первых, вот ваш образец дерево снова:

sampleTree([[[],r,[[],u,[[],t,[]]]],a,[[],c,[]]]). 

Далее is_tree/1 определяет, какие деревья выглядят как:

is_tree([]). 
is_tree([Left,_,Right]) :- 
    is_tree(Left), 
    is_tree(Right). 

Наконец, определим tree_leftmostLongestPath/2, которые мы используем для pre-order tree traversal.

По сравнению с is_tree/1, tree_leftmostLongestPath_/4 имеет 3 дополнительных аргумента:

• RPath что путь до сих пор в обратном порядок
• Best0 пара Len-Path и имеет самый длинный путь найден до сих пор
• Best также представляет собой пару Len-Path и содержит самый длинный путь всего дерева/поддерева

Вот код:

:- use_module(library(clpfd)). 

tree_leftmostLongestPath(Tree, Path) :- 
    tree_leftmostLongestPath_(Tree, [], 0-[], _-Path). 

% "internal" auxiliary predicate 
tree_leftmostLongestPath_([], RPath, Best0, Best) :- 
    Best0 = L0-_, 
    length(RPath, Len), 
    ( Len #=< L0,      Best = Best0 
    ; Len #> L0, reverse(RPath, Path), Best = Len-Path 
    ). 
tree_leftmostLongestPath_([Left,Name,Right], RPath, Best0, Best) :- 
    RPath1 = [Name|RPath], 
    tree_leftmostLongestPath_(Left , RPath1, Best0, Best1), 
    tree_leftmostLongestPath_(Right, RPath1, Best1, Best). 

Некоторые запросы и ответы:

?- sampleTree(Tree), tree_leftmostLongestPath(Tree, Path). 
Path = [a,r,u,t], Tree = [[[],r,[[],u,[[],t,[]]]],a,[[],c,[]]]). 

?- is_tree(Tree), tree_leftmostLongestPath(Tree, Path). 
    Path = []  , Tree = [] 
; Path = [A] , Tree = [[],A,[]] 
; Path = [A,B] , Tree = [[],A,[[],B,[]]] 
; Path = [A,B,C], Tree = [[],A,[[],B,[[],C,[]]]] 
…