Binary Search Tree Template

18 Years Ago dubeyprateek 0 153 Views
Introduction
There are many times when we try to create a binary search tree of many different data types. This article explains creation of a template library CTree. template <class T>class CTree can be used to create a binary search tree (BST) of any data type.
Features
This class support all basic operations on the tree, other then basic operations it includes
bool TreeInorderWalk(CNode<T>*) ;
bool TreePreorderWalk(CNode<T>*) ;
bool TreePostorderWalk(CNode<T>*) ;
bool TreeInorderWalk(T & ) ;
bool TreePreorderWalk(T & ) ;
bool TreePostorderWalk(T & ) ;
These functions performs various walks on the tree and they prepare a lnk list of all the nodes in the order they incounter. Pointer of thses link list is a public data member of ths CTree class.
1 - CLinkList<T> *m_pListInorder ;
Pointer to the link list prepared by calling TreeInorderWalk.
2 - CLinkList<T> *m_pListPreorder ;
Pointer to the link list prepared by calling TreePreorderWalk.
3 - CLinkList<T> *m_pListPostorder ;
Pointer to the link list prepared by calling TreePostorderWalk.
This list further supports a number of operations like
bool AddToFirst(T &);
bool AddToLast(T &);
bool DeleteFirst();
bool DeleteLast();
bool GetNode(T &, CListNode<T> **) ;
How to use
using is class is very simple, just copy all the header files
Node.h
ListNode.h"
LinkList.h
Tree.h
Treelib.h
to your project folder and inlude TreeLib.h in your application. After this
create an intance of 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.
Thses objects now support a nummber of methods of the class like
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>*) ;
In addition the link lists which can be prepared by using methods from 22 to 26 supprors methods like
1 - bool AddToFirst(T &);
2 - bool AddToLast(T &);
3 - bool DeleteFirst();
4 - bool DeleteLast();
5 - bool GetNode(T &, CListNode<T> **) ;
Constraints
While creating tree of any user defined class object one must over load '==', '=', '<' and '>' operators, in the class.
At Last
I have tested this for a number of opertaions, but if you find any kind of bug, feel free to inform me. Enjoy reading.
Prateek Kumar Dubey
/******************************************************************************
-------------------------------------------------------------------------------
                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 ::             TreeLib.h

Purpose ::
            Include this file in your application to avail yourself with all
            functionality of class CTree.
******************************************************************************/
#ifndef __TREE__TEMPLATE__TREELIB__H__
#define __TREE__TEMPLATE__TREELIB__H__

#pragma once

#include <iostream>
#include <tchar.h>

// TODO: reference additional headers your program requires here
#include "Node.h"
#include "ListNode.h"
#include "LinkList.h"
#include "Tree.h"

#endif
/*****************************************************************************/
//node.h
#ifndef __TREE__TEMPLATE__NODE__H__
#define __TREE__TEMPLATE__NODE__H__

#pragma once

template <class T>
class CNode
{
public:
    T       m_Node ;
    CNode   *m_pLeft ;
    CNode   *m_pRight ;
    CNode   *m_pParent ;
public:
    CNode(void) ;
    CNode(T &obj) ;
    ~CNode(void) ;
};

template <class T>
CNode<T>::CNode(void)
{
    m_pLeft = NULL ;
    m_pRight = NULL ;
    m_pParent = NULL ;
}

template <class T>
CNode<T>::CNode(T &obj)
{
    m_Node = obj ;
    m_pLeft = NULL ;
    m_pRight = NULL ;
    m_pParent = NULL ;
}

template <class T>
CNode<T>::~CNode(void)
{
}
#endif
/*****************************************************************************/

#ifndef __TREE__TEMPLATE__LISTNODE__H__
#define __TREE__TEMPLATE__LISTNODE__H__

#pragma once
template< class T>
class CListNode
{
public:
    T           m_Node ;
    CListNode   *m_pNext ;
public:
    CListNode(void);
    CListNode(T & obj);
    ~CListNode(void);
};

template <typename T>
CListNode<T>::CListNode() {
    m_pNext = NULL ;
}

template <typename T>
CListNode<T>::~CListNode() {
}

template <typename T>
CListNode<T>::CListNode(T &obj) {
    m_Node = obj ;
    m_pNext = NULL ;
}
#endif

/******************************************************************************
-------------------------------------------------------------------------------
                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 ::             LinkList.h

Supporting Files ::
            1   -       ListNode.h

Used By::
                        Tree.h

Purpose ::
            This header file declares and defines a Link List template
            class CLinkList. using this template loink list of any object
            or of basic data type can be created.

Example ::
            CLinkList<int> objCLinkListInt ;    //creating an instance of class
            CLinkList<float> objCLinkListFloat ;
            CLinkList<MyClass> objCLinkListMyClass ;

            Now use various methods of CTree for further processings.

Methods ::
            Public ::
                1   -       bool AddToFirst(T &);
                2   -       bool AddToLast(T &);
                3   -       bool DeleteFirst();
                4   -       bool DeleteLast();
                5   -       bool GetNode(T &, CListNode<T> **) ;

Member Variables ::
            private ::
                1   -       CListNode<T>        *m_pNode ;
                                Pointer used in varoius funtions for various
                                operations, no specific purpose.

                2   -       CListNode<T>        *m_pHead ;
                                Pointer to the first node of link list.

                3   -       CListNode<T>        *m_pTail ;
                                Pointer to the last node of link list.

                4   -       int                 m_TotelElements ;
                                Totel number of elements in the link list.

******************************************************************************/

#ifndef __TREE__TEMPLATE__LINKLIST__H__
#define __TREE__TEMPLATE__LINKLIST__H__
#pragma once


template <class T>
class CLinkList
{
    CListNode<T>    *m_pNode ;
    CListNode<T>    *m_pHead ;
    CListNode<T>    *m_pTail ;
    int         m_TotelElements ;
public:
    CLinkList(void);
    ~CLinkList(void);
    bool AddToFirst(T &);
    bool AddToLast(T &);
    bool DeleteFirst();
    bool DeleteLast();
    bool GetNode(T &, CListNode<T> **) ;
};


/******************************************************************************
Method Name::   CLinkList (Constutor)

Parameters::    None

Return::        None

Purpose::       Constructs CLinkList objects.

******************************************************************************/
template <typename T>
CLinkList<T>::CLinkList() {
    m_pNode = NULL ;
    m_pHead = NULL ;
    m_pTail = NULL ;
    m_TotelElements = 0;
}

/******************************************************************************
Method Name::   ~CLinkList (Distructor)

Parameters::    None

Return::        None

Purpose::       Distructs CLinkList objects.

******************************************************************************/
template <typename T>
CLinkList<T>::~CLinkList() {
    if(m_pHead) {
        while(m_pHead) {
            m_pNode = m_pHead ;
            m_pHead = m_pHead->m_pNext ;
            delete m_pNode ;
            m_pNode = NULL ;
        }
    }
    m_pHead =  NULL ;
    m_pTail =  NULL ;
    m_TotelElements = 0;
}

/******************************************************************************
Method Name::   AddToFirst

Parameters::
                1-      [IN] T & obj

Return::        bool
                    true    - On Success.
                    false   - On Failure.
Purpose::
                Adds the node at the first position in the link list.
******************************************************************************/
template <typename T>
bool CLinkList<T>::AddToFirst(T &obj) {

    CListNode<T> *pNode = new CListNode<T> ;
    if(!pNode) {
        return false ;
    }
    pNode->m_Node = obj ;

    if(0 == m_TotelElements ) {
        pNode->m_pNext = NULL ;
        m_pHead = pNode ;
        m_pTail = pNode ;
        pNode->m_pNext = NULL ;
        m_TotelElements =1 ;
        return true ;
    }
    pNode->m_pNext = m_pHead->m_pNext ;
    m_pHead = pNode ;
    ++m_TotelElements ;
    return true ;
}

/******************************************************************************
Method Name::   AddToFirst

Parameters::
                1-      [IN] T & obj

Return::        bool
                    true    - On Success.
                    false   - On Failure.
Purpose::
                Adds the node at the last position in the link list.
******************************************************************************/
template <typename T>
bool CLinkList<T>::AddToLast(T &obj) {
    CListNode<T> *pNode = new CListNode<T> ;
    if(!pNode) {
        return false ;
    }
    pNode->m_Node = obj ;
    if(0 == m_TotelElements ) {
        pNode->m_pNext = NULL ;
        m_pHead = pNode ;
        m_pTail = pNode ;
        m_TotelElements =1 ;
        return true ;
    }
    pNode->m_pNext = NULL ;
    m_pTail->m_pNext = pNode ;
    m_pTail = pNode ;
    ++m_TotelElements ;
    return true ;
}

/******************************************************************************
Method Name::   DeleteFirst

Parameters::    None

Return::        bool
                    true    - On Success.
                    false   - On Failure.
Purpose::
                Deletes the node at the first position in the link list.
******************************************************************************/
template <typename T>
bool CLinkList<T>::DeleteFirst() {
    if(0 == m_TotelElements ) {
        return false ;
    }
    m_pNode = m_pHead ;
    m_pHead = m_pHead->m_pNext ;
    delete m_pNode ;
    --m_TotelElements ;
    return true ;
}

/******************************************************************************
Method Name::   DeleteLast

Parameters::    None

Return::        bool
                    true    - On Success.
                    false   - On Failure.
Purpose::
                Deletes the node at the last position in the link list.
******************************************************************************/
template <typename T>
bool CLinkList<T>::DeleteLast() {
    if(0 == m_TotelElements ) {
        return false ;
    }
    m_pNode = m_pHead ;
    while(m_pNode->m_pNext != m_pTail) {
        m_pNode = m_pNode->m_pNext ;
    }
    delete m_pTail ;
    m_pTail = m_pNode ;
    --m_TotelElements ;
    return true ;
}

/******************************************************************************
Method Name::   GetNode

Parameters::
                1-  [IN]    T & obj
                2-  [OUT]   CListNode<T> **pOut

Return::        bool
                    true    - On Success.
                    false   - On Failure.
Purpose::
                Searches a node in the link list. OUT parameter holds the
                address of the searched node, and NULL if node is not found
                in the linklist.
******************************************************************************/
template <typename T>
bool CLinkList<T>::GetNode(T &obj, CListNode<T> **pNode) {
    if(0 == m_TotelElements ) {
        return false ;
    }
    m_pNode = m_pHead ;
    while(m_pNode->m_Node != obj) {
        if(!m_pNode){
            break ;
        }
        m_pNode = m_pNode->m_pNext ;
    }
    *pNode = m_pNode ;
    return true ;
}
#endif


/******************************************************************************
-------------------------------------------------------------------------------
                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
Be the first to reply
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.