Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!maverick.ksu.ksu.edu!hoss!fergvax!231b3678 From: 231b3678@fergvax.unl.edu (Phil Dietz) Newsgroups: comp.sys.amiga.programmer Subject: Re: tree traversal Keywords: non-recursive tree traversal algorithm needed Message-ID: <1991Feb26.063024.6408@hoss.unl.edu> Date: 26 Feb 91 06:30:24 GMT References: <1991Feb26.045024.6487@ux1.cso.uiuc.edu> Sender: news@hoss.unl.edu (Network News Administer) Organization: Comp Sci and Engr, Univ. of Nebr. Lines: 55 In article <1991Feb26.045024.6487@ux1.cso.uiuc.edu> andreess@mrlaxs.mrl.uiuc.edu (Marc Andreessen) writes: >In article anderson@mrcnext.cso.uiuc.edu writes: >>I need _non-recursive_ pre, post and inorder tree traversal algorithms. >> >>The trees are implemented with leftmost-child, right-sibling and parent >>pointers. >> >>Please, no algorithms which use "states" or a stack. > >This is a blatant attempt by a student in CS225 here at UIUC >to farm out his homework to the net. The question given in class >(and due 26 Feb) is 3.19 from _Data Structures and Algorithms_ >(Aho, Hopcraft, Ullman): > >"Suppose trees are implemented by leftmost-child, right-sibling, >and parent pointers. Give nonrecursive preorder, postorder, and >inorder traversal algorithms that do not use 'states' or a stack." > >Thought you'd like to know... > >Marc > >-- >Marc Andreessen___________University of Illinois Materials Research Laboratory >Internet: andreessen@uimrl7.mrl.uiuc.edu____________Bitnet: andreessen@uiucmrl The secret is to use HEAPED trees (trees that are very even). Whenever you add a new node, you'll have to re-heap the mother to keep everything in order. You will also want to keep track of the levels of the tree (VIA a counter or using log2(n) dealer).... Printing it out shouldn't be that hard now that it's symetrical. One idea you have to keep in mind is that the left half of the tree will be full and the right half will only part time. Here is a sample people greg scott bob fred randy tim alan dick note the empty (or NULLED) children on the bottom level. Make sure you check for them. This will be the hardest part. ~~~~~~~~~ Take it from a CS student, if you want the source code to a routine, go to the library! Most CS programs are derived directly or indirectly from example pograms from FORMER texts! :-) Phil Dietz --- Nothing but the best; Phil Dietz Panic Zone, Howard Stern, 231b3678@fergvax.unl.edu an Amiga, and a couple a babes. Univ. of Nebraska