On Mon, May 19, 2008 at 11:56:17AM +0200, Zoltan Boszormenyi wrote: > >From an implementation point of view, the only difference between > >breadth-first and depth-first is that your tuplestore needs to be LIFO > >instead of FIFO. > > Are you sure? I think a LIFO tuplestore would simply return reversed > breadth-first order. Depth-first means for every new record descend into > another recursion first then continue with the next record on the right.
Say your tree looks like: Root->A, D A->B,C D->E,F LIFO pushes A and D. It then pops A and pushes B and C. B and C have no children and are returned. Then D is popped and E and F pushed. So the returned order is: A,B,C,D,E,F. You could also do B,C,A,E,F,D if you wanted. FIFO pushes A and D. It then pops A and puts B and C at *the end*. It then pops D and pushes E and F at the end. So you get the order A,D,B,C,E,F Hope this helps, -- Martijn van Oosterhout <[EMAIL PROTECTED]> http://svana.org/kleptog/ > Please line up in a tree and maintain the heap invariant while > boarding. Thank you for flying nlogn airlines.
signature.asc
Description: Digital signature
