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 */

Saturday, September 1, 2007

[WiMAX] Fundamentals of WiMAX - (6)

We have introduced the basic idea of OFDM before. In this post, we will discuss OFDMA (Orthogonal Frequency Division Multiple Access) in Q&A style.

Q: What's the relationship between OFDM and OFDMA?
A: OFDMA can be considered as a version of OFDM optimized for multiple users. The basic idea behind OFDMA is Sub-Channelization, i.e. assigning subsets of subcarriers to different users.

Q: What's the advantage of OFDMA over OFDM?
A: We know OFDM has immuity to frequency-selective fading channel because it breaks a single high data rate stream into multiple low data rate streams, thereby the subcarrier's bandwidth is smaller than the coherence bandwidth of the channel. For a wireless system with multi users, the total system resources are shared by all users. However, in one time slot, OFDM only assigns the whole resource to only one user, i.e. one user occupies all subcarriers in one time. This makes OFDM not efficient in resource allocation. A new multiple-access technique becomes necessary. This is the purpose of OFDMA. By allowing users share subcarriers and time slots, additional flexibility can be provided by OFDMA: multi-user diversity. In addition, adpative modulation can be used in OFDMA for different users according to channel condition.

Q: How is the 'Sub-Channelization' realized?
A: In OFDMA, the sub-carriers are divided into groups of sub-carriers. Each group is called a sub-channel. The sub-carriers that form a sub-channel need not be continuous. Based on their channel conditions and QoS requirements, different sub-channels can be assigned (scheduled) to different users. This multiple access is performed before the IFFT operation, thereby the scheduling algorithm used for OFDMA is realized in both frequency and time domain.

(to be continued)