/******************************************************************************
-------------------------------------------------------------------------------
If ihis file works as expected, it is created
by Prateek Kumar Dubey (dubeyprateek@gamil.com),
otherwise, I dont know who has written this !
-------------------------------------------------------------------------------
_______________________________________________________________________________
Discription
_______________________________________________________________________________
Filename :: Tree.h
Supporting Files ::
1 - Node.h
2 - LinkList.h
3 - ListNode.h
Purpose ::
This header file declares and defines a Binary Search Tree(BST)
template class CTree. using this template tree of any object or
of basic data type can be created.
Precautions ::
While creating tree of any user defined class object one must
over load '==', '=', '<' and '>' operators, in the class.
Example ::
CTree<int> objCTreeInt ; //creating an instance of class
CTree<float> objCTreeFloat ;
CTree<MyClass> objCTreeMyClass ;
Now use various methods of CTree for further processings.
Methods ::
Public ::
1 - bool AddRoot(T & );
2 - bool Insert(T & );
3 - bool Delete(T & );
4 - bool Search(T & );
5 - bool Minimum(T &, T & );
6 - bool Maximum(T &, T & );
7 - bool Successor(T &, T & );
8 - bool Predecessor(T &, T & );
9 - bool Parent(T &, T &) ;
10 - bool Left(T &, T &) ;
11 - bool Right(T &, T &) ;
12 - bool TreeInorderWalk(T & ) ;
13 - bool TreePreorderWalk(T & ) ;
14 - bool TreePostorderWalk(T & ) ;
15 - bool DeleteTree(T & ) ;
16 - bool Delete(CNode<T>* pNode );
17 - bool Search(T &obj, CNode<T> **pOut);
18 - bool Minimum(CNode<T>* , CNode<T>** );
19 - bool Maximum(CNode<T>* , CNode<T>** );
20 - bool Successor(CNode<T>* , CNode<T>** );
21 - bool Predecessor(CNode<T>* , CNode<T>** );
22 - CNode<T>* Parent(CNode<T>** pNode)
23 - CNode<T>* Left(CNode<T>** pNode)
24 - CNode<T>* Right(CNode<T>** pNode)
25 - bool TreeInorderWalk(CNode<T>*) ;
26 - bool TreePreorderWalk(CNode<T>*) ;
27 - bool TreePostorderWalk(CNode<T>*) ;
28 - bool DeleteTree(CNode<T>*) ;
Private::
1 - bool InorderTreeWalk(CNode<T>*) ;
2 - bool PreorderTreeWalk(CNode<T>*) ;
3 - bool PostorderTreeWalk(CNode<T>*) ;
4 - bool InorderTreeWalk(T & ) ;
5 - bool PreorderTreeWalk(T & ) ;
6 - bool PostorderTreeWalk(T & ) ;
Member Variables ::
public ::
1 - CLinkList<T> *m_pListInorder ;
Pointer to the link list prepared by calling
TreeInorderWalk.
Please see funtion definition also.
2 - CLinkList<T> *m_pListPreorder ;
Pointer to the link list prepared by calling
TreePreorderWalk.
Please see funtion definition also.
3 - CLinkList<T> *m_pListPostorder ;
Pointer to the link list prepared by calling
TreePostorderWalk.
Please see funtion definition also.
private ::
1 - CNode<T> *m_pNode ;
Pointer used in varoius funtions for various
operations, no specific purpose.
2 - CNode<T> *m_pRoot ;
Pointer to the root of the tree.
3 - int m_TotelElements ;
Totel number of nodes in the tree.
******************************************************************************/
#ifndef __TREE__TEMPLATE__H__
#define __TREE__TEMPLATE__H__
#pragma once
template <class T>
class CTree
{
CNode<T> *m_pNode ;
CNode<T> *m_pRoot ;
int m_TotelElements ;
bool InorderTreeWalk(CNode<T>*) ;
bool PreorderTreeWalk(CNode<T>*) ;
bool PostorderTreeWalk(CNode<T>*) ;
bool InorderTreeWalk(T & ) ;
bool PreorderTreeWalk(T & ) ;
bool PostorderTreeWalk(T & ) ;
public:
CLinkList<T> *m_pListInorder ;
CLinkList<T> *m_pListPreorder ;
CLinkList<T> *m_pListPostorder ;
public:
CTree(void);
~CTree(void);
bool AddRoot(T & );
bool Insert(T & );
bool Delete(CNode<T>* pNode );
bool Delete(T & );
bool Search(T &obj, CNode<T> **pOut);
bool Search(T & );
bool Minimum(CNode<T>* , CNode<T>** );
bool Minimum(T &, T & );
bool Maximum(CNode<T>* , CNode<T>** );
bool Maximum(T &, T & );
bool Successor(CNode<T>* , CNode<T>** );
bool Successor(T &, T &);
bool Predecessor(CNode<T>* , CNode<T>** );
bool Predecessor(T &, T &);
CNode<T>* Parent(CNode<T>** pNode) ;
CNode<T>* Left(CNode<T>** pNode) ;
CNode<T>* Right(CNode<T>** pNode) ;
bool Parent(T &, T &) ;
bool Left(T &, T &) ;
bool Right(T &, T &) ;
bool TreeInorderWalk(CNode<T>*) ;
bool TreePreorderWalk(CNode<T>*) ;
bool TreePostorderWalk(CNode<T>*) ;
bool TreeInorderWalk(T & ) ;
bool TreePreorderWalk(T & ) ;
bool TreePostorderWalk(T & ) ;
bool DeleteTree(CNode<T>*) ;
bool DeleteTree(T & ) ;
};
/******************************************************************************
Method Name:: CTree (Constutor)
Parameters:: None
Return:: None
Purpose:: Constructs CTree objects.
******************************************************************************/
template <class T>
CTree<T>::CTree(void)
{
m_pNode = NULL;
m_pRoot = NULL;
m_TotelElements = 0;
m_pListInorder = NULL;;
m_pListPreorder = NULL;;
m_pListPostorder = NULL;;
}
/******************************************************************************
Method Name:: ~CTree (Distructor)
Parameters:: None
Return:: None
Purpose:: Distructs CTree objects.
******************************************************************************/
template <class T>
CTree<T>::~CTree(void)
{
if(m_pRoot) {
DeleteTree(m_pRoot) ;
m_pRoot = NULL;
}
if(m_TotelElements) {
m_TotelElements = 0;
}
if(m_pListInorder) {
delete m_pListInorder ;
m_pListInorder = NULL ;
}
if(m_pListPreorder){
delete m_pListPreorder ;
m_pListPreorder = NULL ;
}
if(m_pListPostorder) {
delete m_pListPostorder ;
m_pListPostorder = NULL ;
}
}
/******************************************************************************
Method Name:: AddRoot
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Adds the root node if already not present in the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::AddRoot(T & obj)
{
m_pNode = new CNode<T> ; //allocate memory to root
if(!m_pNode) {
return false;
}
m_pNode->m_Node = obj ; //copy the object
m_pRoot = m_pNode ; //set the root pointer
m_TotelElements = 1 ; //increase the count of elements in the tree
m_pNode->m_pParent = NULL ;
m_pNode->m_pLeft = NULL ;
m_pNode->m_pRight = NULL ;
return true ;
}
/******************************************************************************
Method Name:: Insert
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Inserts a node in the tree, can be used to insert root also if
root is already not present in the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::Insert(T & obj)
{
if( 0 == m_TotelElements ) //no root first element
{
if(!AddRoot(obj)) { //add at the root position
return false ; //return on failour
}
else {
return true ;
}
}
m_pNode = m_pRoot ;
//now traverse to the right node
while(m_pNode) {
if(m_pNode->m_Node == obj) {
return false ; //element already present
}
if(m_pNode->m_Node > obj && m_pNode ->m_pLeft != NULL) {
m_pNode = m_pNode->m_pLeft ;
continue;
}
else if(m_pNode->m_Node < obj && m_pNode ->m_pRight != NULL) {
m_pNode = m_pNode->m_pRight ;
continue;
}
else {
break ;
}
}
//now insert at the appropriate position
if(m_pNode->m_Node > obj) {
m_pNode->m_pLeft = new CNode<T> ;
if(!m_pNode->m_pLeft) {
return false ;
}
m_pNode->m_pLeft->m_pParent = m_pNode ; //set parent
m_pNode = m_pNode->m_pLeft ;
m_pNode->m_pLeft = NULL ;
m_pNode->m_pRight = NULL ;
m_pNode->m_Node = obj ; //insert data
++m_TotelElements ; //increment count
}
else {
m_pNode->m_pRight = new CNode<T> ;
if(!m_pNode->m_pRight) {
return false ;
}
m_pNode->m_pRight->m_pParent = m_pNode ; //set parent
m_pNode = m_pNode->m_pRight ;
m_pNode->m_pLeft = NULL ;
m_pNode->m_pRight = NULL ;
m_pNode->m_Node = obj ; //insert data
++m_TotelElements ; //increment count
}
return true;
}
/******************************************************************************
Method Name:: Delete
Parameters::
1- [IN] CNode<T>* pNode
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Deletes a node frem the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::Delete(CNode<T>* pNode)
{
if(0 == m_TotelElements) {
return false ;
}
//if only root
if(1 == m_TotelElements) {
if(m_pRoot == pNode) {
delete pNode ;
--m_TotelElements ;
return true ;
}
else {
return false; //node is not in the tree
}
}
// when leaf root ;
m_pNode = Parent(&pNode) ;
if(pNode->m_pLeft == NULL && pNode->m_pRight == NULL) {
if(pNode == Left(&m_pNode)) {
m_pNode->m_pLeft = NULL ;
delete pNode ;
--m_TotelElements ;
return true ;
}
else {
m_pNode->m_pRight = NULL ;
delete pNode ;
--m_TotelElements ;
return true ;
}
}
// one of the child is not present
if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL) {
m_pNode = Parent(&pNode) ;
if(!m_pNode) {
if(Left(&pNode) == NULL) {
Right(&pNode)->m_pParent = NULL ;
}
else if(Right(&pNode) == NULL) {
Left(&pNode)->m_pParent = NULL ;
}
delete pNode ; //delete root
--m_TotelElements ;
return true ;
}
if(Left(&m_pNode) == pNode) {
m_pNode->m_pLeft = pNode->m_pRight ;
delete pNode ;;
--m_TotelElements ;
return true ;
}
else if (Right(&m_pNode) == pNode) {
m_pNode->m_pRight = pNode->m_pRight ;
delete pNode ;
--m_TotelElements ;
return true ;
}
}
else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL) {
m_pNode = Parent(&pNode) ;
if(!m_pNode) {
if(Left(&pNode) == NULL) {
Right(&pNode)->m_pParent = NULL ;
}
else if(Right(&pNode) == NULL) {
Left(&pNode)->m_pParent = NULL ;
}
delete pNode ; //delete root
--m_TotelElements ;
return true ;
}
if(Left(&m_pNode) == pNode) {
m_pNode->m_pLeft = pNode->m_pLeft ;
delete pNode ;
--m_TotelElements ;
return true ;
}
else if(Right(&m_pNode) == pNode) {
m_pNode->m_pRight = pNode->m_pLeft ;
delete pNode ;
--m_TotelElements ;
return true;
}
}
//both of the child are present
CNode<T> *tempObj = NULL ;
Successor(pNode,&tempObj) ;
//swap with successor
m_pNode->m_Node = tempObj->m_Node ;
tempObj->m_Node = m_pNode->m_Node ;
pNode->m_Node = m_pNode->m_Node ;
Delete(tempObj) ;
return true;
}
/******************************************************************************
Method Name:: Delete
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Deletes a node frem the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::Delete(T & obj) {
CNode<T> *pNode ;
Search(obj,&pNode);
if(!pNode) {
return false ;
}
return Delete(pNode) ;
}
/******************************************************************************
Method Name:: Search
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches a node in the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::Search(T & obj)
{
m_pNode = m_pRoot ;
while(m_pNode) {
if(m_pNode->m_Node == obj) {
return true ;
}
else if(m_pNode->m_Node > obj){
continue ;
}
else if(m_pNode->m_Node < obj){
continue ;
}
}
return false;
}
/******************************************************************************
Method Name:: Search
Parameters::
1- [IN] T & obj
2- [OUT] CNode<T> **pOut
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Sarches a node in the tree. OUT parameter holds the address of
the searched node, and NULL if node is not found in the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::Search(T & obj, CNode<T> **pOut)
{
m_pNode = m_pRoot ;
while(m_pNode) {
if(m_pNode->m_Node == obj) {
*pOut = m_pNode ;
return true ;
}
else if(m_pNode->m_Node > obj){
m_pNode = m_pNode->m_pLeft ;
continue ;
}
else if(m_pNode->m_Node < obj){
m_pNode = m_pNode->m_pRight ;
continue ;
}
}
pOut = NULL ;
return false;
}
/******************************************************************************
Method Name:: Minimum
Parameters::
1- [IN] CNode<T>* pNode
2- [OUT] CNode<T>** pMinimum
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for tree minimum, from the node pointed by IN
parameter and returns the minimum in the OUT parameter.
Give pointer to the root of the tree to search Tree
Minimum.
******************************************************************************/
template<typename T>
bool CTree<T>::Minimum(CNode<T>* pNode, CNode<T>** pMinimum)
{
if(0 == m_TotelElements) {
return false ; //no element
}
m_pNode = pNode ;
while(m_pNode->m_pLeft != NULL) {
m_pNode = m_pNode->m_pLeft ;
}
*pMinimum = m_pNode ;
return true;
}
/******************************************************************************
Method Name:: Minimum
Parameters::
1- [IN] T & obj
2- [OUT] T & objMinimum
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for tree minimum, from the node conataining IN
parameter and returns the minimum in the OUT parameter.
Give value of the root of the tree to search Tree Minimum.
******************************************************************************/
template<typename T>
bool CTree<T>::Minimum(T & obj, T & objMinimum)
{
CNode<T>* pNode ;
CNode<T>* pMinimum ;
Search(obj,&pNode) ;
if(!pNode) {
return false ;
}
Minimum(pNode, &pMinimum) ;
if(!pMinimum) {
return false ;
}
objMinimum = pMinimum->m_Node ;
return true ;
}
/******************************************************************************
Method Name:: Maximum
Parameters::
1- [IN] CNode<T>* pNode
2- [OUT] CNode<T>** pMaximum
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for tree maximum, from the node conataining IN
parameter and returns the maximum in the OUT parameter.
Give value of the root of the tree to search Tree Maximum.
******************************************************************************/
template<typename T>
bool CTree<T>::Maximum(CNode<T>* pNode, CNode<T>** pMaximum)
{
if(0 == m_TotelElements) {
return false ; //no element
}
m_pNode = pNode ;
while(m_pNode->m_pRight != NULL) {
m_pNode = m_pNode->m_pRight ;
}
*pMaximum = m_pNode ;
return true;
}
/******************************************************************************
Method Name:: Maximum
Parameters::
1- [IN] T & obj
2- [OUT] T & objMaximum
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for tree maximum, from the node conataining IN
parameter and returns the maximum in the OUT parameter.
Give value of the root of the tree to search Tree Maximum.
******************************************************************************/
template<typename T>
bool CTree<T>::Maximum(T & obj, T & objMaximum)
{
CNode<T>* pNode ;
CNode<T>* pMaximum ;
Search(obj,&pNode) ;
if(!pNode) {
return false ;
}
Maximum(pNode, &pMaximum) ;
if(!pMaximum) {
return false ;
}
objMaximum = pMaximum->m_Node ;
return true ;
}
/******************************************************************************
Method Name:: Successor
Parameters::
1- [IN] CNode<T>* pNode
2- [OUT] CNode<T>** pSuccessor
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the successor of the node pointed by IN
parameter, result is returned in OUT parameter, OUT
paramenter contains NULL is successor is not present.
******************************************************************************/
template<typename T>
bool CTree<T>::Successor(CNode<T>* pNode, CNode<T>** pSuccessor)
{
if(0 == m_TotelElements) {
return false ; //no element
}
if(pNode->m_pRight != NULL) {
if(!Minimum(pNode->m_pRight,pSuccessor)) {
return false ;
}
else {
return true ;
}
}
m_pNode = Parent(&pNode);
*pSuccessor = pNode ;
while(m_pNode != NULL && *pSuccessor == Right(&m_pNode)) {
*pSuccessor = m_pNode ;
m_pNode = Parent(&m_pNode) ;
}
*pSuccessor = m_pNode ;
return true ;
}
/******************************************************************************
Method Name:: Successor
Parameters::
1- [IN] T & obj
2- [OUT] T & objSuccessor
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the successor of the node containg IN
parameter, result is returned in OUT parameter, this
function fails and returns false if successor is not
present.
******************************************************************************/
template<typename T>
bool CTree<T>::Successor(T & obj, T & objSuccessor)
{
CNode<T> *pNode = NULL ;
CNode<T> *pSuccessor = NULL ;
Search(obj,&pNode) ;
if(!pNode) {
return false ;
}
Successor(pNode,&pSuccessor) ;
if(!pSuccessor) {
return false ;
}
objSuccessor = pSuccessor->m_Node ;
return true ;
}
/******************************************************************************
Method Name:: Predecessor
Parameters::
1- [IN] CNode<T>* pNode
2- [OUT] CNode<T>** pPredecessor
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the predecessor of the node pointed by IN
parameter, result is returned in OUT parameter, OUT
paramenter contains NULL is predecessor is not present.
******************************************************************************/
template<typename T>
bool CTree<T>::Predecessor(CNode<T>* pNode, CNode<T>** pPredecessor)
{
if(0 == m_TotelElements) {
return false ; //no element
}
if(pNode->m_pLeft != NULL) {
if(!Maximum(pNode->m_pLeft,pPredecessor)) {
return false ;
}
else {
return true ;
}
}
m_pNode = Parent(&pNode);
*pPredecessor = pNode ;
while(m_pNode != NULL && *pPredecessor == Left(&m_pNode)) {
*pPredecessor = m_pNode ;
m_pNode = Parent(&m_pNode) ;
}
*pPredecessor = m_pNode ;
return true ;
}
/******************************************************************************
Method Name:: Predecessor
Parameters::
1- [IN] T & obj
2- [OUT] T & objPredecessor
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the predecessor of the node containg IN
parameter, result is returned in OUT parameter, this
function fails and returns false if predecessor is not
present.
******************************************************************************/
template<typename T>
bool CTree<T>::Predecessor(T & obj, T & objPredecessor)
{
CNode<T> *pNode = NULL ;
CNode<T> *pPredecessor = NULL ;
Search(obj,&pNode) ;
if(!pNode) {
return false ;
}
Predecessor(pNode, &pPredecessor) ;
if(!pPredecessor) {
return false ;
}
objPredecessor = pPredecessor->m_Node ;
return true ;
}
/******************************************************************************
Method Name:: Parent
Parameters::
1- [IN] CNode<T>** pNode
Return:: CNode<T>*
CNode<T>* - On Success.
NULL - On Failure.
Purpose::
Returns the parent of the node pointed by IN parameter.
******************************************************************************/
template<typename T>
CNode<T>* CTree<T>::Parent(CNode<T>** pNode)
{
return (*pNode)->m_pParent;
}
/******************************************************************************
Method Name:: Left
Parameters::
1- [IN] CNode<T>** pNode
Return:: CNode<T>*
CNode<T>* - On Success.
NULL - On Failure.
Purpose::
Returns the left child of the node pointed by IN parameter.
******************************************************************************/
template<typename T>
CNode<T>* CTree<T>::Left(CNode<T>** pNode)
{
return (*pNode)->m_pLeft;
}
/******************************************************************************
Method Name:: Right
Parameters::
1- [IN] CNode<T>** pNode
Return:: CNode<T>*
CNode<T>* - On Success.
NULL - On Failure.
Purpose::
Returns the right child of the node pointed by IN parameter.
******************************************************************************/
template<typename T>
CNode<T>* CTree<T>::Right(CNode<T>** pNode)
{
return (*pNode)->m_pRight;
}
/******************************************************************************
Method Name:: Parent
Parameters::
1- [IN] T & obj
2- [OUT] T & objOut
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the parent of the node contained in the IN
parameter, OUT parameter contains the result, this function
fails and returns false if parent not present.
******************************************************************************/
template<typename T>
bool CTree<T>::Parent(T & obj, T & objOut)
{
CNode *pNode ;
Search(obj, &pNode) ;
if(!pNode) {
return false ;
}
pNode = Parent(&pNode) ;
if(!pNode) {
return false ;
}
pbjOut = pNode->m_Node ;
return true;
}
/******************************************************************************
Method Name:: Left
Parameters::
1- [IN] T & obj
2- [OUT] T & objOut
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the left child of the node contained in the IN
parameter, OUT parameter contains the result, this function
fails and returns false if left child not present.
******************************************************************************/
template<typename T>
bool CTree<T>::Left(T & obj, T & objOut)
{
CNode *pNode ;
Search(obj, &pNode) ;
if(!pNode) {
return false ;
}
pNode = Left(&pNode) ;
if(!pNode) {
return false ;
}
pbjOut = pNode->m_Node ;
return true;
}
/******************************************************************************
Method Name:: Right
Parameters::
1- [IN] T & obj
2- [OUT] T & objOut
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the right child of the node contained in the IN
parameter, OUT parameter contains the result, this function
fails and returns false if right child not present.
******************************************************************************/
template<typename T>
bool CTree<T>::Right(T & obj, T & objOut)
{
CNode *pNode ;
Search(obj, &pNode) ;
if(!pNode) {
return false ;
}
pNode = Right(&pNode) ;
if(!pNode) {
return false ;
}
pbjOut = pNode->m_Node ;
return true;
}
/******************************************************************************
Method Name:: InorderTreeWalk
Parameters::
1- [IN] CNode<T>* pNodeI
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Performs a In Order Tree walk of the tree or a sub tree
pointed by IN parameter. It prepares a link list of
content of tree nodes it encounter. This list is pointed
public data member of class CTree names as m_pListInorder.
There are various other functions suppored by this list,
they are explained in LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
******************************************************************************/
template<typename T>
bool CTree<T>::InorderTreeWalk(CNode<T>* pNodeI) {
CNode<T>* pNode ;
pNode = pNodeI;
if(pNode != NULL ){
InorderTreeWalk(pNode->m_pLeft) ;
m_pListInorder->AddToLast(pNode->m_Node) ;
InorderTreeWalk(pNode->m_pRight) ;
}
return true ;
}
/******************************************************************************
Method Name:: PreorderTreeWalk
Parameters::
1- [IN] CNode<T>* pNodeP
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Performs a Pre Order Tree walk of the tree or a sub tree
pointed by IN parameter. It prepares a link list of
content of tree nodes it encounter. This list is pointed
public data member of class CTree names as m_pListPreorder.
There are various other functions suppored by this list,
they are explained in LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
******************************************************************************/
template<typename T>
bool CTree<T>::PreorderTreeWalk(CNode<T>* pNodeP) {
CNode<T>* pNode ;
pNode = pNodeP;
if(pNode != NULL ){
m_pListPreorder->AddToLast(pNode->m_Node) ;
PreorderTreeWalk(pNode->m_pLeft) ;
PreorderTreeWalk(pNode->m_pRight) ;
}
return true ;
}
/******************************************************************************
Method Name:: PostorderTreeWalk
Parameters::
1- [IN] CNode<T>* pNodeP
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Performs a Post Order Tree walk of the tree or a sub tree
pointed by IN parameter. It prepares a link list of
content of tree nodes it encounter. This list is pointed
public data member of class CTree names as m_pListPostorder.
There are various other functions suppored by this list,
they are explained in LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
******************************************************************************/
template<typename T>
bool CTree<T>::PostorderTreeWalk(CNode<T>* pNodeP) {
CNode<T>* pNode ;
pNode = pNodeP;
if(pNode != NULL ){
PostorderTreeWalk(pNode->m_pLeft) ;
PostorderTreeWalk(pNode->m_pRight) ;
m_pListPostorder->AddToLast(pNode->m_Node) ;
}
return true ;
}
/******************************************************************************
Method Name:: InorderTreeWalk
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node containg IN parameter and performs a
In Order Tree walk of the tree or a sub tree containing IN
parameter. It prepares a link list of content of tree nodes
it encounter. This list is pointed public data member of
class CTree names as m_pListInorder.There are various other
functions suppored by this list,they are explained in
LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
This functions fails and returns false if node containg IN
parameter not found.
******************************************************************************/
template<typename T>
bool CTree<T>::InorderTreeWalk(T & obj) {
CNode<T>* pNode = NULL ;
Search(obj,&pNode) ;
if(pNode == NULL) {
return false ;
}
return InorderTreeWalk(pNode) ;
}
/******************************************************************************
Method Name:: PreorderTreeWalk
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node containg IN parameter and performs a
Pre Order Tree walk of the tree or a sub tree containing IN
parameter. It prepares a link list of content of tree nodes
it encounter. This list is pointed public data member of
class CTree names as m_pListPretorder.There are various other
functions suppored by this list,they are explained in
LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
This functions fails and returns false if node containg IN
parameter not found.
******************************************************************************/
template<typename T>
bool CTree<T>::PreorderTreeWalk(T & obj) {
CNode<T>* pNode = NULL ;
Search(obj,&pNode) ;
if(pNode == NULL) {
return false ;
}
return PreorderTreeWalk(pNode) ;
}
/******************************************************************************
Method Name:: PostorderTreeWalk
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node containg IN parameter and performs a
Post Order Tree walk of the tree or a sub tree containing IN
parameter. It prepares a link list of content of tree nodes
it encounter. This list is pointed public data member of
class CTree names as m_pListPostorder.There are various other
functions suppored by this list,they are explained in
LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
This functions fails and returns false if node containg IN
parameter not found.
******************************************************************************/
template<typename T>
bool CTree<T>::PostorderTreeWalk(T & obj) {
CNode<T>* pNode = NULL ;
Search(obj,&pNode) ;
if(pNode == NULL) {
return false ;
}
return PostorderTreeWalk(pNode) ;
}
/******************************************************************************
Method Name:: TreeInorderWalk
Parameters::
1- [IN] CNode<T>* pNode
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Performs a In Order Tree walk of the tree or a sub tree
pointed by IN parameter. It prepares a link list of
content of tree nodes it encounter. This list is pointed
public data member of class CTree names as m_pListInorder.
There are various other functions suppored by this list,
they are explained in LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
******************************************************************************/
template<typename T>
bool CTree<T>::TreeInorderWalk(CNode<T>* pNode)
{
if(m_pListInorder) {
delete m_pListInorder ;
}
m_pListInorder = new CLinkList<T> ;
if(!m_pListInorder) {
return false ;
}
return InorderTreeWalk(pNode) ;
}
/******************************************************************************
Method Name:: TreePreorderWalk
Parameters::
1- [IN] CNode<T>* pNode
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Performs a Pre Order Tree walk of the tree or a sub tree
pointed by IN parameter. It prepares a link list of
content of tree nodes it encounter. This list is pointed
public data member of class CTree names as m_pListPreorder.
There are various other functions suppored by this list,
they are explained in LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
******************************************************************************/
template<typename T>
bool CTree<T>::TreePreorderWalk(CNode<T>* pNode)
{
if(m_pListPreorder) {
delete m_pListPreorder ;
}
m_pListPreorder = new CLinklist ;
if(!m_pListPreorder) {
return false ;
}
return PreorderTreeWalk(pNode);
}
/******************************************************************************
Method Name:: TreePostorderWalk
Parameters::
1- [IN] CNode<T>* pNode
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Performs a Post Order Tree walk of the tree or a sub tree
pointed by IN parameter. It prepares a link list of
content of tree nodes it encounter. This list is pointed
public data member of class CTree names as m_pListPostorder.
There are various other functions suppored by this list,
they are explained in LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
******************************************************************************/
template<typename T>
bool CTree<T>::TreePostorderWalk(CNode<T>* pNode)
{
if(m_pListPostorder) {
delete m_pListPostorder ;
}
return PostorderTreeWalk(pNode) ;
}
/******************************************************************************
Method Name:: TreeInorderWalk
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node containg IN parameter and performs a
In Order Tree walk of the tree or a sub tree containing IN
parameter. It prepares a link list of content of tree nodes
it encounter. This list is pointed public data member of
class CTree names as m_pListInorder.There are various other
functions suppored by this list,they are explained in
LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
This functions fails and returns false if node containg IN
parameter not found.
******************************************************************************/
template<typename T>
bool CTree<T>::TreeInorderWalk(T & obj)
{
if(m_pListInorder) {
delete m_pListInorder ;
}
m_pListInorder = new CLinkList<T> ;
if(!m_pListInorder) {
return false ;
}
return InorderTreeWalk(obj) ;
}
/******************************************************************************
Method Name:: TreePreorderWalk
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node containg IN parameter and performs a
Pre Order Tree walk of the tree or a sub tree containing IN
parameter. It prepares a link list of content of tree nodes
it encounter. This list is pointed public data member of
class CTree names as m_pListPretorder.There are various other
functions suppored by this list,they are explained in
LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
This functions fails and returns false if node containg IN
parameter not found.
******************************************************************************/
template<typename T>
bool CTree<T>:: TreePreorderWalk(T & obj)
{
if(m_pListPreorder) {
delete m_pListPreorder ;
}
m_pListPreorder = new CLinkList<T> ;
if(!m_pListPreorder) {
return false ;
}
return PreorderTreeWalk(obj);
}
/******************************************************************************
Method Name:: TreePostorderWalk
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node containg IN parameter and performs a
Post Order Tree walk of the tree or a sub tree containing IN
parameter. It prepares a link list of content of tree nodes
it encounter. This list is pointed public data member of
class CTree names as m_pListPostorder.There are various other
functions suppored by this list,they are explained in
LinkList.h.
Pass pointer to the root of the tree to traverse whole tree.
This functions fails and returns false if node containg IN
parameter not found.
******************************************************************************/
template<typename T>
bool CTree<T>::TreePostorderWalk(T & obj)
{
if(m_pListPostorder) {
delete m_pListPostorder ;
}
m_pListPostorder = new CLinkList<T> ;
if(!m_pListPostorder) {
return false ;
}
return PostorderTreeWalk(obj);
}
/******************************************************************************
Method Name:: DeleteTree
Parameters::
1- [IN] CNode<T>* pNodeD
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Deletes tree or the sub tree pointed by IN parameter.
******************************************************************************/
template<typename T>
bool CTree<T>::DeleteTree(CNode<T>* pNodeD)
{
static bool deletall = false ;
if(pNodeD == NULL ) {
return true ;
}
CNode<T>* pNode ;
pNode = pNodeD;
if(pNodeD == m_pRoot){
m_pRoot= NULL;
deletall = true ;
}
else {
m_pNode = Parent(&pNodeD) ;
if(pNodeD == Left(&m_pNode)) {
m_pNode->m_pLeft = NULL ;
}
else {
m_pNode->m_pRight = NULL ;
}
}
if(pNodeD == m_pNode && deletall){
m_pNode= NULL;
}
if(pNode != NULL ){
if(pNode->m_pLeft) {
DeleteTree(pNode->m_pLeft) ;
}
if(pNode->m_pRight) {
DeleteTree(pNode->m_pRight) ;
}
if(pNode) {
pNode->m_pLeft = NULL ;
pNode->m_pRight = NULL ;
delete pNode ;
pNode = NULL;
}
}
--m_TotelElements ;
return true ;
}
/******************************************************************************
Method Name:: DeleteTree
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches for the node in the tree containg value equal to IN
parameter, and then deletes the tree or the sub tree from the
found node. Pass content of the root to delet complete tree.
This function fails and return false if value paases not
present in the tree.
******************************************************************************/
template<typename T>
bool CTree<T>::DeleteTree(T & obj)
{
CNode<T>* pNode = NULL ;
Search(obj,&pNode) ;
if(pNode == NULL) {
return false ;
}
if(m_pListInorder ){
delete m_pListInorder ;
m_pListInorder = NULL ;
}
if(m_pListPreorder) {
delete m_pListPreorder ;
m_pListPreorder = NULL ;
}
if(m_pListPostorder) {
delete m_pListPostorder ;
m_pListPostorder = NULL ;
}
return DeleteTree(pNode) ;
}
#endif
Submit an article or tip