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 <1991Feb25.074028.992@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > 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." If the class's professor happens to be reading this newsgroup, the student in question is cs225cz, aka Brent J. Anderson, who has since posted a question to our internal CS225 notesfile inquiring as to the legality of a variable maintaining current up/down traversal state in an attempt to cash in on Kent's pseudo-algorithm. Marc -- Marc Andreessen___________University of Illinois Materials Research Laboratory Internet: andreessen@uimrl7.mrl.uiuc.edu____________Bitnet: andreessen@uiucmrl