Binary Search Tree Template

• Download source files - 8 Kb
• Download demo project - 1148 Kb

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.

Using the code

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 objCTreeInt ; //creating an instance of class

CTree<FLOAT> objCTreeFloat ;
CTree<MYCLASS> objCTreeMyClass ;

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> **) ;


Constraints

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

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 fro minimum of the tree or a sub tree, pass content of the root in IN prameter (see code) to find minimum of the tree.
6 - bool Maximum(T &, T & );
counterpart of Minimum.
7 - bool Successor(T &, T & );
Searches fro Successor of the tree or a sub tree, pass content of the root in IN prameter (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 incounters. 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 incounters. 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 incounters. Pass content of root to traverse complete tree.
15 - bool DeleteTree(T & ) ;
Deletes a tree or a sub tree. pass 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 fro minimum of the tree or a sub tree, pass pointer to the root in IN prameter (see code) to find minimum of the tree. Minmum is returned in OUT paramenter (see code).
19 - bool Maximum(CNode<T>* , CNode<T>** );
Counterpart of minimum.
20 - bool Successor(CNode<T>* , CNode<T>** );
Searches fro Successor of the node , pass pointer to the root in IN prameter (see code) to find Successor of the tree. Successor is returned in OUT paramenter (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 incounters. Pass 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 incounters. Pass 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 incounters. Pass pointer to root to traverse complete tree.
28 - bool DeleteTree(CNode<T>*) ;
Deletes a tree or a sub tree. pass pointer to the root to delete complete tree.
In addition the link lists which can be prepared by using methods from 22 to 26 supprors methods like
1 - bool AddToFirst(T &);
Add a node in bigning of the link list list.
2 - bool AddToLast(T &);
Add a node at last of the link list list.
3 - bool DeleteFirst();
Deletes a node from bigning of the link list list.
4 - bool DeleteLast();
Deletes a node from last of the link list list.
5 - bool GetNode(T &, CListNode<T> **) ;
Retrive pointer to a node.

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.

You must Sign In to use this message board.

FAQ    Noise Tolerance Very HighHighMediumLowVery Low   Layout Expand Posts & RepliesThread ViewNo JavascriptNo JS + Preview   Per page 102550

Msgs 1 to 3 of 3 (Total in Forum: 3) (Refresh) FirstPrevNext

exapanded code using string Sadru 21:13 23 Feb '09   #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 CListNode<t,k>::CListNode() { m_pNext = NULL ; } template CListNode<t,k>::~CListNode() { } template 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 objCLinkListInt ; //creating an instance of class CLinkList objCLinkListFloat ; CLinkList 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 **) ; Member Variables :: private :: 1 - CListNode *m_pNode ; Pointer used in varoius funtions for various operations, no specific purpose. 2 - CListNode *m_pHead ; Pointer to the first node of link list. 3 - CListNode *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 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 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 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 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 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 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 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 **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 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 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 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 Sign In·View Thread·PermaLink 2.00/5 (1 vote) THIS is a bad written article, but... Kochise 3:09 18 May '06   ...*THIS* is a nice written one : http://www.codeproject.com/cpp/BinaryTree.asp What's your implementation have to offer HatemMostafa's doesn't ? You article isn't even better documented, illustrated, explained... If you cannot follow the easy CP's article guidelines, please refrain yourself from posting. Or scrub the mess up BEFORE submission, don't plan the future on an article update. Kochise EDIT : Since you edited your article, it's kindly better. But there is room for improvements... Thanks anyway, all of this is interresting stuff. In Code we trust ! Sign In·View Thread·PermaLink 2.38/5 (7 votes) Re: THIS is a bad written article, but... Rage 3:15 18 May '06   http://www.codeproject.com/cpp/BinaryTree.asp[^] Clickety police ! Apart from that, I agrre with you. ~RaGE(); Sign In·View Thread·PermaLink 2.00/5 (4 votes)

Last Visit: 19:51 23 Nov '09     Last Update: 19:51 23 Nov '09 1