Solved

convert  recursive(preOrder,inOrder,postOrder) binaryTree to iterative one

Posted on 2003-11-07
3
2,807 Views
Last Modified: 2007-12-19
I have to change the PreOrder, Inorder and PostOrder  from its recusive implementation to a iterative implementation. I tried doing the preOrder but it loop over the one of the roots more than once. So i need Some help doin do.
I am attaching the code I need to convert.

// BinaryTree.h
// This header file implements a template
// BinaryTree class.
//
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include <stack>
template <class T>

class BinaryTree
{
public:
  // Constructors
  BinaryTree() : _data(0), _left(0), _right(0) { }
  BinaryTree(const T& root) : _data(new T(root)), _left(0), _right(0) { }

  // Destructor
  virtual ~BinaryTree();

  // Traversal
  template <class Op> void preorder(Op op) //const
  {
     
        BinaryTree<T> *cur = this;
        while(cur){
              if(_data)
                    op(*_data);
              if(cur->_left)//{
                    op(*(cur->_left->_data));
                  //cur = cur->_left;
              if(cur->_right)//{
                    op(*(cur->_right->_data));
                  cur=cur->_right;

             
        }
           

   /*
      if (_data)
            op(*_data);
         if (_left)
            _left->preorder(op);
      if (_right)
            _right->preorder(op);
            
      */      
}

 
  template <class Op> void inorder(Op op) const
  {
      if (_left)
            _left->inorder(op);
      if (_data)
            op(*_data);
      if (_right)
            _right->inorder(op);
  }

  template <class Op> void postorder(Op op) //const
  {
        /*
        BinaryTree<T> *cur = this;
        for (;cur !=0; )
         if(cur->_left){
              op(*(cur->_left->_data));
            cur = cur->_left;
        }
        if(cur->_right){
              op(*(cur->_right->_data));
              cur = cur->_right;
        }
        if(*_data)
              op(*_data);
        */
 


      if (_left)
            _left->postorder(op);
      if (_right)
            _right->postorder(op);
      if (_data)
      op(*_data);
      
  }

  // Height
  virtual int height() const;

  // Size
  virtual int size() const;

  // Existence
  virtual bool exists(const T& value) const;

  // Insertion and Deletion
  virtual void insert(const T& value);
  virtual void remove(const T& value);

//protected:
  T* _data;
  BinaryTree<T>* _left;
  BinaryTree<T>* _right;
};

template <class T>
BinaryTree<T>::~BinaryTree()
{
  if (_data)
  {
    delete _data;
    if (_left)
      delete _left;
    if (_right)
      delete _right;
  }
}

template <class T>
int BinaryTree<T>::size() const
{
    int cnt = 0;
   
    if (_data)
    {
      ++cnt;
    }

    if (_left)
    {
      cnt += _left->size();
    }

    if (_right)
    {
      cnt += _right->size();
    }

    return cnt;
}

template <class T>
int BinaryTree<T>::height() const
{
    int ret = 0;
    int lht = 0, rht = 0;

    if (_data)
    {
      ++ret;
    }

    if (_left)
    {
      lht = _left->height();
    }

    if (_right)
    {
      rht = _right->height();
    }

    ret += (lht > rht) ? lht : rht;
    return ret;
}

template <class T>
bool BinaryTree<T>::exists(const T& value) const
{
    bool ret = false;

    if (_data)
    {
      if (*_data == value)
      {
          ret = true;
      }      
      else
      {
          if (_left)
          {
            ret = _left->exists(value);
          }
          if (_right && !ret)
          {
            ret = _right->exists(value);
          }
      }
    }
    return ret;
}

template <class T>
void BinaryTree<T>::insert(const T& value)
{
  // Implementation left as an exercise
    if(!_data)
      {
            _data = new T(value);
      }
      else if(value < *_data)
      {
            if(!_left)
                  _left = new BinaryTree<T>(value);
            else
                _left ->insert(value);
      }
      else if(value > *_data)
      {
            if(!_right)
                  _right = new BinaryTree<T>(value);
            else
                  _right->insert(value);
      }
}






template <class T>
void BinaryTree<T>::remove(const T& value)
{
  // Implementation left as an exercise
}

#endif // _BINARYTREE_H_


this is the test program:

#include "BinaryTree.h"
#include <iostream>
using namespace std;

template <class T> struct Print
{
   void operator() (const T& input) { cout <<"=>\t" << input << endl; }
};

int main()
{
   BinaryTree<int> btree(5);
   int value;
    cout << " Enter 6 value " << endl;

    for  ( int i =0; i < 6; i++){
            cin >> value;
            btree.insert(value);  
      }
   cout <<"PREORDER"<<endl;
   btree.preorder(Print<int>());
   cout << endl<< endl;
   cout <<"INORDER"<<endl;
   btree.inorder(Print<int>());
   cout << endl<< endl;
   cout <<"POSTORDER"<<endl;
   btree.postorder(Print<int>());
   return 0;
}

0
Comment
Question by:KingGrey
3 Comments
 
LVL 11

Accepted Solution

by:
bcladd earned 95 total points
ID: 9709940
I am going to talk, in general, about inorder traversal (in general only because this is homework).

Recursive inorder traversal is:

inorder (currRoot)
    if (currRoot)
         inorder(currRoot->left);
         visit(currRoot);
         inorder(currRoot->right);
 

Okay, we want to remove the  first recursive call. This is NOT a tail recursive function (tail recursion, where the only recursion is the very last thing that happens in the function, can always, easily, be replaced with iteration) so we need to do some bookkeeping to keep track of where we need to go back to. That is, the following pseudocode CANNOT work:

    if (currRoot)
        for (loopRoot = currRoot; loopRoot != NULL; loopRoot = loopRoot->left)
             ....do something....

The problem is that we want to go down to the left over and over (to the end of the "list" of left pointers), visit that node, then back up and visit the SECOND to last node (and then visit the right subtree, too). One pointer is not enough to keep all of the information. Why does recursion work? It sure looks like there is only one pointer in inorder above...Oh, yeah, that pointer is a local variable and is allocated on the calling stack so that different values are maintained in different stack frames.

This should give you a good place to get started: if you use a stack of pointers, you can simulate the activitiy of the calling stack.

If you have any specific questions, I would be happy to help.

-bcl
0
 
LVL 9

Expert Comment

by:tinchos
ID: 10242619
No comment has been added lately, so it's time to clean up this TA.
I will leave the following recommendation for this question in the Cleanup topic area:

Accept: bcladd {http:#9709940}

Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos
EE Cleanup Volunteer
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now