I had recently written a small basic program on various tree traversal methods and ways to build a tree give Pre-order,Post-order and In-order here is the complete code snippet for the same.
//----------------------------------------------------------------------------------------
int In[17] = {75,24,27,39,73,43,91,14,8,70,87,99,9,25,0,45,13}; /* In Order */
int Pre[17] = {8,14,39,24,75,27,43,73,91,45,9,87,70,99,25,0,13}; /* Pre Order */
int Post[17] = {75,27,24,73,91,43,39,14,70,99,87,0,25,9,13,45,8}; /* Post Order */
//----------------------------------------------------------------------------------------
int iLastIndex = 16;
class TreeNode
{
public:
TreeNode* pLeft;
TreeNode* pRight;
int data;
/*This variable(index) is used only while building a tree using iteration*/
int index;
};
TreeNode* pRoot=NULL;
TreeNode* makeNode()
{
TreeNode* pNode = new TreeNode();
pNode->pLeft=NULL;
pNode->pRight=NULL;
return pNode;
}
int findNewRtIndex(int data)
{
for(int i=0;i<=iLastIndex;i++)
{
if(In[i] == data )
{
return i;
}
}
}
void AddToTree(TreeNode* pParent , TreeNode* pNode)
{
if(pNode->index <= pParent->index)
{
if(pParent->pLeft!=NULL)
AddToTree(pParent->pLeft,pNode);
else
pParent->pLeft=pNode;
}
if(pNode->index > pParent->index)
{
if(pParent->pRight!=NULL)
AddToTree(pParent->pRight,pNode);
else
pParent->pRight = pNode;
}
}
/*
This function tries build a tree using the Pre-order and In-Order Traversals without Recursion.
This is a a nice function in the sense that it builds the tree based on the index instead of the actual Pre/In order traversals, It needs and additional member variable called index for the same purpose.
*/
void makeTreeWithPreAndInUsingIteration(int iEndIndex)
{
TreeNode* pNode=NULL;
pRoot = makeNode();
pRoot->data = Pre[0];
pRoot->index = findNewRtIndex(Pre[0]);
for(int i=0;i<=iEndIndex;i++)
{
int iInIndex = findNewRtIndex(Pre[i]);
pNode = makeNode();
pNode->index = iInIndex;
pNode->data = Pre[i];
AddToTree(pRoot,pNode);
}
}
/*This function tries build a tree using the Pre-order and In-Order Traversals using Recursion*/
void makeTreeWithPreAndIn(TreeNode* pNode,int iStIndex,int iEndIndex)
{
static int iCurIndex = -1;
int iNewRtIndex =-1;
if(iStIndex>iEndIndex)
return;
if(iCurIndex==-1)
{
iNewRtIndex = findNewRtIndex(Pre[0]);
iCurIndex =0;
pRoot = makeNode();
pRoot->data = Pre[0];
pNode = pRoot;
pNode->pLeft = makeNode();
pNode->pRight = makeNode();
}
else
{
iNewRtIndex = findNewRtIndex(Pre[++iCurIndex]);
pNode->data = In[iNewRtIndex];
pNode->pLeft = makeNode();
pNode->pRight = makeNode();
}
if(iStIndex==iEndIndex)
return;
makeTreeWithPreAndIn(pNode->pLeft,iStIndex,iNewRtIndex-1);
makeTreeWithPreAndIn(pNode->pRight,iNewRtIndex+1,iEndIndex);
}
/* This function tries build a tree using the Post-order and In-Order Traversals using Recursion*/
TreeNode* makeTreeWithPostAndIn(int iStIndex,int iEndIndex)
{
static int iCurIndex = -1;
TreeNode* pNode=NULL;
int iNewRtIndex =-1;
if(iStIndex>iEndIndex)
return pNode;
if(iCurIndex==-1)
{
iNewRtIndex = findNewRtIndex(Post[iLastIndex]);
iCurIndex = iLastIndex;
pRoot = makeNode();
pRoot->data = Post[iLastIndex];
pNode = pRoot;
}
else
{
iNewRtIndex = findNewRtIndex(Post[--iCurIndex]);
pNode = makeNode();
pNode->data = In[iNewRtIndex];
}
if(iStIndex==iEndIndex)
return pNode;
pNode->pRight = makeTreeWithPostAndIn(iNewRtIndex+1,iEndIndex);
pNode->pLeft = makeTreeWithPostAndIn(iStIndex,iNewRtIndex-1);
return pNode;
}
/* This function does Pre-order traversal of the tree using iteration.*/
void IterativePreOrderTraversal()
{
std::stack<TreeNode*> stck;
stck.push(pRoot);
while(!stck.empty())
{
TreeNode* pNode =(TreeNode*) stck.top();
stck.pop();
if(pNode->pRight!=NULL)
{
stck.push(pNode->pRight);
}
if(pNode->pLeft!=NULL)
{
stck.push(pNode->pLeft);
}
cout<<pNode->data<<endl;
}
}
/* This function does Post-order traversal of the tree using iteration.*/
void IterativePostOrderTraversal()
{
std::stack<TreeNode*> stck;
stck.push(pRoot);
while(!stck.empty())
{
TreeNode* pNode =(TreeNode*) stck.top();
stck.pop();
if(pNode->pLeft!=NULL)
{
stck.push(pNode->pLeft);
}
if(pNode->pRight!=NULL)
{
stck.push(pNode->pRight);
}
cout<<pNode->data<<endl;
}
}
/* This function does In-order traversal of the tree using iteration.*/
void IterativeInOrderTraversal()
{
std::stack<TreeNode*>stck;
stck.push(pRoot);
TreeNode* pNode = pRoot;
while(!stck.empty())
{
if(pNode!=NULL)
{
stck.push(pNode);
pNode = pNode->pLeft;
continue;
}
else
{
if(!stck.empty())
{
pNode = (TreeNode*) stck.top();
stck.pop();
if(!stck.empty())
{
cout<<pNode->data<<endl;
pNode = (TreeNode*)pNode->pRight;
}
else
break;
}
else
break;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//makeTreeWithPreAndIn(NULL,0,16);
cout<<"-------------------------------------------"<<endl;
//makeTreeWithPostAndIn(NULL,0,16);
pRoot = makeTreeWithPostAndIn(0,16);
cout<<"-------------------------------------------"<<endl;
//makeTreeWithPreAndInUsingIteration(16);
cout<<"-------------------------------------------"<<endl;
IterativePreOrderTraversal();
cout<<"-------------------------------------------"<<endl;
IterativePostOrderTraversal();
cout<<"-------------------------------------------"<<endl;
IterativeInOrderTraversal();
cout<<"-------------------------------------------"<<endl;
return 0;
}
No comments:
Post a Comment