#include<bits/stdc++.h>
using namespace std;
class tree_node{
public:
int val;
tree_node *left,*right;
public:
tree_node(int n){
this->val = n;
this->left = this-> right = NULL;
}
//int get_value(){return this->val;}
//tree_node* get_left(){return (tree_node *)this->left;}
//tree_node* get_right() {return(tree_node *)this->right;}
};
class tree{
public:
tree_node * root;
public:
tree(int n){
//constructor
root = new tree_node(n);
}
tree_node * get_root(){
return root;
}
void insert(int n);
void print_level_wise();
void delete_node(int n);
};
void tree::insert(int n){
tree_node *r = get_root();
queue<tree_node *>q;
q.push(r);
while(1){
tree_node * curr = q.front();
q.pop();
if(curr->left==NULL){
curr->left = new tree_node(n);
return;
}
else{
q.push(curr->left);
}
if(curr->right==NULL){
curr->right = new tree_node(n);
return;
}
else{
q.push(curr->right);
}
}
}
void tree::delete_node(int key){
//delete k from the tree
//find key node and also right most deep most node
tree_node *target=NULL,*rd,*rdp;
tree_node *r = get_root();
queue<tree_node *>q;
q.push(r);
while(1){
tree_node* curr = q.front(); q.pop();
//cout<<curr->val<<endl;
if(target==NULL and curr->val==key){
target = curr;
// cout<<"target val is "<<target->val<<endl;
}
if(q.empty() and curr->left==NULL and curr->right== NULL){
//this is rd node
rd =curr;
break;
}
if(curr->left!=NULL or curr->right!= NULL){
if(curr->left!=NULL)
q.push(curr->left);
if(curr->right!=NULL)
q.push(curr->right);
// cout<<"pushed iterms are :\n";
// if(curr->left!=NULL)
// cout<<curr->left->val<<endl;
// if(curr->right!=NULL)
// cout<<curr->right->val<<endl;
rdp = curr;
}
}
if(target!=NULL){
target->val = rd->val;
if(rdp->left==rd){
rdp->left=NULL;
}
else if(rdp->right==rd){
rdp->right=NULL;
}
free(rd);
print_level_wise();
}
else{
cout<<"Can not find key in tree\n";
}
}
void tree::print_level_wise(){
tree_node* r = get_root();
queue<tree_node*>q;
q.push(r);
while(!q.empty()){
tree_node*c= q.front();
q.pop();
cout<<c->val<<"\t";
if(c->left!=NULL)q.push(c->left);
if(c->right!=NULL)q.push(c->right);
}
}
int main() {
int root_val=1;
tree t1(1);
t1.insert(2);
t1.insert(3);
t1.insert(4);
t1.insert(6);
t1.insert(5);
//t1.insert(7);
t1.print_level_wise();
cout<<endl;
t1.delete_node(2);
return 0;
}
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.