treeMerge в swi-прологе

Question

Я пытаюсь построить предикат treeMerge(A,B,C), который возвращает true, если C является результатом слияния двух деревьев A и B. Есть предложения о том, как я могу это реализовать? У меня есть грубая идея, я думаю о слиянии корня, потом первого потомка, потом второго и так далее, но я довольно плохо знаком с прологом.

Answer 1

Идея состоит в том, чтобы получить список узлов внутри дерева, а затем добавить каждый узел в другое дерево. Я разработал предикат merge/3 который объединяет два дерева в качестве входных данных в третьем дереве (вставьте все узлы первого дерева во второе). Дерево представлено в виде t(Node,Left,Right), Вот код:

getNodes(nil,[]).
getNodes(t(E,L,R),[E|S]) :- 
    append(SL,SR,S), 
    getNodes(L,SL), 
    getNodes(R,SR),!.

insert(Node,nil,t(Node,nil,nil)).
insert(Node,t(El,Left,Right),t(El,L,R)):-
    (Node > El ->  
        insert(Node,Right,R),
        L = Left
    ; insert(Node,Left,L),
        R = Right).

insertNodesList([],T,T).
insertNodesList([H|T],Tree,M):-
    insert(H,Tree,T1),
    insertNodesList(T,T1,M).

merge(T1,T2,Merged):-
    getNodes(T1,LNodesT1),
    insertNodesList(LNodesT1,T2,Merged).

Запрос:

?-merge(t(3,t(2,t(1,nil,nil),nil),t(4,nil,t(7,nil,t(5,nil,nil)))),t(3,t(2,nil,nil),t(4,nil,t(7,nil,t(5,nil,nil)))),T).
T = t(3, t(2, t(2, t(1, nil, nil), nil), t(3, nil, nil)), t(4, t(4, nil, nil), t(7, t(7, t(5, nil, nil), nil), t(5, nil, nil))))