5 Replies - 2939 Views - Last Post: 30 April 2014 - 06:51 PM Rate Topic: -----

#1 Jars   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 12-February 13

Binary Search Trees - Specification, Implementation, and Driver files

Posted 13 April 2014 - 02:22 PM

Before we get into this I would like to thank everyone ahead of time for there help. I haven't posted on here in a while, but I am running into some issue with this project.

Part 1. Binary Search Tree Class
Design your own BinarySearchTree class to create a binary tree that can hold values of integer data type. The class should have member functions for inserting, finding, deleting, displaying pre-, in-order, and post-order traversals. Demonstrate the class with a driver program.
Create specification file (BinarySearchTree.h), Implementation file (BinarySearchTree.cpp), and driver program (myBST.cpp).

I understand the basics of implementing binarySearchTrees but when it comes to using header files it starting to get a little tricky. So my question is, how do you pass values from the Driver file to the Implementation file? This is what I have so far. It does compile, but I have a good feeling that I will need to rewrite a decent amount of code in the Implementation file but i would like to start passing values.

#include <iostream>
#include <string.h>
#include "BinarySearchTree.h"

using namespace std;

int main(void)
{
	BinarySearchTree *theTree;
	theTree = new BinarySearchTree();

	cout <<"Building tree...\n";
	//Insert 7, 3, 10, 1, 6, 14, 4, 7, 13 to the tree
	//cretes nodes
	TreeNode one, two, three, four, five, six, seven, eight, nine;
	TreeNode *root;
	root = &one;
	//values of nodes
	one.info = 7;
	two.info= 3;
	three.info= 10;
	four.info= 1;
	five.info= 6;
	six.info= 14;
	seven.info= 4;
	eight.info= 7;
	nine.info= 13;
	//Set up of tree
	one.left = &two;
	one.right = &three;
	two.left = &four;
	two.right = &five;
	three.left = NULL;
	three.right = &six;
	four.left = NULL;
	four.right = NULL;
	five.left = &seven;
	five.right = &eight;
	six.left = &nine;
	six.right = NULL;
	seven.left = NULL;
	seven.right = NULL;
	eight.left = NULL;
	eight.right = NULL;
	nine.left = NULL;
	nine.right = NULL;

	cout <<  "Pre-order traversal looks like this:"<< endl;
	treePreeOrder(root);
	cout <<  "\nIn-Order traversal looks like this: " << endl;
	treeInOrder(root);
	cout <<  "\nPre-order traversal looks like this:" << endl;
	treePostOrder(root);

	system("pause");
	return 0;
}



#include <iostream>
#include "BinarySearchTree.h"

using namespace std;
// Default constructor
BinarySearchTree::BinarySearchTree()
{
	root = NULL;
	return;
}
bool BinarySearchTree::IsEmpty()
{
	return(root ==NULL);
}
void BinarySearchTree::Insert(TreeNode* &node, int item)
{
	if (node == NULL)
	{
		node = new TreeNode;
		node -> right = NULL;
		node -> left = NULL;
		node -> info = item;
	}
	else if (item < (node -> info))
		Insert(node -> left, item);
	else
		Insert(node -> right, item);
}
TreeNode *BinarySearchTree::SearchTree(int info)
{
	int valueInTree = false;
	TreeNode *temp;
	temp = root;

	while((temp != NULL) && (temp ->info != info))
	{
		//Search is before
		if(info < temp->info)
			temp = temp -> left;

		//Search is after
		else 
			temp = temp-> right;
	}
	//Search Not found
	if(temp ==NULL)
		return temp;		
}
void BinarySearchTree::treeDelete(int info)
{
	TreeNode *back;
	TreeNode *temp;
	TreeNode *deleteParent;
	TreeNode *deleteNode;
	temp = root;
	back = NULL;
	//Locates the Node to be deleted
	while((temp != NULL) && (info != temp->info))
    {
        back = temp;
        if(info < temp->info)
            temp = temp->left;
        else
            temp = temp->right;
    }
	// Deleting the root 
	if(temp == root) 
	{
		deleteNode = root;
		deleteParent = NULL; 
	}                
	else
	{
		deleteNode = temp;
		deleteParent = back;
	}
	Deleting node with no children or one child 
	if(deleteNode->right == NULL)
	{
        if(deleteParent == NULL)    // If deleting the root    
		{
            root = deleteNode->left;
            delete deleteNode;
		}
        else
		{
            if(deleteParent->left == deleteNode)
				deleteParent->left = deleteNode->left;
            else
                deleteParent->right = deleteNode->left;
                delete deleteNode;
		}
    }
	// There is at least one child 
    else 
	{
		if(deleteNode->left == NULL)    // Only 1 child and it is on the right
		{
			if(deleteParent == NULL)    // If deleting the root    
			{
                root = deleteNode->right;
                delete deleteNode;
			}
            else
            {
                if(deleteParent->left == deleteNode)
					deleteParent->left = deleteNode->right;
                else
					deleteParent->right = deleteNode->right;
                delete deleteNode;
            }
        }
		//Deleting node with two children 
        else 
        {
            // Find the replacement value.  Locate the node  
            // containing the largest value smaller than the 
            // key of the node being deleted.                
            temp = deleteNode->left;
            back = deleteNode;
            while(temp->right != NULL)
            {
                back = temp;
                temp = temp->right;
            }
            // Copy the replacement values into the node to be deleted 
            deleteNode->info = temp->info;
            // Remove the replacement node from the tree 
            if(back == deleteNode)
                back->left = temp->left;
            else
                back->right = temp->left;
            delete temp;
        }
}
}
void BinarySearchTree::treeInOrder(TreeNode *root)
{
	if(!root == NULL)
	{
          treeInOrder(root -> left);
		  cout << root -> info << " ";
		  treeInOrder(root -> right);
	}

}
void BinarySearchTree::treePostOrder(TreeNode *root)
{
	if(!root == NULL)
	{
		treePostOrder(root -> left);
		treePostOrder(root -> right);
		cout << root -> info << " " ;
	}
}
void BinarySearchTree::treePreOrder(TreeNode *root)
{
if(!root == NULL)
	{
		cout << root -> info << " ";
		treePreOrder(root -> left);
		treePreOrder(root -> right);
	}
}

//Spectification file for the IntStack class
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include <iostream>
using namespace std;
struct TreeNode
	{
		int info;
		TreeNode * left;
		TreeNode * right;
	};

class BinarySearchTree
{
private:
	TreeNode *root;
public:
	//Constructor
	BinarySearchTree();
	//Deconstructor
	~BinarySearchTree();
	//Operations
	void Insert(TreeNode *&node, int item);
	TreeNode *SearchTree(int info);
	void treeDelete(int info);
	void treeInOrder(TreeNode*);
	void treePreOrder(TreeNode*);
	void treePostOrder(TreeNode*);
	bool IsEmpty(); 
};
#endif


Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Trees - Specification, Implementation, and Driver files

#2 #define   User is offline

  • Duke of Err
  • member icon

Reputation: 1853
  • View blog
  • Posts: 6,671
  • Joined: 19-February 09

Re: Binary Search Trees - Specification, Implementation, and Driver files

Posted 13 April 2014 - 03:37 PM

Do you need to create the nodes yourself, cannot the tree class create them itself?
Was This Post Helpful? 1
  • +
  • -

#3 Jars   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 12-February 13

Re: Binary Search Trees - Specification, Implementation, and Driver files

Posted 13 April 2014 - 04:05 PM

View Post#define, on 13 April 2014 - 03:37 PM, said:

Do you need to create the nodes yourself, cannot the tree class create them itself?

I was actually just thinking that. Cant I just pass the values in to the class? How do you pass the value in through a pointer?
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6335
  • View blog
  • Posts: 21,747
  • Joined: 05-May 12

Re: Binary Search Trees - Specification, Implementation, and Driver files

Posted 13 April 2014 - 08:09 PM

Your tree's insert method should simply look like:
class BinaryTree
{
public:
    :
    void Insert(int value);
    :
};



So that in your main(), you would do something like:
int main()
{
    BinaryTree tree;

    tree.Insert(42);
    :
}


or
int main()
{
    BinaryTree * tree = new BinaryTree;

    tree->Insert(42);
    :

    delete tree;
    :
}


Was This Post Helpful? 1
  • +
  • -

#5 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,233
  • Joined: 14-September 07

Re: Binary Search Trees - Specification, Implementation, and Driver files

Posted 14 April 2014 - 06:55 AM

If you need further information and perhaps a visual, check out my BST post.
Was This Post Helpful? 1
  • +
  • -

#6 Jars   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 12-February 13

Re: Binary Search Trees - Specification, Implementation, and Driver files

Posted 30 April 2014 - 06:51 PM

Thank you both for the help! +Rep
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1