Prolog - 在二叉树中找到一个共同的祖先

Question

假设你有一个二叉搜索树：

t (73， t (31， t(5，nil，nil(， nil(， t (101， t (83， nil， t(97，nil，nil((， t(200，nil，nil

(((即：

73
/     
31     101
/      /   
5      83  200
/
97

我需要编写一个谓词子树 (X1，X2，T(，它将从树(X1 和 X2(中获取 2 个值并为其找到最小的公共父级，并将其子树存储在 T 中。

所以对于上面的例子，如果我查询：子树(83,200，X(。

我应该回来了：

t(101，t(83，nil，t(97，nil，nil((，t(200，nil，nil(( 即：

101
/   
83  200
/
97

由于 101 是我两个数字的最小公共值，因此我取回了该子树。我该怎么做？

谢谢！

Answer 1

这是我针对此问题的代码。只需致电

tree(X),common_ancestor(83,200,X,Y)

你会在Y中得到答案。

tree3(X) :- X = t (73, t (31, t(5,nil,nil), nil), t (101, t (83, nil, t(97,nil,nil)), t(200,nil,nil))).
% Chech membership in tree:
in(X, t(X, _, _)).
in(X, t(_, L, _)):-
in(X, L).
in(X, t(_, _, R)):-
in(X, R).
% Getting subtree given the value of root 
get_subtree(X, t(X, L, R),Res) :- Res = t(X,L,R).
get_subtree(X, t(_, L, _),Res):-
get_subtree(X, L,Res).
get_subtree(X, t(_, _, R),Res):-
get_subtree(X, R,Res).
% least_common_ancestor(N1, N2, Tree, Res) assignes the value of the least common ancestor to Res.
% Note that it's assumed all nodes have different values.
% Base cases: when one value is the parent of the other, then the parent is the LCA:
least_common_ancestor(N1, N2, t(N1, L, R), N1):-
(in(N2, L) ; in(N2, R)), !.
least_common_ancestor(N1, N2, t(N2, L, R), N2):-
(in(N1, L) ; in(N1, R)), !.
% If one is in the left (right) subtree and the other is in the right (left) subtree then the current root is the LCA
least_common_ancestor(N1, N2, t(X, L, R), Res):-
((in(N1, L), in(N2, R)) ; (in(N1, R), in(N2, L))), !,
Res = X.
% Otherwise, recurse to both subtrees:
least_common_ancestor(N1, N2, t(_, L, _), Res):-
least_common_ancestor(N1, N2, L, Res), !. 
least_common_ancestor(N1, N2, t(_, _, R), Res):-
least_common_ancestor(N1, N2, R, Res).

% The main function
commonGP(Ka,Kb,T,ST) :-
least_common_ancestor(Ka,Kb,T,Res), get_subtree(Res,T,ST).