markh@csd4.csd.uwm.edu (Mark William Hopkins) (02/26/91)
anderson@mrcnext.cso.uiuc.edu writes: > I need _non-recursive_ pre, post and inorder tree traversal > algorithms. ... > Please, no algorithms which use "states" or a stack. In article <1991Feb25.074028.992@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > >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. There is such an algorithm. If you have 3 pointers on each tree-node (Left, Right, Parent), then on each traversal of a node you rotate the pointers. I think you also need the ability to compare nodes (for <, and >) too. I have a version written in FORTRAN somewhere...
kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (02/26/91)
In article <9756@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes: >anderson@mrcnext.cso.uiuc.edu writes: >> I need _non-recursive_ pre, post and inorder tree traversal >> algorithms. >> Please, no algorithms which use "states" or a stack. >There is such an algorithm. If you have 3 pointers on each tree-node (Left, >Right, Parent), then on each traversal of a node you rotate the pointers. >I think you also need the ability to compare nodes (for <, and >) too. >I have a version written in FORTRAN somewhere... Another method is to use `pointerless' trees. That is, if a node is at index `n' in a global node table, its left daughter is at 2n+1 and right daughter is at 2(n+1). It is then possible to backtrack from the leaves by going from (leaf) node k to node k/2 (its mother). A simple FSA will suffice to do the job (i.e. the `state' is encoded in the FSA state and the current node number). -kym
markh@csd4.csd.uwm.edu (Mark William Hopkins) (02/27/91)
anderson@mrcnext.cso.uiuc.edu writes: > I need _non-recursive_ pre, post and inorder tree traversal algorithms... In article <1991Feb25.074028.992@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >... you can't avoid saving _some_ state; you have to know at any node >whether you are going up or down... In article <9756@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes: > >There is such an algorithm. If you have 3 pointers on each tree-node (Left, >Right, Parent), then on each traversal of a node you rotate the pointers. > >I think you also need the ability to compare nodes (for <, and >) too. On the other hand, you only need 2 pointers, and you don't need to be able to compare pointers (as is possible only in C), IF you keep track of the number of visits to a node (during traversal) in each node. So there IS an implicit state. You still rotate the pointers (with a period of 3), and the node-state is on a Finite State machine with 3 states arranged in a cyclic fashion. All the algorithms for pre/in/post order can be merged into one just by changing which state in a node's 3-state FSA you process the information in the node at. The pointers of each leaf will be made to circularily point to the leaf in order to tie things off neatly and make the traversal clean. There is an implicit stack in the algorithm, but the tree itself is used as the stack (!). So here's a sample algorithm written in C to demonstrate this. In this sample Traverse(PRE_ORDER, P, Root), Traverse(IN_ORDER, P, Root), Traverse(POST_ORDER, P, Root) would traverse the tree, Root, carrying out the procedure, P, on each node in the order specified. /* Type definitons */ typedef struct Tree { Data Key; int Visits; struct Tree *Left, *Right; } *Tree; static Tree NewLeaf(Key) Data Key; { /* Leaf node Left/Right pointers point to the leaf itself. */ Tree Leaf; Leaf = (Tree)malloc(sizeof(struct Tree)); Leaf->Left = Leaf->Right = Leaf; Leaf->Visits = 0; Leaf->Key = Key; return Leaf; } void Insert(Key, TP) Data Key; Tree *TP; { /* Duplications on "Key"-s are allowed here */ Tree Cur, Prev; for (Prev = NULL, Cur = *TP; Prev != Cur; ) { Prev = Cur; if (Key > Cur->Key) Cur = Cur->Right; else Cur = Cur->Left; } if (*TP == NULL) *TP = NewLeaf(Key); else if (Key < Prev->Key) Prev->Left = NewLeaf(Key); else Prev->Right = NewLeaf(Key); } /* Values for Order */ #define PRE_ORDER 0 #define IN_ORDER 1 #define POST_ORDER 2 void Traverse(Order, Handler, T) int Order; void (*Handler)(); Tree T; { Tree Cur, Prev, Next; for (Prev = NULL, Cur = T; Cur != NULL; Prev = Cur, Cur = Next) { if (Cur->Visits == Order) (*Handler)(Cur->Key); Cur->Visits = (Cur->Visits + 1)%3; /* Rotate pointers */ Next = Cur->Left; Cur->Left = Cur->Right; Cur->Right = Prev; } } You can pick up demonstration source code by doing an anonymous ftp to csd4.csd.uwm.edu and obtaining the file named TreeStuff, which is in the top-level directory. It's a shell archive, so once you get it, type /bin/sh TreeStuff tp unpack it.