Binary Tree

C++ Programming

C++ Programming Examples

#include<iostream>
using namespace std;

/* Tree structure */
struct tree {
	int data;
	tree *left;
	tree *right;
};

class btree {
	private:
		void destroy_tree(tree *leaf) {
			if(leaf != NULL) {
				destroy_tree(leaf->left);
				destroy_tree(leaf->right);
				delete leaf;
			}
		}

		void insert(int key, tree *leaf) {
			if(key < leaf->data) {
				if(leaf->left != NULL) 
					insert(key, leaf->left);
				else {
					leaf->left = new tree;
					leaf->left->data = key;

					/* Sets the left child of the child node to null */
					leaf->left->left = NULL;

					/* Sets the right child of the child node to null */
					leaf->left->right = NULL;
				}  
			}
			else if(key>=leaf->data) {
				if(leaf->right!=NULL)
					insert(key, leaf->right);
				else {
					leaf->right = new tree;
					leaf->right->data = key;

					/* Sets the left child of the child node to null */
					leaf->right->left = NULL;

					/* Sets the right child of the child node to null */
					leaf->right->right = NULL; 
				}
			}
		}

		tree *search(int key, tree *leaf) {
			if(leaf != NULL) {
				if(key == leaf->data)
					return leaf;
				if(key < leaf->data)
					return search(key, leaf->left);
				else
					return search(key, leaf->right);
			}
			else
				return NULL;
		}

	public:
		tree *root;

		/* Constructor */
		btree() {
			root = NULL;
		}

		/* Destructor */
		~btree() {
			destroy_tree();
		}

		/* Function for Insert data into the Tree */
		void insert(int value) {
			if(root != NULL)
				insert(value, root);
			else {
				root = new tree;
				root->data = value;
				root->left = NULL;
				root->right = NULL;
			}
		}

		/* Function for Search data from the Tree */
		void search(int value) {
			if(search(value, root) == NULL)
				cout << "Not Found!" << endl;
			else
				cout << "Data Found!" << endl;
		}		
	
		/* Function for Destroy Tree */
		void destroy_tree() {
			destroy_tree(root);
		}

		/* Function for find minimum value from the Tree */
		tree *minvalue(struct tree *leaf) {
			if(leaf == NULL)
				return NULL;

			/* Go to the left sub tree to find the min element */
			if(leaf->left)
				return minvalue(leaf->left);
			else
				return leaf;
		}

		/* Function for find maximum value from the Tree */
		tree *maxvalue(struct tree *leaf) {
			if(leaf == NULL)
				return NULL;

			/* Go to the left sub tree to find the max element */
			if(leaf->right)
				return maxvalue(leaf->right);
			else
				return leaf;
		}

		/* Function for print binary tree in Preorder format */
		void preorder(struct tree *leaf) {
			if(leaf == NULL)
				return;
			cout << leaf->data << endl;
			preorder(leaf->left);
			preorder(leaf->right);
		}

		/* Function for print binary tree in Inorder format */
		void inorder(struct tree *leaf) {
			if(leaf == NULL)
				return;
			preorder(leaf->left);
			cout << leaf->data << endl;
			preorder(leaf->right);
		}

		/* Function for print binary tree in Postorder format */
		void postorder(struct tree *leaf) {
			if(leaf == NULL)
				return;
			preorder(leaf->left);
			preorder(leaf->right);
			cout << leaf->data << endl;
		}
};

int main() {
	int key, choice;
	btree bt = btree();
	while(choice != 7) {
		cout << "\n1. Insert\n2. Search\n3. Destroy\n4. Display\n5. Min Value\n6. Max Value\n7. Exit" << endl;
		cout << "Enter your choice:" << endl;
		cin >> choice;
		switch(choice) {
			case 1:
				cout << "Enter the value to insert:" << endl;
				cin >> key;
				bt.insert(key);
				cout << "Data inserted!" << endl;
				break;
			case 2:
				cout << "Enter the value to search:" << endl;
				cin >> key;
				bt.search(key);
				break;
			case 3:
				bt.destroy_tree();
				cout << "Tree Destroyed!" << endl;
				break;
			case 4:
				cout << "Preorder:" << endl;
				bt.preorder(bt.root);
				cout << "Inorder:" << endl;
				bt.inorder(bt.root);
				cout << "Postorder:" << endl;
				bt.postorder(bt.root);
				break;
			case 5:
				if(bt.minvalue(bt.root) == NULL)
					cout << "Tree is empty!" << endl;
				else
					cout << "Minimum value is " << bt.minvalue(bt.root)->data << endl;
				break;
			case 6:
				if(bt.maxvalue(bt.root) == NULL)
					cout << "Tree is empty!" << endl;
				else
					cout << "Maximum value is " << bt.maxvalue(bt.root)->data << endl;
				break;
			case 7:
				cout << "Bye Bye!" << endl;
				return 0;
				break;
			default:
				cout << "Invalid choice!" << endl;
		}
	}
	return 0;
}


          /****** Output ******/
          

1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


1


Enter the value to insert:


5


Data Inserted!




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


1


Enter the value to insert:


3


Data Inserted!




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


1


Enter the value to insert:


6


Data Inserted!




1. Insert

2. Search

3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


1


Enter the value to insert:


2


Data Inserted!




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


1


Enter the value to insert:


7


Data Inserted!




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


2


Enter the value to search:


2


Data found!




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


4


Preorder:


5


3


2


6


7


Inorder:


2


3


5


6


7


Postorder:


2


3


7


6


5




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


5


Minimum value is 2




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


6


Maximum value is 7




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


3


Tree Destroyed!




1. Insert


2. Search


3. Destroy


4. Display


5. Min Value


6. Max Value


7. Exit


Enter your choice:


7


Bye Bye!

Learn more about Binary Tree