### 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: BST, c++, programming

## 0 Comments:

## Post a Comment

Subscribe to Post Comments [Atom]

<< Home