Loading ...
Sorry, an error occurred while loading the content.

Re: Combining two criticisms (was: Re: [hackers-il] Question to graph theorists - non-recursive binary tree traversal algorithm?)

Expand Messages
  • Omer Zak
    ... How about that what-is-its-name transformation, which establishes an equivalence relationship between general and binary trees? Then you need to deal only
    Message 1 of 12 , Aug 25, 2005
    • 0 Attachment
      On Fri, 2005-08-26 at 02:13 +0300, guy keren wrote:

      > aha, but you are forgetting that you do not have an upper-bound on the
      > number of children for a given node. consider this:
      >
      >
      > [ P ]
      >
      >
      > [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]
      >
      >
      > lets say we were in C2, and are now returning to P. we now need to find
      > which is the next node we should visit. the only way to make this in O(1),
      > is that each node will keep a link to its sibling. add these links too,
      > then. (if this operation is not O(1), it makes your scanning algorithm
      > less efficient then O(N)).

      How about that what-is-its-name transformation, which establishes an
      equivalence relationship between general and binary trees?

      Then you need to deal only with two children per node.

      > if you'll want to scan the tree in reverse order, you'll need the siblings
      > list to be bidirectional.
      >
      > if you'll want to make a BFS scan, rather then DFS.....
      >
      > so, you see, you're creating a tree that lends itself to one manner of
      > traversal, and does not work for other types of traversals.
      >
      > this could be useful for specific types of problems, ofcourse, but this is
      > not the generic issue of traversing a tree structure.

      OK, I give up.
      I propose a bicycle as a transportation vehicle, pointing out that it is
      the best solution for some specialized transportation situations.
      You reply by reminding us that most of the transportation needs of
      humans are better served by cars and airplanes.

      > if you can't bring up something useful - it's better to keep the list
      > quiet. would you like me to bring up my mission-imposible project of
      > devising an algorithm that automatically translates C programs into C++
      > programs while introducing classes based on usage relations between data
      > and functions in the original C program?

      Sounds cool and interesting. Can you tell us more about it?
      How do you avoid the trivial solution of enclosing function declarations
      by extern "C" { ... } declarations?
      --- Omer
      --
      Every good master plan involves building a time machine. Moshe Zadka
      My own blog is at http://www.livejournal.com/users/tddpirate/

      My opinions, as expressed in this E-mail message, are mine alone.
      They do not represent the official policy of any organization with which
      I may be affiliated in any way.
      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
    Your message has been successfully submitted and would be delivered to recipients shortly.