CODEWITHSUNDEEP
recursiontreeprologbinary-tree
Aceconhielo
Aceconhielo

Reputation: 3636

Prolog. Reverse nodes in a tree

I want to reverse the nodes in a binary tree like this :

[[ [ [[],1,[]], 5, []],
   7,
   [ [], 3, [[],4,[]]]],
 6,
 [ [ [], 10, []],
   8,
   [ [[],9,[]], 11, [[],2,[]]]]]

enter image description here

I can only use this ABN representation as lists and the following constructors and selectors of the abstract data type.

empty([]).
root([_,N,_], N).
hi([HI,_,_],HI).     %left son 
hd([_,_,HD],HD).     %right son
maketree(R,HI,HD,[HI,R,HD]).

I want to know how could I make a swap predicate like this swap(A4,B). that working like this:

?- swap(A4,B).
B=[[[[[],2,[]],11,[[],9,[]]],8,[[],10,[]]],6,[[[[],4,[]],3,[]],7,[[],5,[[],1,[]]]]]

Thanks !

Upvotes: 0

Views: 655

Answers (1)

Will Ness
Will Ness

Reputation: 71065

For an abstract data type, you can treat your interface predicates as opaque:

% empty([]).
% root(Tree, Root).
left_child(Tree,Left):- hi(Tree,Left).  
right_child(Tree,Right):- hd(Tree,Right).  
mktree(Top,Left,Right,Tree):- maketree(Top,Left,Right,Tree).

To swap two nodes in a tree, just

swapped_tree(Tree, SwappedTree):-
    left_child(Tree, Left ),
    right_child(Tree, Right ),
    root(Tree, Root ),
    % and then combine them in a simple way,
    mktree( ..., ..., ..., SwappedTree).

It is in Prolog just like it is in English.

But the nodes there stayed the same. To have the new tree to be the full mirror of the original, you'll want to treat the child nodes too in the same way as you do the whole tree, before creating the new, mirrored tree:

mirrored_tree(Tree, MirroredTree) :-
    .... ,
    .... ,
    .... ,
    mirrored_tree( ..., ... ),
    mirrored_tree( ..., ... ),
    .... .

Using the predicate you are still writing (as if it were already written) to solve sub-parts of the full problem which are of the same nature as the full problem, and recombining the results in some simple way to get the solution of the full problem, is the essence of recursion.

Upvotes: 2

Related Questions