Click here to Skip to main content
15,860,972 members
Articles / Desktop Programming / MFC

Binary Search Tree Template

Rate me:
Please Sign up or sign in to vote.
3.65/5 (13 votes)
18 May 2006CPOL5 min read 72.7K   2.8K   20   4
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

C++
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)


Written By
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
Member 1205037111-Oct-15 8:09 
Generalexapanded code using string Pin
Sadru23-Feb-09 20:13
Sadru23-Feb-09 20:13 
GeneralTHIS is a bad written article, but... Pin
Kochise18-May-06 2:09
Kochise18-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.