This implementation was done on windows with DEV-C++ 5.11 and complied against MinGW (4.9.3), it contains the following files:

BinarySearchTree.h, BinarySearchTree.cpp, Node.h,Node.cpp, main.h, main.cpp.


The program has the following number entered into a binary tree: 15, 11, 20, 16, 8, 24, 7, 12.

This results in the following structure:

binary_search_tree_structure

Searching for any of the above values will show the path the search took to reach the entered value.

binary_search_tree_output

 

 

BinarySearchTree.h

#include "Node.h"
#ifndef _BinarySearchTree_class_included
#define _BinarySearchTree_class_included
class BinarySearchTree{
	private:		
		Node* createNode(int data);
	public:
		Node* rootNode;
		Node* insertNode(Node* node, int data);
		Node* searchForNode(Node* node, int data);
		BinarySearchTree();
};
#endif

BinarySearchTree.cpp

#include "main.h"
using namespace std;

//constructor
BinarySearchTree::BinarySearchTree(){
	this->rootNode = NULL;
}

//createNode implementation
Node* BinarySearchTree::createNode(int data){
	Node* newNode = new Node();
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;	
	return newNode;
}
//insertNode implementation
Node* BinarySearchTree::insertNode(Node* node, int data){
	if(node == NULL){ //empty branch
		node = createNode(data);
	}
	else if(data <= node->data){ //if data to be inserted is equal or less than (node) insert to the left
		node->left = this->insertNode(node->left,data);		
	} else {// if data is more than the data in (node) insert on the right.
		node->right = this->insertNode(node->right,data);
	}
	return node;
}

//searchForNode implementation
Node* BinarySearchTree::searchForNode(Node* node, int data){
	if(node == NULL){
		return NULL;
	} else if(node->data == data){
		return node; //return node if the data matches
	} else if(data <= node->data ){
		return searchForNode(node->left,data);
	} else {
		return searchForNode(node->right,data);
	}	
	return NULL;// should never reach here;
}

Node.h

#ifndef _node_class_included
#define _node_class_included
class Node
{
	public:
		int data; //Node data
		Node* left; //values Less then or equal to.
		Node* right; //values greater then
		Node();
};
#endif

Node.cpp

#include "main.h"

Node::Node(void){
	this->left = NULL;
	this->right = NULL;	
}

main.h

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

main.cpp

#include "main.h"

using namespace std;
int main(int argc, char** argv) {
	BinarySearchTree* bst = new BinarySearchTree();
	bst->rootNode = bst->insertNode(bst->rootNode,15);
	bst->rootNode = bst->insertNode(bst->rootNode,11);
	bst->rootNode = bst->insertNode(bst->rootNode,20);
	bst->rootNode = bst->insertNode(bst->rootNode,16);
	int search_number;
	cout <<"Enter a number to search for:";
	cin >>search_number;
	Node* searchResult = bst->searchForNode(bst->rootNode,search_number);
	if(searchResult != NULL){
		cout <<"Found found the match:"<<searchResult<<endl;
	} else {
		cout <<"Not Found"<<endl;
	}
	
	return 0;
}

 

Download source code here -> Source(Binary_Search_Tree)

 

Leave a comment

Your email address will not be published. Required fields are marked *