Binary Search Tree Template

• Download source files - 7.68 KB
• Download demo project - 135.37 KB

Introduction

There are many times when we try to create a binary search tree of many different data types. This article explains the 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.

Using the Code

Using this 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 include TreeLib.h in your application. After this, create an instance of the class.

Example

CTree<int> objCTreeInt ; //creating an instance of class
CTree<FLOAT> objCTreeFloat ;
CTree<MYCLASS> objCTreeMyClass ;

Features

This class supports all basic operations on the tree. Other than 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 perform various walks on the tree and they prepare a linked list of all the nodes in the order they are encountered. Pointer of these linked lists is a public data member of the 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> **) ;

Constraints

While creating tree of any user defined class object, one must overload '==', '=', '<' and '>' operators, in the class, and should keep a copy constructor.

Methods and Explanations

1. bool AddRoot(T & );
   Adds the root element, only if root is not present.
2. bool Insert(T & );
   Inserts an element in the tree, can insert root if not present.
3. bool Delete(T & );
   Deletes an element from the tree.
4. bool Search(T & );
   Searches for an element.
5. bool Minimum(T &, T & );
   Searches for minimum of the tree or a sub tree, passes content of the root in IN parameter (see code) to find minimum of the tree.
6. bool Maximum(T &, T & );
   Counterpart of Minimum.
7. bool Successor(T &, T & );
   Searches for Successor of the tree or a sub tree, passes content of the root in IN parameter (see code) to find Successor of the tree.
8. bool Predecessor(T &, T & );
   Counterpart of Successor.
9. bool Parent(T &, T &) ;
   Searches for parent of a node in the tree. 
10. bool Left(T &, T &) ;
    Searches for left child of a node in the tree.
11. bool Right(T &, T &) ;
    Searches for right child of a node in the tree.
12. bool TreeInorderWalk(T & ) ;
    Performs In Order Tree walk of the tree or a sub tree, and prepares a link list of all the nodes it encounters. Pass content of root to traverse complete tree.
13. bool TreePreorderWalk(T & ) ;
    Performs Pre Order Tree walk of the tree or a sub tree. and prepares a link list of all the nodes it encounters. Pass content of root to traverse complete tree.
14. bool TreePostorderWalk(T & ) ;
Private function:: Performs Post Order Tree walk of the tree or a sub tree, and prepares a link list of all the nodes it encounters. Pass content of root to traverse complete tree.
15. bool DeleteTree(T & ) ;
    Deletes a tree or a sub tree. Passes content of the root to delete complete tree.
16. bool Delete(CNode<T>* pNode );
    Deletes a node in the tree.
17. bool Search(T &obj, CNode<T> **pOut);
    Searches for a node in the tree, and returns its pointer in the out parameter (see code).
18. bool Minimum(CNode<T>* , CNode<T>** );
    Searches for minimum of the tree or a sub tree, passes pointer to the root in IN parameter (see code) to find minimum of the tree. Minimum is returned in OUT parameter (see code).
19. bool Maximum(CNode<T>* , CNode<T>** );
    Counterpart of minimum.
20. bool Successor(CNode<T>* , CNode<T>** );
    Searches for Successor of the node, passes pointer to the root in IN parameter (see code) to find Successor of the tree. Successor is returned in OUT parameter (see code).
21. bool Predecessor(CNode<T>* , CNode<T>** );
    Counterpart of the Successor.
22. CNode<T>* Parent(CNode<T>** pNode)
    Returns pointer to the Parent of a node.
23. CNode<T>* Left(CNode<T>** pNode)
    Returns pointer to the Left child of a node.
24. CNode<T>* Right(CNode<T>** pNode)
    Returns pointer to the Right child of a node.
25. bool TreeInorderWalk(CNode<T>*) ;
    Performs In Order Tree walk of the tree or a sub tree, and prepares a link list of all the nodes it encounters. Passes pointer to root to traverse complete tree.
26. bool TreePreorderWalk(CNode<T>*) ;
    Performs Pre Order Tree walk of the tree or a sub tree, and prepares a link list of all the nodes it encounters. Passes pointer to root to traverse complete tree.
27. bool TreePostorderWalk(CNode<T>*) ;
    Performs Post Order Tree walk of the tree or a sub tree, and prepares a link list of all the nodes it encounters. Passes pointer to root to traverse complete tree.
28. bool DeleteTree(CNode<T>*) ;
    Deletes a tree or a sub tree. Passes pointer to the root to delete complete tree.
    In addition, the link lists which can be prepared by using methods from 22 to 26 supports methods like:
1. bool AddToFirst(T &);
   Add a node in the beginning of the linked list.
2. bool AddToLast(T &);
   Add a node at the end of the linked list.
3. bool DeleteFirst();
   Deletes a node from the beginning of the linked list.
4. bool DeleteLast();
   Deletes a node from the end of the linked list.
5. bool GetNode(T &, CListNode<T> **) ;
   Retrieve pointer to a node.

At Last

I have tested this for a number of operations, but if you find any kind of bug, feel free to inform me. Enjoy reading!

History

• 18^th May, 2006: Initial post