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

问题描述

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

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 中。

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

我应该回来了：

t(101,t(83,nil,t(97,nil,nil)),t(200,nil,nil)) 即：

由于 101 是我的两个数字的最小公共值，我得到了那个子树。我怎么能那样做？

谢谢！

标签： prologbinary-tree

这是我解决这个问题的代码。打电话

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).

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

问题描述

解决方案

推荐阅读