Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * File: BinarySearchTree.cpp
- * Prj: Dictonary
- *
- * Created by Will Mernagh on April 21.
- * Copyright 2007. All rights reserved.
- *
- */
- #include <iostream>
- #include "nodes.h"
- #include "BinarySearchTree.h"
- using namespace std;
- /*
- * Constructor
- */
- BST::BST()
- {
- setRoot(NULL);
- }
- /*
- * Returns the root
- */
- TreeNode * BST::getRoot(){
- return root;
- }
- /*
- * Set the root
- */
- void BST::setRoot(TreeNode *rootin){
- root = rootin;
- }
- /*
- * Inserts the node into the tree
- *
- * @param TreeNode The Node to add to the tree
- * @return False if already in the tree
- */
- bool BST::insert(TreeNode *tnode)
- {
- TreeNode *search, *position;
- search = getRoot();
- /* If empty tree */
- if(search == NULL){
- setRoot(tnode);
- getRoot()->setLeft(NULL);
- getRoot()->setRight(NULL);
- getRoot()->setParent(NULL);
- return true;
- }
- /* if word already in the tree */
- if(find(tnode->word)){
- return false;
- }
- position = search;
- while(position != NULL){
- search = position;
- if(tnode->word > search->word){
- position = search->getRight();
- }else if (tnode->word < search->word){
- position = search->getLeft();
- }else{
- return false; //match
- }
- }
- if(tnode->word > search->word){
- search->setRight(tnode);
- tnode->setParent(search);
- tnode->setLeft(NULL);
- tnode->setRight(NULL);
- }else if (tnode->word < search->word){
- search->setLeft(tnode);
- tnode->setParent(search);
- tnode->setLeft(NULL);
- tnode->setRight(NULL);
- }
- return true;
- }
- /*
- * Inserts the string into the tree.
- *
- * @param String The string to add to the tree
- * @return False if already in the tree
- */
- bool BST::insert(string word)
- {
- TreeNode *tnode = new TreeNode;
- tnode->word = word;
- if(BST::insert(tnode)){
- return true;
- }else{
- delete tnode;
- return false;
- }
- }
- /*
- * Search for a string and return true if in tree
- *
- * @param String The string to search for
- * @return True if string in the tree
- */
- bool BST::find(string word)
- {
- TreeNode *search;
- search = getRoot();
- while(search != NULL){
- if(word > search->word){
- search = search->getRight();
- }else if (word < search->word){
- search = search->getLeft();
- }else{
- return true; //match
- }
- }
- return false;
- }
- /*
- * Search for a node and return true if in tree
- *
- * @param String The string encapsulated in node to search for
- * @return True if string in the tree
- */
- TreeNode * BST::findNode(string word)
- {
- TreeNode *search;
- search = getRoot();
- while(search != NULL){
- if(word > search->word){
- search = search->getRight();
- }else if (word < search->word){
- search = search->getLeft();
- }else{
- return search; //match
- }
- }
- return NULL;
- }
- /*
- * Search for the successor of a string and return it if in tree
- *
- * @param String The string whose successor to search for
- * @return TreeNode if string in the tree else return null
- */
- TreeNode * BST::successor(string word)
- {
- TreeNode *wordNode;
- TreeNode *search;
- wordNode = findNode(word);
- if(wordNode == NULL){
- return NULL;
- }
- if((wordNode->getRight()==NULL)&&(wordNode->getParent()==NULL)){
- return NULL; //no successor
- }else if(wordNode->getRight() != NULL) {//search down
- search = wordNode->getRight();
- while(search->getLeft() != NULL){
- search = search->getLeft();
- }
- return search;
- }else if(wordNode->getParent()->word > wordNode->word){
- return wordNode->getParent();
- }else{
- //Search up
- search = wordNode;
- while((search->getParent() != NULL) &&
- (search->getParent()->word < wordNode->word)){
- search = search->getParent();
- }
- return search->getParent();
- }
- return NULL;
- }
- /*
- * Display the items in a tree in order
- *
- * @param TreeNode The next node to recurse on
- */
- void BST::recurseDisplay(TreeNode *node)
- {
- if(node != NULL){
- recurseDisplay(node->getLeft());
- cout<<node->word<<"";
- if(node->getParent() != NULL){
- cout << "(" << node->getParent()->word<<")\n";
- }else{
- cout<<"\n";
- }
- recurseDisplay(node->getRight());
- }
- }
- /*
- * Display the items in a tree in order
- *
- */
- void BST::display()
- {
- recurseDisplay(getRoot());
- }
- /* Delete a word from the tree
- *
- * @param string The string to delete
- * @return bool False if it does not exist in tree
- */
- bool BST::del(string word)
- {
- TreeNode *todel, *scsr;
- string scsrWord;
- todel = findNode(word);
- /* does not exist */
- if(todel == NULL){
- return false;
- }
- if(todel == getRoot()){
- scsr = successor(word);
- if((scsr == NULL)&&(todel->getLeft() == NULL)){
- delete(todel);
- setRoot(NULL);
- return true;
- }else if(scsr == NULL){
- setRoot(todel->getLeft());
- todel->getLeft()->setParent(NULL);
- delete(todel);
- return true;
- }else{
- scsrWord = scsr->word;
- del(scsrWord);
- todel->word = scsrWord;
- return true;
- }
- }else if((todel->getLeft() == NULL)&&(todel->getRight() == NULL)){
- if((todel->getParent()->getLeft() != NULL) &&
- (todel->getParent()->getLeft()->word == todel->word)){
- todel->getParent()->setLeft(NULL);
- }else{
- todel->getParent()->setRight(NULL);
- }
- delete todel;
- return true;
- }else if(todel->getLeft() == NULL){
- if((todel->getParent()->getLeft() != NULL) &&
- (todel->getParent()->getLeft()->word == todel->word)){
- todel->getParent()->setLeft(todel->getRight());
- todel->getRight()->setParent(todel->getParent());
- }else{
- todel->getParent()->setRight(todel->getRight());
- todel->getRight()->setParent(todel->getParent());
- }
- delete todel;
- return true;
- }else if(todel->getRight() == NULL){
- if((todel->getParent()->getLeft() != NULL) &&
- (todel->getParent()->getLeft()->word == todel->word)){
- todel->getParent()->setLeft(todel->getLeft());
- todel->getLeft()->setParent(todel->getParent());
- }else{
- todel->getParent()->setRight(todel->getLeft());
- todel->getLeft()->setParent(todel->getParent());
- }
- delete todel;
- return true;
- }else{
- scsr = successor(word);
- scsrWord = scsr->word;
- del(scsr->word);
- todel->word = scsrWord;
- return true;
- }
- return false;
- }
- /* Destructor
- */
- BST::~BST(){
- while(getRoot() != NULL){
- del(getRoot()->word);
- }
- }
Add Comment
Please, Sign In to add comment