GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
Reload this Page Binary Search Tree Verification Help
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 13-Oct-2008, 07:12
Peter_APIIT Peter_APIIT is offline
Regular Member
  
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Binary Search Tree Verification Help

Hello to all expect software engineer, i have create a binary search
tree.

I know to know what is your opinion about my program.

CPP / C++ / C Code:
template <typename T>
class treeNode
{
public:

        T key;
        T value;

        treeNode<T> *leftNode;
        treeNode<T> *rightNode;

        treeNode() : key(T()), value(T()),
                leftNode(0),
                rightNode(0)
        {}

        treeNode(const T& aKey) : key(aKey),
                value(T()),
                leftNode(0),
                rightNode(0)
        {}

        treeNode(const T& aKey, const T& aValue)
                : key(aKey),
                value(aValue),
                leftNode(0),
                rightNode(0)
        {}

        ~treeNode()
        {

        }

};

template <typename T>
class BSearchTree
{
private:

        treeNode<T>* root;

public:
        BSearchTree<T>()
                : root(0)
        {
        }

        ~BSearchTree()
        {
                if (root != 0)
                {
                        destroy();
                }
        }

        void Insert(const T& key, const T& value)
        {
                if (root != 0)
                {
                        treeNode<T>* newNode = new treeNode<T>(key, value);
                        treeNode<T>* iteratorNode = root;

                        while(iteratorNode->leftNode != 0
                                || iteratorNode->rightNode != 0)
                        {
                                if (key < iteratorNode->key)
                                {
                                        iteratorNode = iteratorNode->leftNode;
                                }
                                else
                                {
                                        iteratorNode = iteratorNode->rightNode;
                                }
                        }

                        if (key < iteratorNode->key)
                        {
                                iteratorNode->leftNode = newNode;
                        }
                        else
                        {
                                iteratorNode->rightNode = newNode;
                        }
                }
                else
                {
                        treeNode<T>* newNode = new treeNode<T>(key, value);
                        treeNode<T>* iteratorNode = root;

                        root = newNode;
                }

        }

        void Remove(T& key)
        {
        }

        void destroy()
        {
                treeNode<T>* iteratorNode = root;

        }

        void RecursivePreOrder(treeNode<T>* aTreeNode)const
        {
                if (aTreeNode != 0)
                {
                        cout << "Key is " << aTreeNode->key << "\n";
                        cout << "Value is " << aTreeNode->value << "\n";

                        if (aTreeNode->leftNode != 0)
                        {
                                RecursivePreOrder(aTreeNode->leftNode);
                        }

                        if (aTreeNode->rightNode != 0)
                        {
                                RecursivePreOrder(aTreeNode->rightNode);
                        }
                }

        }

        // Root->Left->Right
        void PreOrderDisplay()const
        {
                if (root != 0)
                {
                        cout << "Pre Order Display \n";
                        RecursivePreOrder(this->root);
                }
        }

        void RecursiveInOrder(treeNode<T>* aTreeNode)const
        {
                if (aTreeNode != 0)
                {
                        if (aTreeNode->leftNode != 0)
                        {
                                RecursiveInOrder(aTreeNode->leftNode);
                        }

                        cout << "Key is " << aTreeNode->key << "\n";
                        cout << "Value is " << aTreeNode->value << "\n";

                        if (aTreeNode->rightNode != 0)
                        {
                                RecursiveInOrder(aTreeNode->rightNode);
                        }
                }

        }

        // Left->Root->Right
        void InOrderDisplay()const
        {
                if (root != 0)
                {
                        cout << "In Order Display \n";
                        RecursiveInOrder(this->root);
                }
        }

        void RecursivePostOrder(treeNode<T>* aTreeNode)const
        {
                if (aTreeNode != 0)
                {
                        if (aTreeNode->leftNode != 0)
                        {
                                RecursivePostOrder(aTreeNode->leftNode);
                        }

                        if (aTreeNode->rightNode != 0)
                        {
                                RecursivePostOrder(aTreeNode->rightNode);
                        }

                        cout << "Key is " << aTreeNode->key << "\n";
                        cout << "Value is " << aTreeNode->value << "\n";

                }

        }

        // Left->Right->Root
        void PostOrderDisplay()const
        {
                if (root != 0)
                {
                        cout << "Post Order Display \n";
                        RecursivePostOrder(this->root);
                }
        }

};

I wonder does something wrong with my code.
Another question how i can improve encapsulation by private the treeNode but BSearchTree is unable to access it.

What method to solve it ?


Thanks for your help.
Last edited by LuciWiz : 13-Oct-2008 at 08:38. Reason: Please insert your C++ code between [cpp] & [/cpp] tags
  #2  
Old 13-Oct-2008, 21:58
L7Sqr L7Sqr is offline
Member
  
Join Date: Jul 2005
Location: constant limbo
Posts: 234
L7Sqr is a jewel in the roughL7Sqr is a jewel in the rough

Re: Binary Search Tree Verification Help

I dont know about binary search trees, but this function is really helpful in genetic programming.
__________________
My personal site: Utilities for text processing, debugging, testing and plotting
  #3  
Old 15-Oct-2008, 02:15
Peter_APIIT Peter_APIIT is offline
Regular Member
  
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Re: Binary Search Tree Verification Help

Any one who expect in this ?

Thanks.
  #4  
Old 15-Oct-2008, 11:10
Howard_L Howard_L is offline
Regular Member
  
Join Date: Apr 2007
Location: Maryland/PA, USA
Posts: 803
Howard_L is a jewel in the roughHoward_L is a jewel in the roughHoward_L is a jewel in the rough

Re: Binary Search Tree Verification Help

Do you mean has anybody looked at this?
I did, it's pretty neat. I don't really feel qualified to say much as I barely understand templates at this point. BUT I was able to put together a main() to make some calls and added some prints to help illustrate the mechanics. Maybe this ready-to-run example will be of more interest to others (something to consider in future postings):
CPP / C++ / C Code:
#include <iostream> 
using namespace std;
    
template <typename T>
class treeNode
{
public:
  T key;
  T value;
    
  treeNode<T> *leftNode;
  treeNode<T> *rightNode;

  treeNode() : key(T()), value(T()),
    leftNode(0),
    rightNode(0)
  {}

  treeNode(const T& aKey) : key(aKey),
    value(T()),
    leftNode(0),
    rightNode(0)
  {}
  
  treeNode(const T& aKey, const T& aValue)
    : key(aKey),
    value(aValue),
    leftNode(0),
    rightNode(0)
  {}

  ~treeNode()
  {
  } 
};  

template <typename T>
class BSearchTree
{
private:
  
  treeNode<T>* root;

public:
  BSearchTree<T>()
    : root(0)
  {
  }

  ~BSearchTree()
  {
    if (root != 0)
    {
      destroy();
    }
  }

  void Insert(const T& key, const T& value)
  {
    cout <<"\ninsert1  :          key= "<< key <<"           value= "<< value <<"     root= "<< root << endl;
    if (root != 0)
    {
      treeNode<T>* newNode = new treeNode<T>(key, value);
      treeNode<T>* iteratorNode = root;

      while(iteratorNode->leftNode != 0
         || iteratorNode->rightNode != 0)
      {
        if (key < iteratorNode->key)
        {
          iteratorNode = iteratorNode->leftNode;
        }
        else
        {
          iteratorNode = iteratorNode->rightNode;
        }
      }

      if (key < iteratorNode->key)
      {
        iteratorNode->leftNode = newNode;
      }
      else
      {
        iteratorNode->rightNode = newNode;
      }
      cout << " insert2b: newNode->key= " << newNode->key <<"  newNode->value= " << newNode->value <<"  newNode= "<< newNode << endl;

    }
    else
    {
      treeNode<T>* newNode = new treeNode<T>(key, value);
      //treeNode<T>* iteratorNode = root;
      //cout <<"\nWARNING 1: in Insert(): unused var:iteratorNode here: "<< iteratorNode <<endl;
      root = newNode;
      cout << " insert2a:    root->key= "<< root->key <<"     root->value= "<< root->value <<" new root= "<< root << endl;
    }
  }

  void Remove(T& key)
  {
  }

  void destroy()
  {
    treeNode<T>* iteratorNode = root;
    cout <<"\nWARNING 2:  in destroy(): unused var: iteratorNode here: "<< iteratorNode <<endl;
  }

  void RecursivePreOrder(treeNode<T>* aTreeNode)const
  {
    if (aTreeNode != 0)
    {
      cout << "  Key is: " << aTreeNode->key ;
      cout << "    Value is " << aTreeNode->value << "\n";
      if (aTreeNode->leftNode != 0)
      {
         RecursivePreOrder(aTreeNode->leftNode);
      }
      if (aTreeNode->rightNode != 0)
      {
        RecursivePreOrder(aTreeNode->rightNode);
      }
    }
  }

  // Root->Left->Right
  void PreOrderDisplay()const
  {
    if (root != 0)
    {
      cout << "\nPre Order Display  \n";
      RecursivePreOrder(this->root);
    }
  }

  void RecursiveInOrder(treeNode<T>* aTreeNode)const
  {
    if (aTreeNode != 0)
    {
      if (aTreeNode->leftNode != 0)
      {
        RecursiveInOrder(aTreeNode->leftNode);
      }
      cout << "  Key is: " << aTreeNode->key ;
      cout << "    Value is " << aTreeNode->value << "\n";

      if (aTreeNode->rightNode != 0)
      {
        RecursiveInOrder(aTreeNode->rightNode);
      }
    }
  }

  // Left->Root->Right
  void InOrderDisplay()const
  {
    if (root != 0)
    {
       cout << "\nIn Order Display  \n";
       RecursiveInOrder(this->root);
    }
  }

  void RecursivePostOrder(treeNode<T>* aTreeNode)const
  {
    if (aTreeNode != 0)
    {
      if (aTreeNode->leftNode != 0)
      {
        RecursivePostOrder(aTreeNode->leftNode);
      }

      if (aTreeNode->rightNode != 0)
      {
        RecursivePostOrder(aTreeNode->rightNode);
      }
      cout << "  Key is: " << aTreeNode->key ;
      cout << "    Value is " << aTreeNode->value << "\n";
    }
  }

  // Left->Right->Root
  void PostOrderDisplay()const
  {
    if (root != 0)
    {
      cout << "Post Order Display \n";
      RecursivePostOrder(this->root);
    }
  }
};  /*  end of class BSearchTree  */


int main(void)
{
  BSearchTree <int> list;
  //BSearchTree <char[50]> list2;
  BSearchTree <string> list2;
  list.Insert(1 , 100);
  list.Insert(6 , 600);
  list.Insert(5 , 500);

  list.PreOrderDisplay();
  list.InOrderDisplay();

  list2.Insert("color" , "red");
  list2.Insert("calor" , "blue");
  list2.Insert("cilor" , "black");

  list2.PreOrderDisplay();
  list2.InOrderDisplay();



  return  0;
}
Like I said the main() is minimal. I don't know much about this but I learn by working through things like that. Thanks
I got a couple of warnings about unused variable which I noted in the above.
One of those unused was in a destructor... which made me curious, don't you need to destroy all allocated space? Maybe I just don't see it yet... anyhow , pretty neat!
  #5  
Old 17-Oct-2008, 05:06
Peter_APIIT Peter_APIIT is offline
Regular Member
  
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Re: Binary Search Tree Verification Help

By the way, this is my latest code.

CPP / C++ / C Code:
#ifndef BST
#define BST

#include "TreeNode.h"

#ifdef WIN32

template <typename T>
class BSearchTree
{
private:
	
	treeNode<T>* root;

public:
	BSearchTree<T>();
	
	~BSearchTree();

	void Insert(const T&, const T&);
	void Remove(const T&);
	
	void destroy()const;
	void PostOrderDestroy(treeNode<T>*)const;

	// Root->Left->Right
	void PreOrder()const;	
	void RecursivePreOrder(treeNode<T>*)const;

	// Left->Root->Right
	void InOrder()const;
	void RecursiveInOrder(treeNode<T>*)const;

	// Left->Right->Root
	void PostOrder()const;
	void RecursivePostOrder(treeNode<T>*)const;
	
	treeNode<T>* InsertSearch(treeNode<T>*, const T&); 

	void display(treeNode<T>*)const;
	
};

// ================================================
template <typename T>
BSearchTree<T>::BSearchTree() : root(0)
{
}
// ================================================
template <typename T>
BSearchTree<T>::~BSearchTree()
{
	if (root != 0)
	{
		destroy();
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::Insert(const T &key, const T &value)
{
	if (root != 0)
	{
		treeNode<T>* newNode = new treeNode<T>(key, value);
		treeNode<T>* iteratorNode = root;

		iteratorNode = InsertSearch(this->root, key);

		if (key < iteratorNode->key)
		{
			iteratorNode->leftNode = newNode;
		}
		else
		{
			iteratorNode->rightNode = newNode;
		}
	}
	else
	{
		treeNode<T>* newNode = new treeNode<T>(key, value);
		root = newNode;
	}

/*
	Top Down construction - Create root first
	Bottom Up construction - Create child first
*/
}
// ================================================
template <typename T>
void BSearchTree<T>::Remove(const T &key)
{
	/*
		if no child, just delete
		if one child, point by grandparent
		
		if two children, swap with it with 
		inorder-successor
		(Left child of right sub Tree)	
		
		Smallest in right sub tree
		Traverse once to right , then continue
		traverse to left  
		
		or inorder-predecessor
		(Right child of Left sub Tree)
		Largest in left sub tree
	*/
	if (root != 0 && (root->leftNode != 0 
		&& root->rightNode != 0))
	{
		treeNode<T>* iteratorNode = root;
		treeNode<T>* parentRemoveNode = root;

		while (iteratorNode->key != key
			&& (iteratorNode->leftNode != 0 
			|| iteratorNode->rightNode != 0))
		{
			if (key < iteratorNode->key)
			{
				(iteratorNode->leftNode != 0)
					? iteratorNode = iteratorNode->leftNode
					: iteratorNode;
				
				(iteratorNode->key != key) 
					? parentRemoveNode = parentRemoveNode->leftNode 
					:  parentRemoveNode;
			}
			else
			{
				(iteratorNode->rightNode != 0)
					? iteratorNode = iteratorNode->rightNode
					: iteratorNode; 

				(iteratorNode->key != key) 
					? parentRemoveNode = parentRemoveNode->rightNode
					: parentRemoveNode;			
			}
		}

		if (iteratorNode->key == key)
		{
			// Key is equal root's key/remove root
			if (this->root->key == key 
				|| root->key == iteratorNode->key)
			{
				treeNode<T>* iteratorNode = root;
				treeNode<T>* tempRightNode = root;
				treeNode<T>* previousLeftNode = root->leftNode;

				// root got right node
				if (iteratorNode->rightNode != 0)
				{
					iteratorNode = iteratorNode->rightNode;
					tempRightNode = iteratorNode->rightNode;

					if (iteratorNode->leftNode != 0)
					{
						while (iteratorNode->leftNode != 0)
						{	
							iteratorNode = iteratorNode->leftNode;
						}
					}
					
					treeNode<T>* newRoot = iteratorNode;
					treeNode<T>* removeNode = root;

					root = newRoot;
					root->leftNode = previousLeftNode;
					root->rightNode = tempRightNode;

					delete removeNode;
				
				}// root no right node
				else
				{
					treeNode<T>* removeNode = root;
					treeNode<T>* newRoot = root;

					if (root->leftNode != 0)
					{
						newRoot = root->leftNode;
						root->leftNode = newRoot;
					}
					delete removeNode;
				}

			} // remove child
			else
			{
				// two children
				if (iteratorNode->leftNode != 0
					&& iteratorNode->rightNode != 0)
				{
					treeNode<T>* removeNode = iteratorNode;
					treeNode<T>* tempLeftNode = iteratorNode->leftNode;

					iteratorNode = iteratorNode->rightNode;
					while(iteratorNode->leftNode != 0)
					{
						iteratorNode = iteratorNode->leftNode;
					}

					if (parentRemoveNode->key 
						> iteratorNode->key)
					{
						parentRemoveNode->leftNode = iteratorNode;
					}
					else
					{
						parentRemoveNode->rightNode = iteratorNode;
					}
					
					iteratorNode->leftNode = tempLeftNode;
			
					delete removeNode;
				}
				// one children
				else if ((iteratorNode->leftNode != 0
					&& iteratorNode->rightNode == 0) 
					|| (iteratorNode->leftNode == 0
					&& iteratorNode->rightNode != 0))
				{
					if (iteratorNode->leftNode != 0
						&& iteratorNode->rightNode == 0)
					{
						treeNode<T>* removeNode = iteratorNode;
						treeNode<T>* nextNode = iteratorNode->leftNode;
						
						parentRemoveNode->leftNode = nextNode;
						delete removeNode;
					}
					else
					{
						treeNode<T>* removeNode = iteratorNode;
						treeNode<T>* nextNode = iteratorNode->rightNode;
						
						parentRemoveNode->rightNode = nextNode;
						delete removeNode;
					}
					
				}
				// no children
				else if (iteratorNode->leftNode == 0
					&& iteratorNode->rightNode == 0)
				{
					if (parentRemoveNode->leftNode 
						== iteratorNode)
					{
						parentRemoveNode->leftNode = 0;
					}
					else
					{
						parentRemoveNode->rightNode = 0;
					}

					delete iteratorNode;
				}
			}
		}
		else
		{
			cout << "\nKey Node not found\n";
		}
		
	}
	else
	{
		cout << "\nRoot no child";
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::destroy() const
{
	PostOrderDestroy(this->root);
}
// ================================================
template <typename T>
void BSearchTree<T>::PostOrderDestroy(treeNode<T> *aTreeNode) const
{
	if (aTreeNode != 0)
	{
		if (aTreeNode->leftNode != 0)
		{
			PostOrderDestroy(aTreeNode->leftNode);
		}

		if (aTreeNode->rightNode != 0)
		{
			PostOrderDestroy(aTreeNode->rightNode);
		}

		delete aTreeNode;
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::PreOrder() const
{
	if (root != 0)
	{
		cout << "Pre Order Display \n";
		RecursivePreOrder(this->root);
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::RecursivePreOrder(treeNode<T> *aTreeNode) const
{
	if (aTreeNode != 0)
	{
		display(aTreeNode);

		if (aTreeNode->leftNode != 0)
		{
			RecursivePreOrder(aTreeNode->leftNode);
		}
		
		if (aTreeNode->rightNode != 0)
		{
			RecursivePreOrder(aTreeNode->rightNode);
		}
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::InOrder() const
{
	if (root != 0)
	{
		cout << "In Order Display \n";
		RecursiveInOrder(this->root);
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::RecursiveInOrder(treeNode<T> *aTreeNode) const
{
	if (aTreeNode != 0)
	{
		if (aTreeNode->leftNode != 0)
		{
			RecursiveInOrder(aTreeNode->leftNode);
		}

		display(aTreeNode);
		
		if (aTreeNode->rightNode != 0)
		{
			RecursiveInOrder(aTreeNode->rightNode);
		}
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::PostOrder() const
{
	if (root != 0)
	{
		cout << "Post Order Display \n";
		RecursivePostOrder(this->root);
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::RecursivePostOrder(treeNode<T> *aTreeNode) const
{
	if (aTreeNode != 0)
	{
		if (aTreeNode->leftNode != 0)
		{
			RecursivePostOrder(aTreeNode->leftNode);
		}
		
		if (aTreeNode->rightNode != 0)
		{
			RecursivePostOrder(aTreeNode->rightNode);
		}

		display(aTreeNode);
	}
}
// ================================================
template <typename T>
treeNode<T>* BSearchTree<T>::InsertSearch(treeNode<T> *iteratorNode,
									 const T& key)
{
	if (iteratorNode != 0)
	{
		if (key < iteratorNode->key)
		{
			if (iteratorNode->leftNode != 0)
			{
				return InsertSearch(iteratorNode->leftNode, key);
			}
		}
		else
		{
			if (iteratorNode->rightNode != 0)
			{
				return InsertSearch(iteratorNode->rightNode, key);
			}
		}
	}
}
// ================================================
template <typename T>
void BSearchTree<T>::display(treeNode<T>* aTreeNode) const
{
	cout << "Key is " << aTreeNode->key << "\n";
	cout << "Value is " << aTreeNode->value << "\n";
}

// ================================================

// ================================================



// ================================================



// ================================================




#else


#endif



#endif






#ifndef TreeNode
#define TreeNode


#ifdef WIN32
// Windows Function 

	
template <typename T>
class treeNode
{
public:

	T key;
	T value;

	treeNode<T> *leftNode;
	treeNode<T> *rightNode;


	treeNode() : key(T()), value(T()), 
		leftNode(0), 
		rightNode(0)
	{}

	treeNode(const T& aKey) : key(aKey), 
		value(T()), 
		leftNode(0), 
		rightNode(0) 
	{}

	treeNode(const T& aKey, const T& aValue) 
		: key(aKey), 
		value(aValue), 
		leftNode(0), 
		rightNode(0) 
	{}

	~treeNode()
	{
		
	}
};


#else
	// POSIX Function


#endif



#endif



#include<iostream>
#include<iomanip>
#include<ios>
#include<string>


#include "TreeNode.h"
#include "BST.h"

using std::cout;
using std::cin;
using std::string;



// ================================================
int main()
{
	BSearchTree<int> mytree;

	mytree.Insert(7, 70);
	mytree.Insert(1, 10);
	mytree.Insert(2, 20);
	mytree.Insert(0, 0);
	mytree.Insert(3, 30);
	mytree.Insert(8, 80);
	mytree.Insert(5, 50);
	mytree.Insert(4, 40);	
	mytree.Insert(6, 60);

	mytree.Insert(40, 400);
	mytree.Insert(50, 500);
	mytree.Insert(60, 600);
	mytree.Insert(70, 700);
	mytree.Insert(10, 100);
	mytree.Insert(20, 200);
	mytree.Insert(9, 90);
	
	cout << "\n\n\n\n";
	mytree.PreOrder();

	cout << "\n\nAfter Remove 7 :";
	mytree.Remove(7);

	cout << "\n\n\n\n";
	mytree.PreOrder();


	




	return 0;
}


What is your opinion about my latest program ?

Have fun with it.
 
 
« Previous Thread | Next Thread »

Recent GIDBlogProblems with the Navy (Chiefs) by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Link List In C Peter_APIIT C Programming Language 33 12-Jun-2008 14:33
Deleting a node from binary search tree earachefl C++ Forum 3 28-Jun-2006 08:26
can anyone help me with my tree :) bioeng_mtm C++ Forum 5 22-Apr-2006 13:50
Binary Search Tree in C++ rpg3 C++ Forum 5 02-Apr-2006 10:53
Search Engine Positioning 101 and 201 "How To" Tips... 000 Search Engine Optimization Forum 0 29-May-2003 11:34

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 01:28.

Contact Us - GIDForums™ - Archive - Top

vBulletin, Copyright © 2000 - 2009, Jelsoft Enterprises Ltd.