Binary Search Tree

BinarySearchTree.cpp

// BinarySearchTree.cpp : Defines the entry point for the console application.
// L.D.C.Lakmal

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

using namespace std;

typedef int element;

//bintree_node class for store nodes with values and operate their functions...
class bintree_node{
public:
	element value;
	bintree_node* left;
	bintree_node* right;
public:
	element getValue();
	void setValue(element val);
	bintree_node* getLeft();
	void setLeft(bintree_node* node);
	bintree_node* getRight();
	void setRight(bintree_node* node);
};
element bintree_node::getValue(){
	return this->value;
}
void bintree_node::setValue(element val){
	this->value = val;
}
bintree_node* bintree_node::getLeft(){
	return this->left;
}
void bintree_node::setLeft(bintree_node* node){
	this->left = node;
}
bintree_node* bintree_node::getRight(){
	return right;
}
void bintree_node::setRight(bintree_node* node){
	this->right = node;
}

//method for add node as a left child...
int add_left_child(bintree_node* parent, element value){
	bintree_node* leftNode = new bintree_node();
	leftNode->setValue(value);
	leftNode->setLeft(NULL);
	leftNode->setRight(NULL);

	if(parent->getLeft() == NULL){
		parent->setLeft(leftNode);
		return 1;
	}
	return 0;
}

//method for add node as a right child...
int add_right_child (bintree_node* parent, element value){
	bintree_node* rightNode = new bintree_node();
	rightNode->setValue(value);
	rightNode->setLeft(NULL);
	rightNode->setRight(NULL);

	if(parent->getRight() == NULL){
		parent->setRight(rightNode);
		return 1;
	}
	return 0;
}

bintree_node* create_tree(bintree_node* tree, element* elements, int size);
int add_value(bintree_node* root, element value);
element delete_value(bintree_node *&root, element value);
void make_deletion(bintree_node *&root);
bintree_node* search_value(bintree_node* root, element value);
void traverse_inOrder(bintree_node* root);
void traverse_preOrder(bintree_node* root);
void traverse_postOrder(bintree_node* root);

void main(){
	bintree_node* tree = new bintree_node();
	tree->setValue(50);
	tree->setLeft(NULL);
	tree->setRight(NULL);

	element arr[17] = {20,70,10,25,60,80,5,12,23,40,65,7,11,21,24,35,45};
	create_tree(tree, arr, 17);

	cout << "In order traversal : ";
	traverse_inOrder(tree);
	cout << endl << "Pre order traversal : ";
	traverse_preOrder(tree);
	cout << endl << "Post order traversal : ";
	traverse_postOrder(tree);
	cout << endl << endl;

	cout << "Find the node with value 10 : " << endl;
	bintree_node* find = search_value(tree, 10);
	cout << find->getValue() << " found !";
	cout << endl << endl;

	cout << "Delete the node with value 65 : " << endl;
	delete_value(tree, 65);
	cout << "In order traversal : ";
	traverse_inOrder(tree);
	cout << endl << endl;

	cout << "Delete the node with value 5 : " << endl;
	delete_value(tree, 5);
	cout << "In order traversal : ";
	traverse_inOrder(tree);
	cout << endl << endl;

	cout << "Delete the node with value 20 : " << endl;
	delete_value(tree, 20);
	cout << "In order traversal : ";
	traverse_inOrder(tree);
	cout << endl << endl;

	system("PAUSE");
}

//method for create tree with the given set of values...
bintree_node* create_tree(bintree_node* tree, element* elements, int size){
	for(int i=0; i<size; i++){
		add_value(tree, elements[i]);
	}
	return tree;
}

//method for insert a node to the relavant place of the tree...
int add_value(bintree_node* root, element value){
	if(root->getValue() == value){
		return -1;
	}else if(root->getValue() < value){
		if(root->getRight() == NULL){
			add_right_child(root, value);
		}else{
			add_value(root->getRight(), value);
		}
	}else{
		if(root->getLeft() == NULL){
			add_left_child(root, value);
		}else{
			add_value(root->getLeft(), value);
		}
	}
	return 1;
}

//method for delete a value of the tree...
element delete_value(bintree_node *&root, element value){
	if(root == NULL){
		return -1;
	}else if(root->getValue() < value){
		return delete_value(root->right, value);
	}else if(root->getValue() > value){
		return delete_value(root->left, value);
	}else{
		make_deletion(root);
	}
	return 1;
}

//method for make deletion and reset the tree...
void make_deletion(bintree_node *&root){
	bintree_node* temp;
	if (root == NULL){
		cout << "Cannot delete empty node.\n";
	}else if (root->getRight() == NULL){
		temp = root;
		root = root->getLeft();
		delete temp;
	}else if (root->getLeft() == NULL){
		temp = root;
		root = root->getRight();
		delete temp;
	}else{
		temp = root->getRight();
		while (temp->getLeft())
			temp = temp->getLeft();
		temp->setLeft(root->getLeft());
		temp = root;
		root = root->getRight();
		delete temp;
	}
}

//method for search a value of the tree...
bintree_node* search_value(bintree_node* root, element value){
	if(root == NULL){
		return NULL;
	}else if(root->getValue() == value){
		return root;
	}else if(root->getValue() < value){
		return search_value(root->getRight(), value);
	}else{
		return search_value(root->getLeft(), value);
	}
}

//method for in-order traversal of the tree...
void traverse_inOrder(bintree_node* root){
	if (root == NULL)
		return;
	traverse_inOrder(root->getLeft());
	cout << root->getValue() <<  " ";
	traverse_inOrder(root->getRight());
}

//method for pre-order traversal of the tree...
void traverse_preOrder(bintree_node* root){
	if (root == NULL)
		return;
	cout << root->getValue() << " ";
	traverse_preOrder(root->getLeft());
	traverse_preOrder(root->getRight());
}

//method for post-order traversal of the tree...
void traverse_postOrder(bintree_node* root){
	if (root == NULL)
		return;
	traverse_postOrder(root->getLeft());
	traverse_postOrder(root->getRight());
	cout << root->getValue() << " ";
}