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:
Searching for any of the above values will show the path the search took to reach the entered value.
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)