//
// bSearchTreeType.h
//
//
// Created by keovessna vong on 1/2/2012.
// Copyright (c) 2012 Burapha. All rights reserved.
//
#include "binaryTreeType.h"
#include <cassert>
#include <iostream>
using namespace std;
class bSearchTreeType:public binaryTreeType{
public:
bool search(const int& searchItem);
//Function to determine whether searchItem is in the binary search tree.
//Postcondition : Return true if searchITem is found in th binary search tree;
// otherwise , return false.
void insert(const int& insertItem);
//Function to insert in the binary search tree.
//Postcondition : If no node in the bianry tree has the same
// into as insertItem, a node with the info insertItem is created and inserted
// in the binary search tree.
void deleteNode(const int& deleteItem);
//Function to delete deleteItem from the binary search tree.
//Postcondition : If a node with the same info as deleteItem
// isfound, it is delete from the binary search tree.
private:
void deleteFromTree(nodeType* &p);
//Function to delete the node, to which p points, from the bianry search tree.
//Postcodition : The node to which p points is deleted from the binary search tree
};
bool bSearchTreeType::search(const int &searchItem){
nodeType *current ;
bool found = false ;
if(root == NULL)
cerr<<"Cannot search an empty tree.\n";
else{
current = root;
while(current != NULL && !found){
if(current->info == searchItem)
found = true;
else{
if(current->info >searchItem)
current = current->llink;
else
current = current->rlink;
}
}
}
return found;
}
void bSearchTreeType::insert(const int& insertItem){
nodeType *current; //pointer to traverse the tree
nodeType *trailCurrnt; //pointer to behind current
nodeType *newNode; //pointer to create the node
newNode = new nodeType;
assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;
if(root == NULL){
root = newNode;
}else{
current = root;
while(current != NULL){
trailCurrnt = current;
if(current->info == insertItem){
cerr << "The insert item is already in the list - ";
cerr << "duplicates are not allowed. \n";
exit(0);
}else{
if(current->info > insertItem)
current = current->llink;
else
current = current->rlink;
}
}
if(trailCurrnt->info > insertItem)
trailCurrnt->llink = newNode;
else
trailCurrnt->rlink = newNode;
}
}
void bSearchTreeType::deleteFromTree(nodeType* &p){
nodeType *current; //pointer to travers the tree
nodeType *trailCurrnt; //pointer to behind current
nodeType *temp; //pointer to delete the node
if(p == NULL)
cerr << "Error : The node to be delete is NULL. \n";
else if(p->llink == NULL && p->rlink == NULL){
temp = p;
p = NULL ;
delete temp;
}else if(p->llink == NULL){
temp = p;
p = temp->rlink;
delete temp;
}else if(p->rlink == NULL){
temp = p;
p = temp->llink;
delete temp;
}else{
current =p->llink;
trailCurrnt = NULL;
while(current->rlink != NULL){
trailCurrnt = current;
current = current->rlink;
}
p->info = current->info;
if(trailCurrnt == NULL) //current did not move;
p->llink = current->llink; //current == p->llink; adjust p
else
trailCurrnt->rlink = current->llink;
delete current;
}
}
void bSearchTreeType::deleteNode(const int& deleteItem){
nodeType *current; //pointer to travers the tree
nodeType *trailCurrnt; //pointer behind current
bool found = false;
if(root == NULL)
cerr << "Cannot delete from the empty tree. \n";
else{
current = root;
trailCurrnt = root;
while(current != NULL && !found){
if(current->info == deleteItem)
found = true;
else{
trailCurrnt = current;
if(current->info > deleteItem)
current = current->llink;
else
current = current->rlink;
}
} // end while
if(current == NULL)
cout << "The delete item is not in the list. \n";
else{
if(found){
if(current == root)
deleteFromTree(root);
else{
if(trailCurrnt->info >deleteItem)
deleteFromTree(trailCurrnt->llink);
else
deleteFromTree(trailCurrnt->rlink);
}// end else
}// end if(found)
}
}
}
|
