Re: iterative copying of binary expression trees

Jean Guillaume Pyraksos <wissme@xxxxxxxxxxx> writes:

Pascal, I don't understand your reply. I want to find a one-phase algorithm
to solve this problem of copying in a functional iterative way a binary tree.
I have already a two-phase algorithm.
I'm just asking : does anyone know a one-phase algorithm ?
I'm not a student, I'm trying to get my program done in the best way...

Well, I would think that the best way would be to use a recursive
algorithm.

Tree walkers belong to a class of functions that are fundamentally
recursive. The class of recursive functions is larger than the class of
iterative functions, so you can't really have a purely iterative
solution to this problem. At best you can not use the built-in
recursion and instead implement it yourself by maintaining a stack or
queue of pending operations that you will need to execute.

Since a tree walker is fundamentally a recursive function, you can't
have a proper tail-recursive version. Simply because the algorithm
requires doing things via multiple recursion along different branches of
the tree walk. Again, you could probably disguise it, but any such
solution will be a lot more convoluted than a straight-forward recursive
solution.

Why are you interested in an iterative solution?

--
Thomas A. Russ, USC/Information Sciences Institute
.

Relevant Pages

  • Re: PreOrder Tree Traversal
    ... If your not going through a class, try the wikipedia entries on tree ... Normally recursive means the algorithm calls itself. ... don't use recursion.", had me wondering for some time. ... You can't use recursion with iterator because you have ...
    (comp.lang.java.help)
  • Re: coerce for arbitrary types
    ... the algorithm itself is essentially last-in first-out, ... via some sort of recursion? ... WaitStack <= new stack containing topnode ... As nested lists, there's only one number in a proper position. ...
    (comp.lang.lisp)
  • Re: coerce for arbitrary types
    ... algorithm that Cormen, Leiserson, and Rivest use in their DFS. ... inherently first-in first-out, like a queue, not at all stack-like ... experience, once you get over the hurdle of recursion, ... *intention* is nested lists, *not* arbitrary CONS trees. ...
    (comp.lang.lisp)
  • LOS Optimization Using Binary Tree Structures (with demo)
    ... fast way to calculate LOS using a binary tree (properly called a binary ... describe the visibility-dependency between tiles - as in describing ... Using octants ... The cool thing about using a relational-based LOS algorithm is that you ...
    (rec.games.roguelike.development)
  • Meaning of in-place; was fast stable sort
    ... view is that the "in-place" should refer only to the data element ... Recursion should be an additional qualifier, ... Thus your sorting algorithm that uses indices would be in-place ... The distinction is significant because ...
    (comp.programming)