Monday, September 10, 2007

[Code] Non-recursive pre-order traversal of a tree

Traversal of a tree data structure often uses recursive algorithm. Without recursion, how to solve the problem? Here is the demo code I programmed in C.









001 #include <iostream>
002 using namespace std;
003 /** 
004   Definition of NODE of the TREE 
005 */
006 typedef struct NodeT
007 {
008   struct NodeT *left;
009   struct NodeT *right;
010   char data;
011 }NODE;
012 /**
013   Definition of Element of the STACK
014 */
015 typedef struct ElementS
016 {
017   struct ElementS *next;
018   NODE *data;
019 }ELEMENT;
020 /** 
021   recursive version of Pre-order traversal
022   void PreOrder(NODE * root)
023   Algorithm:
024     Print out the ROOT's value
025   Do a pre-order traversal on the LEFT sub-tree of the ROOT node
026   Do a pre-order traversal on the RIGHT sub-tree of the ROOT node
027 */
028 void PreOrder(NODE * root)
029 {
030   if (root)
031   {
032     cout << root->data << "->" ;
033     PreOrder(root->left);
034     PreOrder(root->right);
035   }
036   else
037     return;
038 }
039 /** 
040    non-recursive version of Pre-order traversal
041    void PreOrderNonRecur(NODE *root)
042    Algorithm:   
043    create a stack
044      PUSH the root node of the tree into the stack
045      While the stack is not empty
046      POP a node
047      If the node is not NULL
048        Print the value of the node
049      PUSH the node's right child into the stack
050      PUSH the node's left child into the stack
051 */
052 bool CreateStack(ELEMENT **stack)
053 {
054   *stack=NULL;
055   return true;
056 }
057 bool DeleteStack(ELEMENT **stack)
058 {
059   ELEMENT *next;
060   while(*stack)
061   {
062     next=(*stack)->next;
063     delete *stack;
064     *stack=next;
065   }
066   return true;
067 }
068 bool Push(ELEMENT **stack, NODE *data)
069 {
070   ELEMENT *p = new ELEMENT;
071   if(!preturn false;
072   p->data = data;
073   p->next = *stack;
074   *stack=p;
075   return true;
076 }
077 bool Pop(ELEMENT **stack, NODE **data)
078 {
079   ELEMENT *p;
080   p=*stack;
081   if(!preturn false;
082   *data = p->data;
083   *stack= p->next;
084   delete p;
085   return true;
086 }
087 void PreOrderNonRecur(NODE *root)
088 {
089   ELEMENT *theStack;
090   NODE *data;
091   NODE *curNode;
092 
093   CreateStack(&theStack);
094   Push(&theStack, root);
095 
096   while(Pop(&theStack, &data))
097   {
098     curNode = data;
099     if(curNode)
100     {
101       cout<<curNode->data<<"->";
102       Push(&theStack, curNode->right);
103       Push(&theStack, curNode->left);
104     }
105   }
106   DeleteStack(&theStack);
107 }
108 void main()
109 {
110   NODE a,b,c,d,e,f,g;
111   /** 
112     manually construct the tree
113   */
114   a.left=&b;
115   a.right=&c;  
116   b.left=NULL;
117   b.right=&d;
118   c.left=&e;
119   c.right=&f;
120   d.left=&g;
121   d.right=NULL;
122   e.left=NULL;
123   e.right=NULL;
124   f.left=NULL;
125   f.right=NULL;
126   g.left=NULL;
127   g.right=NULL;
128   a.data='a';
129   b.data='b';
130   c.data='c';
131   d.data='d';
132   e.data='e';
133   f.data='f';
134   g.data='g';
135 
136   cout<<"Recursive pre-order traversal of the tree: "<<endl;
137   PreOrder(&a);
138   cout<<"End of traversal";
139   cout<<endl;
140 
141   cout<<"Non-recursive pre-order traversal of the tree: "<<endl;
142   PreOrderNonRecur(&a);
143   cout<<"End of traversal";
144   cout << endl;
145 }
146 /**
147   the output should be
148   a->b->d->g->c->e->f->END
149 */

1 comment:

Anonymous said...

Howdy,

When ever I surf on web I come to this website[url=http://www.weightrapidloss.com/lose-10-pounds-in-2-weeks-quick-weight-loss-tips].[/url]Lots of good information here jinghaoxu.blogspot.com. Frankly speaking we really do not pay attention towards our health. Are you really serious about your weight?. Recent Research displays that closely 60% of all U.S. adults are either obese or overweight[url=http://www.weightrapidloss.com/lose-10-pounds-in-2-weeks-quick-weight-loss-tips].[/url] Therefore if you're one of these citizens, you're not alone. In fact, most of us need to lose a few pounds once in a while to get sexy and perfect six pack abs. Now the question is how you are planning to have quick weight loss? Quick weight loss can be achived with little effort. If you improve some of your daily diet habbits then, its like piece of cake to quickly lose weight.

About me: I am webmaster of [url=http://www.weightrapidloss.com/lose-10-pounds-in-2-weeks-quick-weight-loss-tips]Quick weight loss tips[/url]. I am also health trainer who can help you lose weight quickly. If you do not want to go under difficult training program than you may also try [url=http://www.weightrapidloss.com/acai-berry-for-quick-weight-loss]Acai Berry[/url] or [url=http://www.weightrapidloss.com/colon-cleanse-for-weight-loss]Colon Cleansing[/url] for fast weight loss.