[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
Solved

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

Posted on 2003-11-07
Medium Priority
2,827 Views
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
Question by:KingGrey
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 11

Accepted Solution

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

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:

Tinchos
EE Cleanup Volunteer
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and â€¦
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationâ€¦
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month12 days, 23 hours left to enroll