Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: Re: Non-recursive tree traversal (was: Re: tree traversal)
Keywords: non-recursive tree traversal algorithm needed
Message-ID: <9780@uwm.edu>
Date: 27 Feb 91 01:32:42 GMT
References: <anderson.667437145@mrcnext> <1991Feb25.074028.992@zorch.SF-Bay.ORG> <9756@uwm.edu>
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 96

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.


Brought to you by Super Global Mega Corp .com