I recently started learning binary tree. Following is the code for a typical node for a tree (no code review required for that):
typedef unsigned int uint;
template<typename T>
class BinaryNode
{
T t_Data;
BinaryNode *pt_Left, *pt_Right;
public:
BinaryNode (const T &data) : t_Data(data), pt_Left(0), pt_Right(0) {}
void Insert (const T &data)
{
if(this->t_Data == data)
return;
BinaryNode<T> *&pNode = (data < this->t_Data)? this->pt_Left : this->pt_Right;
if(pNode == 0) pNode = new BinaryNode<T>(data);
else pNode->Insert(data);
}
template<uint SIZE>
static
BinaryNode<T>* GenerateTree (const T (&arr)[SIZE])
{
return GenerateTree(arr, SIZE);
}
static
BinaryNode<T>* GenerateTree (const T *arr, const uint SIZE)
{
BinaryNode<T> *pHead = new BinaryNode<T>(arr[0]);
for(uint i = 0; i < SIZE; i++)
pHead->Insert(arr[i]);
return pHead;
}
operator const T& () const { return t_Data; }
BinaryNode* const getLeft () const { return pt_Left; }
BinaryNode* const getRight () const { return pt_Right; }
};
For example to populate this tree with char
nodes, one need to call the Generate
function as,
const char letters[] = {'F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'I', 'H'};
BinaryNode<char> *pHead = BinaryNode<char>::GenerateTree(letters);
Question:
I wanted to implement, its pre-order, in-order, post-order traversals in recursive as iterative manner. We pass a traversing vector<> vTraversal
to all functions to populate the traversal results.
Recursive is very simple:
template<typename T>
void PreOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
if(pNode == 0)
return;
vTraverse.push_back(*pNode);
PreOrderRecursive(pNode->getLeft(), vTraverse);
PreOrderRecursive(pNode->getRight(), vTraverse);
}
template<typename T>
void InOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
if(pNode == 0)
return;
InOrderRecursive(pNode->getLeft(), vTraverse);
vTraverse.push_back(*pNode);
InOrderRecursive(pNode->getRight(), vTraverse);
}
template<typename T>
void PostOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
if(pNode == 0)
return;
PostOrderRecursive(pNode->getLeft(), vTraverse);
PostOrderRecursive(pNode->getRight(), vTraverse);
vTraverse.push_back(*pNode);
}
You can see the recursive functions are easily understandable and can relate to each other.
However, in iterative functions, I have a problem. I am able to find a good solution for pre-order traversal, a little complex solution for in-order traversal and no elegant solution for post-order traversal:
template<typename T>
void PreOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
vector<const BinaryNode<T>*> record;
record.push_back(pNode);
while(record.size() != 0)
{
const BinaryNode<T> *pN = record.back();
record.pop_back();
if(pN == 0)
continue;
record.push_back(pN->getRight());
record.push_back(pN->getLeft());
vTraversal.push_back(*pN);
}
}
template<typename T>
void InOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
vector<const BinaryNode<T>*> record;
record.push_back(pNode);
while(true)
{
const BinaryNode<T> *pN = record.back();
record.pop_back();
if(pN == 0)
{
if(record.size() == 0)
break;
vTraversal.push_back(*record.back());
record.pop_back();
continue;
}
record.push_back(pN->getRight());
record.push_back(pN);
record.push_back(pN->getLeft());
}
}
template<typename T>
void PostOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
// :(
}
Is there a way by which I can make all 3 iterative solution relating to each other in the same way as recursive traversal ?