IdeaMonk

thoughts, ideas, code and other things...

Friday, October 31, 2008

Binary Search Tree in C++

Finally delete_node() is done!
// BST.cpp - ideamonk.blogspot.com
#include <iostream>

using namespace std;

class BSTnode{
public:
int data;
BSTnode *left, *right;

BSTnode(){
left=right=NULL;
}

BSTnode (int dat, BSTnode *lft=NULL, BSTnode *rgt=NULL){
data = dat;
left = lft;
right = rgt;
}
};

class BST{
public:
BSTnode *root;

BST(){
root = NULL;
}

bool isEmpty() { return root==NULL; }

void insert (int el, BSTnode* &myroot){
if (myroot==NULL){
myroot = new BSTnode (el,0,0);
cout << el << " inserted\n";
} else if (el<myroot->data){
insert (el,myroot->left);
} else if (el>myroot->data){
insert (el,myroot->right);
}
}

bool search(int el, BSTnode* &start){
if (start!=NULL){
if (el<start->data){
return search(el,start->left);
} else if (el>start->data){
return search (el,start->right);
} else {
return true;
}
}
return false;
}

void inorder(BSTnode* &myroot){
if (myroot->left!=NULL)
inorder(myroot->left);
if (myroot!=NULL){
visit (myroot);
}
if (myroot->right!=NULL){
inorder(myroot->right);
}
}

void preorder(BSTnode* &myroot){
if (myroot!=NULL){
visit (myroot);
}
if (myroot->left!=NULL)
inorder(myroot->left);
if (myroot->right!=NULL){
inorder(myroot->right);
}
}

void postorder(BSTnode* &myroot){
if (myroot->left!=NULL)
inorder(myroot->left);
if (myroot->right!=NULL){
inorder(myroot->right);
}
if (myroot!=NULL){
visit (myroot);
}
}

void visit(BSTnode* &node){
cout << node->data<<"->";
}

void delete_node (BSTnode** node){
if (node==NULL) return;
BSTnode *old_node = *node;
if ((*node)->left == NULL){
*node = (*node)->right;
delete old_node;
} else if ((*node)->right == NULL){
*node = (*node)->left;
delete old_node;
} else {
/* NODE with 2 children */
// find inorder predecessor
BSTnode **pred = &(*node)->left;
while ((*pred)->right != NULL) {
*pred = (*pred)->right;
}
// swap pred's data
swap ((*pred)->data, (*node)->data);
delete_node (pred);
}
}

BSTnode** find_node (int data){
BSTnode** node = &root;
while (*node != NULL) {
if (data < (*node)->data)
node = &(*node)->left;
else if ((*node)->data < data)
node = &(*node)->right;
else
break;
}
return node;
}
};

int main(){
BST b;
b.insert (4,b.root);
b.insert (10,b.root);
b.insert (6,b.root);
b.insert (3,b.root);
b.insert (12,b.root);
b.insert (2,b.root);

cout << "inorder traversal - ";
b.inorder (b.root);
cout << endl;

cout << "deleting 4\n";
b.delete_node (b.find_node(4));

cout << "preorder traversal - ";
b.preorder (b.root);
cout << endl;

cout << "postorder traversal - ";
b.postorder (b.root);
cout << endl;

if (b.search(13,b.root))
cout << "13 found!\n";
else
cout << "13 not found\n";

if (b.search(2,b.root))
cout << "2 found!\n";
else
cout << "2 not found\n";

system ("pause");

return 0;
}

Labels: , ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home