Reverse nodes in a binary tree

[Juan]

Hi !

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

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

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,[]]]]]

Any clues ?

Thanks

[Kuniaki Mukai]

Your problem sounds to me like this:

given binary tree
=> flatten the right most branch
=> reverse the flatten list
=> make it a binary tree

For example.
t(a,t(b, t(c)) =>
=> [a, b, c]
=> [c, b, a]
=> t(c, t(b, t(a))

Am I missing something ? Anyway, I hope this help.

Kuniaki Mukai

> On Jun 3, 2017, at 17:45, Juan <juaan...@gmail.com> wrote:
>
> Hi !
>
> I want to know how to reverse the nodes in a binary tree like this :
>
> [[[[[],1,[]],5,[]],
> 7,
> [[],3,[[],4,[]]]],
> 6,
> [[[],10,[]],
> 8,
> [[[],9,[]],11,[[],2,[]]]]]
>
>

> 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,[]]]]]
>
> Any clues ?
>
> Thanks
>

> --
> You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

[Boris Vassilev]

Hello Juan, Kuniaki,

I must be misunderstanding the question, because it seems this predicate does what you show, but not what you ask:

==
tree_mirror([], []). % the empty tree
tree_mirror([L, X, R], [Rm, X, Lm]) :- % swap the mirrored children
    tree_mirror(L, Lm), % mirror the left...
    tree_mirror(R, Rm). % ... and the right child
==

==
?- tree_mirror(

    [[[[[],1,[]],5,[]],
    7,
    [[],3,[[],4,[]]]],
    6,
    [[[],10,[]],
    8,

    [[[],9,[]],11,[[],2,[]]]]],
    R).
R = [[[[[], 2, []], 11, [[], 9, []]], 8, [[], 10, []]], 6, [[[[], 4, []], 3, []], 7, [[], 5, [[], 1, []]]]].
==

So at least I get what you seem to be after. I don't know if this is "reversing", I'd call it "mirroring". For reversing you need an order, so I guess in-order traversal? See Kuniaki's suggeston for a more general solution, however: if you are making a balanced binary tree from the reversed flattened list, as he suggested, you will **not** just mirror the tree in the general case. Rather, you will get a balanced tree that will have the nodes in reverse, if you do in-order traversal. I think doing this might be more useful than just "mirroring".

I also don't know how to use the "constructors and selectors of the abstract data type" without making the definition look clumsy :-(

Hope that helps more than it confuses,

Boris

Save our in-boxes! http://emailcharter.org

> To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.