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:
Author:Geekboots