A
asianmuscle
Hi I am relearning datastructure... but got kinda stuck in a basic
delete node operation. what it does is to delete the first node it
finds when the item is equal the input item. the end result is that the
node is deleted and the b-tree is still kept as b-tree. CAn someone
critique on my implementation?
Any suggestion for improvement? Thanks
The code I have as follows:
#include <iostream>
using namespace std;
class Btree;
class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};
class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isleafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
//Helper functions
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
//Helper functions
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
#include <iostream>
using namespace std;
class Btree;
class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};
class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isLeafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
int Btree::removeNode(Node* cur, int item){
int ret=0;
if(!cur) { ret =0;}
else {
if(cur->value == item) {
/*get rid of node*/
// if there is a left child
// keep promoting the left child up as long as it has one.
if (isLeafNode(cur)){ delete cur;} // if I am leaf node delete
myself
else {
// do I have a left node? yes promote,
// get rid of the last one in chain
while (cur->left)
{
swap(cur,cur->left);
cur=cur->left;
}
while (cur->right) {
swap(cur,cur->right);
cur=cur->right;
}
//should be leaf node pointed by cur
if(isLeafNode(cur)){delete cur;}
// no promote right node
// get rid of the last one in chain
}
}
else{
//if item < cur->value, tell left to do the deletion,
// else tell right
if (item<cur->value)
removeNode(cur->left,item);
else
removeNode(cur->right,item);
}
}
return ret;
}
delete node operation. what it does is to delete the first node it
finds when the item is equal the input item. the end result is that the
node is deleted and the b-tree is still kept as b-tree. CAn someone
critique on my implementation?
Any suggestion for improvement? Thanks
The code I have as follows:
#include <iostream>
using namespace std;
class Btree;
class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};
class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isleafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
//Helper functions
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
//Helper functions
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
#include <iostream>
using namespace std;
class Btree;
class Node {
private:
int value;
Node* left;
Node* right;
friend Btree;
public:
Node(int item): value(item),left(0),right(0){};
~Node(){cout<<"value is :"<<value<<"left ptr"<<left<<"right
ptr"<<right<<endl;}
};
class Btree {
private:
Node* root;
int size;
int swap(Node* node1, Node* node2);
int isLeafNode(Node* cur) const;
public:
Btree():root(0),size(0){};
~Btree(){cout<<"root pointer is"<<root<<"size is :"<<size<<endl;}
int removeNode(Node*, int);
};
int Btree::isLeafNode(Node* cur) const{
if(!cur) { return 0;}
else {
return (!cur->left) &&(!cur->right)
}
}
int Btree::swap(Node* node1, Node* node2){
int ret=0;
if(!node1 || !node2){ ret =0;} else {
int temp = node2->value;
node2->value=node1->value;
node1->value=temp;
ret =1;
}
return ret;
};
int Btree::removeNode(Node* cur, int item){
int ret=0;
if(!cur) { ret =0;}
else {
if(cur->value == item) {
/*get rid of node*/
// if there is a left child
// keep promoting the left child up as long as it has one.
if (isLeafNode(cur)){ delete cur;} // if I am leaf node delete
myself
else {
// do I have a left node? yes promote,
// get rid of the last one in chain
while (cur->left)
{
swap(cur,cur->left);
cur=cur->left;
}
while (cur->right) {
swap(cur,cur->right);
cur=cur->right;
}
//should be leaf node pointed by cur
if(isLeafNode(cur)){delete cur;}
// no promote right node
// get rid of the last one in chain
}
}
else{
//if item < cur->value, tell left to do the deletion,
// else tell right
if (item<cur->value)
removeNode(cur->left,item);
else
removeNode(cur->right,item);
}
}
return ret;
}