TOPIC: C++ program to delete leaf nodes with value as x
Link to source code: https://github.com/pyskmr/D4datastructures/blob/master/binary%20tree/del_X_leafes.cpp
DESCRIPTION:
The idea is simple, we will check for the leaf node(i.e. when the left and the right child becomes NULL), if its a leaf node we will check its data value, if it is equal to the X then we will delete the node and assign NULL to the pointer pointing to the node.
So we will use the POSTORDER approach and instead of where we will go to left and then right subtree.
example:-
10
/ \
3 6
\ / \
10 10 4
and we deleted 10 then it must be like
10
/ \
3 6
\
4
------------------------------------------------------------------------------------------------------------------------------------------------------------
Complexity
O(n) because we are looking for leaf nodes for which we have to traverse the whole tree.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
I always put an emphasis on coding on your own but I'm still providing you the code just in case you need some help.
CODE:-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134 135 136 137 138 139 140 141 142
| #include<iostream>
/*
C++ program to delete leaf nodes with value as x
*/
using namespace std;
/* a base class is created which contain the data of every node in the tree */
template<class P>
class node
{
public:
P data;
node *left,*right;
node()
{
left=NULL;
right= NULL;
}
node(P value)
{
data = value;
left=right=NULL;
}
};
/* class tree inheriting node class and having a root object of the node as its class member */
template<class C>
class tree:public node<C>
{
private:
node<C> *root;
public:
tree();
node<C>* getRoot();
void setRoot(node<C>*);
void createTree();
void inorder(node<C>*);
node<C>* del_leaf_value(node<C>*,const int&);
};
/* tree class default constructor.As soon as the object will be made its root will be pointed to NULL */
template<class C>
tree<C> :: tree()
{
root=NULL;
}
/* this will return the root of the tree's object */
template<class C>
node<C>* tree<C> :: getRoot()
{
return root;
}
/* A setter function to set the root of the tree */
template<class C>
void tree<C>::setRoot(node<C>*p)
{
root=p;
}
/* this will create the tree in the example we just shown */
template<class C>
void tree<C>::createTree()
{
root=new node<C>(10);
root->left=new node<C>(3);
root->left->right=new node<C>(10);
root->right=new node<C>(6);
root->right->left=new node<C>(10);
root->right->right=new node<C>(4);
}
template<class C>
void tree<C>::inorder(node<C> *r)
{
if (r==NULL) {
return;
}
else
{
inorder(r->left);
cout<<r->data<<" ";
inorder(r->right);
}
}
/* Postorder approach to deleteleafes with X as their data */
template<class C>
node<C>* tree<C>::del_leaf_value(node<C>*r,const int& value)
{
if(r==NULL)
{
return NULL;
}
r->left=del_leaf_value(r->left,value);
r->right=del_leaf_value(r->right,value);
if(r->left==NULL && r->right==NULL && r->data == value)
{
delete(r);
return NULL;
}
else
{
return r;
}
}
int main()
{
tree<int> obj;
int X;
X=10; //you can also set any value to X
obj.createTree();
/* Diplaying the tree in INORDER sequence */
obj.inorder(obj.getRoot());
cout<<"\n";
/* Deleting leafes with value as X */ obj.setRoot(obj.del_leaf_value(obj.getRoot(),X));
/* Displaying the tree in INORDER sequence after delting the desired leafes */ obj.inorder(obj.getRoot());
return 0;
}
|
OUTPUT:-
KEEP UP THE GOOD WORK AND KEEP CODING. (:
|
Comments