Tree traversal

ramthegreatcv Fri Jun 05, 2009 3:54 am

different Types of Tree Traversals

ramthegreatcv Fri Jun 05, 2009 3:55 am

Code:: void inOrderRec(node* n){ if(n != NULL){ inOrderRec(n->lChild); cout<<n->data; inOrderRec(n->rChild); } } void preOrderRec(node* n){ if(n != NULL){ cout<<n->data; preOrderRec(n->lChild); preOrderRec(n->rChild); } } void postOrderRec(node* n){ if(n != NULL){ postOrderRec(n->lChild); postOrderRec(n->rChild); cout<<n->data; } }

ramthegreatcv Fri Jun 05, 2009 3:56 am

Code:: void inOrderItr(node* n){ if(n == NULL) return; node* temp; stack<node*> s; while(true){ while(n){ s.push(n); n = n->lChild; } if(! s.empty()){ n = s.top(); s.pop(); } else break; cout<<n->data; n = n->rChild; } return; }

ramthegreatcv Fri Jun 05, 2009 3:57 am

Code:: void postOrderItr(node* n){ /* Suppose we push a NULL on the stack after a pointer to a node whose subtrees have both been explored. When we pop the stack and find a NULL pointer, we'll know that the next pointer we pop represents a subtree that has been fully traversed; it's value should be printed. Here's a possible implementation: */ stack<node *> s; while ( n != NULL || !s.empty() ) { for (; n != NULL; n = n->lChild ) s.push( n ); if ( s.top() != NULL ) { n = s.top()->rChild; s.push( NULL ); } else { s.pop(); cout << s.top()->data; s.pop(); n = NULL; } } return; }

ramthegreatcv Fri Jun 05, 2009 3:58 am

Code:: void preOrderItr(node* n){ if(n == NULL) return; node* temp; stack<node*> s; s.push(n); while(! s.empty() ){ temp = s.top(); s.pop(); cout<<temp->data; if(temp->rChild != NULL) s.push(temp->rChild); if(temp->lChild != NULL) s.push(temp->lChild); } return; }

Sponsored content

Recursive: Simple and must know