binary search tree in cpp using class

Solutions on MaxInterview for binary search tree in cpp using class by the best coders in the world

showing results for - "binary search tree in cpp using class"
Maya
14 Sep 2020
1/* Program to implement Binary Search Tree in c++ using classes  */
2#include<iostream>
3#include<stdlib.h>
4#include<cstdlib>
5using namespace std;
6
7struct Node {
8    int data;
9    Node* left;
10    Node* right;
11};
12
13class BinaryTree {
14    private:
15        struct Node* root;
16    public:
17        BinaryTree() {
18            root = NULL;
19        }
20        Node* createNode(int);
21        Node* insertNode(Node*, int);
22        Node* deleteNode(Node*, int);
23        void inOrder(Node*);
24        void preOrder(Node*);
25        void postOrder(Node*);
26        Node* findMinimum(Node*);
27
28        Node* getRoot() {
29            return root;
30        }
31
32        void setRoot(Node* ptr) {
33            root = ptr; 
34        }
35};
36
37Node* BinaryTree :: createNode(int n) {
38    Node* newNode = new struct Node();
39    newNode->data = n;
40    newNode->left = NULL;
41    newNode->right = NULL;
42    return newNode; 
43}
44
45
46Node* BinaryTree :: findMinimum(Node* rootPtr) {
47    while(rootPtr->left != NULL) {
48        rootPtr = rootPtr->left;
49    }
50    return rootPtr;
51}
52
53
54Node* BinaryTree :: insertNode(Node* rootPtr, int n) {
55    if(rootPtr == NULL) {
56        return createNode(n);
57    }
58    if(n < rootPtr->data) {
59        rootPtr->left = insertNode(rootPtr->left, n);
60    }
61    if(n > rootPtr->data) {
62        rootPtr->right = insertNode(rootPtr->right, n);
63    }
64    return rootPtr;
65}
66
67
68Node* BinaryTree :: deleteNode(Node* rootPtr, int n) {
69    if(rootPtr == NULL) {
70        cout<<"Node to be deleted is not present.!"<<endl;
71        return rootPtr;
72    }
73    else if(n < rootPtr->data) {
74        rootPtr->left = deleteNode(rootPtr->left, n);
75    } else if(n > rootPtr->data) {
76        rootPtr->right = deleteNode(rootPtr->right, n);
77    } else {
78        if(rootPtr->left == NULL && rootPtr->right == NULL) {
79            delete rootPtr;
80            rootPtr = NULL;
81        }
82        else if(root->left == NULL) {
83            struct Node* temp = rootPtr;
84            rootPtr = rootPtr->right;
85            delete temp;
86        }
87        else if(rootPtr->right == NULL) {
88            struct Node* temp = rootPtr;
89            rootPtr = rootPtr->left;
90            delete temp;
91        } else {
92            Node* temp = findMinimum(rootPtr->right);
93            rootPtr->data = temp->data;
94            rootPtr->left = deleteNode(rootPtr->right, temp->data);
95        }
96    }
97
98    return rootPtr;
99}
100
101
102void BinaryTree :: inOrder(Node* root) {
103    if(root == NULL) {
104        return;
105    }
106    inOrder(root->left);
107    cout<<root->data<<"\t";
108    inOrder(root->right);
109}
110
111void BinaryTree :: preOrder(Node* root) {
112    if(root == NULL) return;
113    cout<<root->data<<"\t";
114    preOrder(root->left);
115    preOrder(root->right);
116}
117
118void BinaryTree :: postOrder(Node* root) {
119    if(root == NULL) return;
120    postOrder(root->left);
121    postOrder(root->right);
122    cout<<root->data<<"\t";
123}
124
125int main() {
126    BinaryTree l1;
127    int ch, ele, res;
128    Node* ptr;
129    do {
130            cout<<"1 - Insert Node\n";
131            cout<<"2 - IN-ORDER Traversal\n";
132            cout<<"3 - PRE-ORDER Traversal\n";
133            cout<<"4 - POST-ORDER Traversal\n";
134            cout<<"Enter choice\n";
135            cin>>ch;
136            switch(ch) {
137                case 1: 
138                    cout<<"Entre element to insert to the List\n";
139                    cin>>ele;
140
141                    ptr = l1.insertNode(l1.getRoot(), ele);
142  
143                    l1.setRoot(ptr);
144                    break;
145                case 2:
146                    cout<<"---IN-ORDER TRAVERSAL---"<<endl;
147                    l1.inOrder(l1.getRoot());
148                    cout<<endl;
149                    break;
150                case 3:
151                    cout<<"---PRE-ORDER TRAVERSAL---"<<endl;
152                    l1.preOrder(l1.getRoot());
153                    cout<<endl;
154                    break;
155                case 4:
156                    cout<<"---POST-ORDER TRAVERSAL---"<<endl;
157                    l1.postOrder(l1.getRoot());
158                    cout<<endl;
159                    break;
160                case 5:
161                    cout<<"Enter node to be deleted."<<endl;
162                    cin>>ele;
163                    ptr = l1.deleteNode(l1.getRoot(), ele);
164                    l1.setRoot(ptr);
165                default: cout<<"Invalid choice"<<endl;
166            }
167    } while(ch >=1 && ch <= 5);
168    return 0;
169}