Click here to Skip to main content
14,603,461 members

Binary Search Tree Template

Rate this:
3.65 (13 votes)
Please Sign up or sign in to vote.
3.65 (13 votes)
18 May 2006CPOL
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.

  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

  • 18th May, 2006: Initial post
Auther

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Prateek Kumar Dubey
Other Microsoft
India India
I am currently working with Microsoft at Bangalore (India). My interest lies in areas of generic C++ and windows development. Apart from office hours I try to develop new and useful small tools.
Well, I still feel that I need to be more serious..!
Smile | :)

Comments and Discussions

 
QuestionBag Pin
Member 1205037111-Oct-15 8:09
MemberMember 1205037111-Oct-15 8:09 
Generalexapanded code using string Pin
Sadru23-Feb-09 20:13
MemberSadru23-Feb-09 20:13 
#ifndef __TREE__TEMPLATE__LISTNODE__H__
#define __TREE__TEMPLATE__LISTNODE__H__

#pragma once


template< class T, typename K>
class CListNode
{
public:
K m_key;
size_t len;
T m_Node ;
CListNode *m_pNext ;
public:
CListNode(void);
CListNode(T & obj, K &key);
~CListNode(void);
};

template <typename typename="" k="">
CListNode<t,k>::CListNode() {
m_pNext = NULL ;
}

template <typename typename="" k="">
CListNode<t,k>::~CListNode() {
}

template <typename typename="" k="">
CListNode<t,k>::CListNode(T &obj, K &key) {
m_key = key;
m_Node = obj ;
m_pNext = NULL ;
len = 0;
}




#endif

#include "listnode.h"

/******************************************************************************
-------------------------------------------------------------------------------
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 typename="" k="">
class CLinkList
{
CListNode<t,k> *m_pNode ;
CListNode<t,k> *m_pHead ;
CListNode<t,k> *m_pTail ;
int m_TotelElements ;
public:
CLinkList(void);
~CLinkList(void);
bool AddToFirst(T &, K&);
bool AddToLast(T &, K&);
bool DeleteFirst();
bool DeleteLast();
bool GetNode(T &, K&, CListNode<t,k> **) ;
bool DeleteANode(K&);
bool Insert(T &obj, K &key, int pos );
};


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

Parameters:: None

Return:: None

Purpose:: Constructs CLinkList objects.

******************************************************************************/
template <typename typename="" k="">
CLinkList<t,k>::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 typename="" k="">
CLinkList<t,k>::~CLinkList() {
if(m_pHead) {
while(m_pHead) {
m_pNode = m_pHead ;
m_pHead = m_pHead->m_pNext ;
if (wcslen(m_pNode->m_key) != 0)
delete m_pNode->m_key;
delete m_pNode ;
m_pNode = NULL ;
--m_TotelElements ;
}
}
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 typename="" k="">
bool CLinkList<t,>::AddToFirst(T &obj, K &key) {
int len;
CListNode<t,> *pNode = new CListNode<t,k> ;
if(!pNode) {
return false ;
}
pNode->len = wcslen(key);
pNode->m_key = new WCHAR [(pNode->len)+1];
if(!pNode->m_key) {
return false ;
}
wcscpy_s(pNode->m_key,(pNode->len)+1,key);
pNode->m_key = key;
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 typename="" k="">
bool CLinkList<t,k>::AddToLast(T &obj, K &key) {
CListNode<t,k> *pNode = new CListNode<t,k> ;
if(!pNode) {
return false ;
}
pNode->len = wcslen(key);
pNode->m_key = new WCHAR [(pNode->len)+1];
if(!pNode->m_key) {
return false ;
}
wcscpy_s(pNode->m_key,(pNode->len)+1,key);
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 typename="" k="">
bool CLinkList<t,k>::DeleteFirst() {
if(0 == m_TotelElements ) {
return false ;
}
m_pNode = m_pHead ;
m_pHead = m_pHead->m_pNext ;
if (m_pNode->len)
delete m_pNode->m_key;
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 typename="" k="">
bool CLinkList<t,k>::DeleteLast() {
if(0 == m_TotelElements ) {
return false ;
}
m_pNode = m_pHead ;
while(m_pNode->m_pNext != m_pTail) {
m_pNode = m_pNode->m_pNext ;
}
if (m_pTail->len)
delete m_pTail->m_key;
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 typename="" k="">
bool CLinkList<t,k>::GetNode(T &obj,K &key, CListNode<t,k> **pNode) {
int len,len1;
if(0 == m_TotelElements ) {
*pNode = NULL;
return false ;
}
m_pNode = m_pHead ;
len = wcslen(key);
if (len > 64){
*pNode = NULL;
return false;
}
len1 = max(len,m_pNode->len);
while(/*m_pNode->m_Node != obj*/wcsncmp(m_pNode->m_key,key,len1)!=0) {
m_pNode = m_pNode->m_pNext ;
if (!m_pNone)
break;
len1 = max(len,m_pNode->len);
}
*pNode = m_pNode ;
return true ;
}

/******************************************************************************
Method Name:: DeleteANode

Parameters::
1- [IN] K & key
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 typename="" k="">
bool CLinkList<t,k>::DeleteANode(K &key) {
size_t len,len1;
CListNode<t,k> *prvNode;

if(0 == m_TotelElements ) {
return false ;
}
prvNode = m_pNode = m_pHead ;
len = wcslen(key);
if (len > 64)
return false;
len1 = max(len,m_pNode->len);
while(wcsncmp(m_pNode->m_key,key,len1)!=0) {
prvNode = m_pNode;
m_pNode = m_pNode->m_pNext ;
if (!m_pNode)
break;
len1 = max(len,m_pNode->len);
}
if (!m_pNode)
return false;
if (m_pHead == m_pNode)//deleteing head
{
--m_TotelElements;
m_pHead = m_pHead->m_pNext;
if(m_pNode->len)
delete m_pNode->m_key;
delete m_pNode;
}
else if (m_pNode == m_pTail){//remove tail
--m_TotelElements;
m_pTail = prvNode;
prvNode->m_pNext = NULL;
if(m_pNode->len)
delete m_pNode->m_key;
delete m_pNode;
}
else {//remove middle one
--m_TotelElements;
prvNode->m_pNext = m_pNode->m_pNext;
if(m_pNode->len)
delete m_pNode->m_key;
delete m_pNode;
}

return true ;
}

/******************************************************************************
Method Name:: Insert

Parameters::
1- [IN] T & obj
[IN] K & key
[IN] int pos
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Adds the node at the last position in the link list.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::Insert(T &obj, K &key, int pos ) {
int indx = 0;
CListNode<t,k> *prvNode;
if (pos == 0){
return AddToFirst(obj, key);
}
if (m_TotelElements >= pos){
return AddToLast(obj, key);
}
CListNode<t,k> *pNode = new CListNode<t,k> ;
if(!pNode) {
return false ;
}
pNode->len = wcslen(key);
pNode->m_key = new WCHAR [(pNode->len)+1];
if(!pNode->m_key) {
return false ;
}
wcscpy_s(pNode->m_key,(pNode->len)+1,key);
pNode->m_Node = obj ;

m_pNode = m_pHead ;
for (int i=1; i<= pos; i++){
prvNode = m_pNode;
m_pNode = m_pNode->m_pNext;
if (!m_pNode){
delete pNode->m_key;
delete pNode;
return false;
}
}
pNode->m_pNext = prvNode->m_pNext;
prvNode->m_pNext = pNode;
++m_TotelElements ;
return true ;
}



#endif
GeneralTHIS is a bad written article, but... Pin
Kochise18-May-06 2:09
MemberKochise18-May-06 2:09 
GeneralRe: THIS is a bad written article, but... Pin
Rage18-May-06 2:15
professionalRage18-May-06 2:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 18 May 2006

Stats

68.5K views
2.7K downloads
20 bookmarked