Tue Dec 24 2019

Binary Tree

C++ Programming1849 views

File Name: binary-tree.cpp

#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!
Reference:

We use cookies to improve your experience on our site and to show you personalised advertising. Please read our cookie policy and privacy policy.