dewolfe@ug.cs.dal.ca (Colin DeWolfe) (02/25/91)
In article <anderson.667437145@mrcnext> 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. > I hate to do it, but ME TOO!!! I need one with parent, leftmost-child, and right AND left sibling pointers... as above, no states or stack... >Thanks, >-Beej Hey Beej, I wonder if were doing the same project? -- Colin (Clone) DeWolfe dewolfe@ug.cs.dal.ca
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (02/25/91)
anderson@mrcnext.cso.uiuc.edu writes: > I need _non-recursive_ pre, post and inorder tree traversal > algorithms. After a bit of thinking, at least part of this is possible, which surely means that with more thinking, all of it should be possible. > The trees are implemented with leftmost-child, right-sibling and > parent pointers. As long as your logic can treat it as if it were a bushy tree, that should not be a problem. > Please, no algorithms which use "states" or a stack. Well, you can't avoid saving _some_ state; you have to know at any node whether your are going up or down, for example, , but you can avoid saving O(log(N)) state; you can get by with O(1) state. I don't have the algorithm to hand you, but here is the basis on which such a thing can be done: use the equivalent of the maze solver's "right hand rule" and traverse your (logical) tree as if it were a maze of narrow hallways. You need merely to know if you are going up or down, note if you have reached a leaf going down or a node of order >1 going up that it is time to go the other way, and the third obvioous item of state is that if you return to the root and there is no next (rightward) path, then you are done. By the way, this is a question independent of the Amiga, and this kind of request is best directed to comp.theory, where it is typical, though a little low level, of the questions there. Followups to this posting will go there. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
andreess@mrlaxs.mrl.uiuc.edu (Marc Andreessen) (02/26/91)
In article <anderson.667437145@mrcnext> 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
231b3678@fergvax.unl.edu (Phil Dietz) (02/26/91)
In article <1991Feb26.045024.6487@ux1.cso.uiuc.edu> andreess@mrlaxs.mrl.uiuc.edu (Marc Andreessen) writes: >In article <anderson.667437145@mrcnext> 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
martens@junk.cis.ohio-state.edu (Jeff Martens) (02/27/91)
In article <1991Feb26.045024.6487@ux1.cso.uiuc.edu> andreess@mrlaxs.mrl.uiuc.edu (Marc Andreessen) writes: %In article <anderson.667437145@mrcnext> 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... I certainly hope someone brings this to the attention of the original slimeball poster's instructor, or at least reposts the original request on a UIUC CS newsgroup, assuming they have such a thing. -- -- Jeff (martens@cis.ohio-state.edu) Scissors cut paper, rock breaks scissors, and guy stuff beats girl stuff.