Binary Search Tree Template






3.65/5 (13 votes)
This is a class library, it can be used to create binary search tree of any basic data type or a class object.
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.
CLinkList<T> *m_pListInorder ;
Pointer to the link list prepared by callingTreeInorderWalk
CLinkList<T> *m_pListPreorder ;
Pointer to the link list prepared by callingTreePreorderWalk
CLinkList<T> *m_pListPostorder ;
Pointer to the link list prepared by callingTreePostorderWalk
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
bool AddRoot(T & );
Adds the root element, only if root is not present.bool Insert(T & );
Inserts an element in the tree, can insert root if not present.bool Delete(T & );
Deletes an element from the tree.bool Search(T & );
Searches for an element.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.bool Maximum(T &, T & );
Counterpart of Minimum.bool Successor(T &, T & );
Searches for Successor of the tree or a sub tree, passes content of the root inIN
parameter (see code) to find Successor of the tree.bool Predecessor(T &, T & );
Counterpart of Successor.bool Parent(T &, T &) ;
Searches for parent of a node in the tree.bool Left(T &, T &) ;
Searches for left child of a node in the tree.bool Right(T &, T &) ;
Searches for right child of a node in the tree.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.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.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.bool DeleteTree(T & ) ;
Deletes a tree or a sub tree. Passes content of the root to delete complete tree.bool Delete(CNode<T>* pNode );
Deletes a node in the tree.bool Search(T &obj, CNode<T> **pOut);
Searches for a node in the tree, and returns its pointer in theout
parameter (see code).bool Minimum(CNode<T>* , CNode<T>** );
Searches for minimum of the tree or a sub tree, passes pointer to the root inIN
parameter (see code) to find minimum of the tree. Minimum is returned inOUT
parameter (see code).bool Maximum(CNode<T>* , CNode<T>** );
Counterpart of minimum.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 inOUT
parameter (see code).bool Predecessor(CNode<T>* , CNode<T>** );
Counterpart of the Successor.CNode<T>* Parent(CNode<T>** pNode)
Returns pointer to the Parent of a node.CNode<T>* Left(CNode<T>** pNode)
Returns pointer to the Left child of a node.CNode<T>* Right(CNode<T>** pNode)
Returns pointer to the Right child of a node.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.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.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.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:bool AddToFirst(T &);
Add a node in the beginning of the linked list.bool AddToLast(T &);
Add a node at the end of the linked list.bool DeleteFirst();
Deletes a node from the beginning of the linked list.bool DeleteLast();
Deletes a node from the end of the linked list.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
- 18th May, 2006: Initial post
