Binary Search Tree rude wrap

#include<iostream>
#include<stack>
using namespace std;

const int N_NODE_MAX = 10;
const int N_NODE_USED = 10;
typedef int datatype;

class Node
{
private:
datatype data;
Node* leftchild;
Node* rightchild;

public:
Node(datatype data, Node* leftchild, Node* rightchild)
{
this->data = data;
this->leftchild = leftchild;
this->rightchild = rightchild;
}

~Node(void)
{
// pass
}

datatype getdata(void)
{
return this->data;
}

Node* getleftchild(void)
{
return this->leftchild;
}

Node* getrightchild(void)
{
return this->rightchild;
}

void setleftchild(Node* node)
{
this->leftchild = node;
}

void setrightchild(Node* node)
{
this->rightchild = node;
}

bool hasleftchild(Node* node)
{
// return true if the node passed in is left child of the current node
return this->leftchild == node;
}

bool hasrightchild(Node* node)
{
// return true if the node passed in is right child of the current node
return this->rightchild == node;
}

bool isparent(datatype data)
{
// return true if the node passed in with given data is child of the current node
if( this->leftchild != NULL && this->leftchild->getdata() == data){
return true;
}
if( this->rightchild != NULL && this->rightchild->getdata() == data ){
return true;
}
return false;
}

};

class BST
{
private:
Node* root;

public:
BST(Node* root)
{
this->root = root;
}

~BST(void)
{
// pass
}

void insert(Node* node)
{
Node* p = this->root;
while( p != NULL ){
if( node->getdata() == p->getdata() ){
cout<<"duplicate node inserted with data "<<node->getdata()<<endl;
return;
}
else if( node->getdata() < p->getdata() ){
if( p->getleftchild() == NULL ){
p->setleftchild(node);
return;
}
p = p->getleftchild();
}
else{
if( p->getrightchild() == NULL ){
p->setrightchild(node);
return;
}
p = p->getrightchild();
}
}

}

Node* getparent(datatype data)
{
if( this->root != NULL && data == this->root->getdata() ){
return NULL;
}
Node* p = this->root;
while( p != NULL ){
if( p->isparent(data) ){
return p;
}
if( data < p->getdata() ){
p = p->getleftchild();
}
else{
p = p->getrightchild();
}
}
return NULL;

}

Node* getnode(datatype data)
{
Node* p = this->root;
while( p != NULL ){
if( data == p->getdata() ){
return p;
}
else if( data < p->getdata() ){
p = p->getleftchild();
}
else{
p = p->getrightchild();
}
}
return NULL;

}

void del(datatype data)
{
// get the node to delete
Node* node = this->getnode(data);
if( node == NULL ){
cout<<"no such a node"<<endl;
return;
}
// get the parent of the node to delete
bool isroot = false;
Node* parent = this->getparent(data);
if( parent == NULL ){
isroot = true;
}
if( node->getleftchild() != NULL && node->getrightchild() != NULL ){
// get the node in its left subtree with the biggest data value to replace the node to delete
// the parent of the node to replace with
Node* prevp = node;
// the node to replace with
Node* p = node->getleftchild();
while( p->getrightchild() != NULL ){
prevp = p;
p = p->getrightchild();
}
// adjust the left subtree structure of the node to replace with
if( prevp->hasleftchild(p) ){
prevp->setleftchild(p->getleftchild());
}
else if( prevp->hasrightchild(p) ){
prevp->setrightchild(p->getleftchild());
}
// replace the node to delete
p->setleftchild(node->getleftchild());
p->setrightchild(node->getrightchild());

// if the node to delete is root, simply update root
// otherwise update the parent of the node to replace with
if( isroot ){
this->root = p;
}
else{
if( parent->hasleftchild(node) ){
parent->setleftchild(p);
}
else if( parent->hasrightchild(node) ){
parent->setrightchild(p);
}
}
}
else{
// the node to delete has noly left subtree
if( node->getleftchild() != NULL ){
if( isroot ){
this->root = node->getleftchild();
}
else{
if( parent->hasleftchild(node) ){
parent->setleftchild(node->getleftchild());
}
else if( parent->hasrightchild(node) ){
parent->setrightchild(node->getleftchild());
}
}
}
// the node to delete has noly right subtree
else if( node->getrightchild() != NULL ){
if( isroot ){
this->root = node->getrightchild();
}
else{
if( parent->hasleftchild(node) ){
parent->setleftchild(node->getrightchild());
}
else if( parent->hasrightchild(node) ){
parent->setrightchild(node->getrightchild());
}
}
}
// the node to delete is a leaf
else{
if( isroot ){
this->root = NULL;
}
else{
if( parent->hasleftchild(node) ){
parent->setleftchild(NULL);
}
else if( parent->hasrightchild(node) ){
parent->setrightchild(NULL);
}
}
}

}
delete node;
node = NULL;

}

void visit(Node* node)
{
cout<<node->getdata()<<" ";
}

void preordertravel(void)
{
stack<Node*>buffer;
if( this->root == NULL ){
cout<<"an empty tree"<<endl;
return;
}
buffer.push(this->root);
while( !buffer.empty() ){
Node* p = buffer.top();
buffer.pop();
this->visit(p);
if( p->getrightchild() != NULL ){
buffer.push(p->getrightchild());
}
if( p->getleftchild() != NULL ){
buffer.push(p->getleftchild());
}
}
cout<<endl;
}

};

int main(void)
{
datatype a[10] = { 3, 9, 17, 14, 13, 22, 5, 9, 11, 7 };
datatype b[2] = { 3, 16 };
datatype c[5] = { 3, 16, 5, 8, 7 };
datatype d[3] = { 3, 1, 16 };
datatype e[4] = { 3, 1, 4, 16 };
Node *root = new Node(12, NULL, NULL);
BST tree(root);
for(int i = 0; i < 10; i++){
Node *node = new Node(a[i], NULL, NULL);
tree.insert(node);
}
tree.preordertravel();
// test the function of getparent( ), getnode( ) and del( )

datatype val;
while( cin>>val && val>0 ){
tree.del(val);
tree.preordertravel();
/*
Node* parent = tree.getparent(val);
if( parent != NULL ){
cout<<parent->getdata()<<endl;
}
else{
cout<<"no parent"<<endl;
}

Node* node = tree.getnode(val);
if( node != NULL ){
cout<<node->getdata()<<endl;
}
else{
cout<<"no such a node"<<endl;
}
*/
}
return 0;

}

AllStuffON

Binary Search Tree rude wrap

Learn More :

AllStuffON

Binary Search Tree rude wrap

Learn More :

Share this