diff options
Diffstat (limited to 'bst.h')
| -rw-r--r-- | bst.h | 280 |
1 files changed, 280 insertions, 0 deletions
@@ -0,0 +1,280 @@ +/* definitions are residing in this header since that's how templates get + * expanded, we could have a separate bst.cpp is compiler supports export keyword, + * instantiations of code are compiled along with the translation units that spawn them + */ + +#ifndef _BST_H_ +#define _BST_H_ + +#include <iostream> +#include <cstdio> +#include <cassert> +#include "node.h" + +using namespace std; + +template <class T> +class Bst +{ + public: + Bst(); + Bst(const Bst &); + /* Bst(Node<T> &); */ + Bst(const T &); /* above was hairy, just startup a bst from a T t */ + ~Bst(); + + int insert(const T &); + int remove(const T &); + int list(void) const; + + private: + unsigned int element_count; + void traverse(Node<T> *) const; + void free(); + void freePostOrder(Node<T> *); + + protected: + Node<T> *root; +}; + +template <class T> +Bst<T>::Bst() : element_count(0), root(NULL) +{ +} + +template <class T> +Bst<T>::Bst(const Bst& tree) +{ + this->free(); + /* still a shallow copy, dupe it! */ + this->root = tree.root; +} + +template <class T> +Bst<T>::Bst(const T& t) +{ + Node<T> *first = new Node<T>(t); + this->root = first; +} + +template <class T> +Bst<T>::~Bst() +{ + this->free(); +} + + +template <class T> +int Bst<T>::insert(const T& e) +{ + Node<T> *iter = this->root; + Node<T> *new_node = new Node<T>(e); + + while (iter) + { + if (iter->getVal() == e) + { + std::cout << e << " is already in the tree" << std::endl; + return 1; + } + else if (iter->getVal() < e) + { + if (&iter->getRight() == NULL) + { + iter->setRight((new_node)); + return 1; + } + else + iter = &iter->getRight(); /* taking addr of alias/reference? */ + } + else + { + if (&iter->getLeft() == NULL) + { + iter->setLeft((new_node)); + return 1; + } + else + iter = &iter->getLeft(); + } + } + + std::cout << "creating root node " << e << endl; + this->root = new_node; + + return 0; +} + +template <class T> +int Bst<T>::remove(const T& e) +{ + /* assign the value of leftmost subtree of nodes right child to node to be + * removed, and delete the leaf where value was taken from */ + if (!this->root) + return 1; + + Node<T> *iter = this->root; + while (iter) + { + if (iter->getVal() < e) + { /* working on right subtree */ + if (&iter->getRight() && (iter->getRight().getVal() == e)) /* lookahead */ + { + Node<T> *child_left = &iter->getRight().getLeft(); + Node<T> *child_right = &iter->getRight().getRight(); + Node<T> *node_toremove = &iter->getRight(); + + if (!child_left && !child_right) + { /* leaf */ + delete node_toremove; + iter->setRight(NULL); + } + else if (child_left && child_right) + { /* node to be remove has 2 children */ + if (&child_right->getLeft() == NULL) + { /* move up righ subtree if right child has no left child */ + child_right->setLeft(&node_toremove->getLeft()); + iter->setRight(child_right); + delete node_toremove; + } + else + { + Node<T> *iter = child_right; + while (&iter->getLeft().getLeft()) + iter = &iter->getLeft(); /* seek */ + + node_toremove->setVal(iter->getLeft().getVal()); + delete &iter->getLeft(); + iter->setLeft(NULL); + } + } + else + { /* got one child, delete e and link child to grandfather */ + if (child_left) + iter->setRight(child_left); + else + iter->setRight(child_right); + delete node_toremove; + } + + return 0; + } + else + iter = &iter->getRight(); + } + else if (iter->getVal() > e) + { /* working with left subtree */ + if (&iter->getLeft() && (iter->getLeft().getVal() == e)) /* lookahead */ + { + + Node<T> *child_left = &iter->getLeft().getLeft(); + Node<T> *child_right = &iter->getLeft().getRight(); + Node<T> *node_toremove = &iter->getLeft(); + + if (!child_left && !child_right) + { /* leaf */ + delete node_toremove; + iter->setLeft(NULL); + return 0; + } + else if (child_left && child_right) + { /* node to be remove has 2 children */ + if (&child_right->getLeft() == NULL) + { /* move up righ subtree if right child has no left child */ + child_right->setLeft(&node_toremove->getLeft()); + iter->setLeft(child_right); + delete node_toremove; + } + else + { + Node<T> *iter = child_right; + while (&iter->getLeft().getLeft()) + iter = &iter->getLeft(); /* seek */ + + node_toremove->setVal(iter->getLeft().getVal()); + delete &iter->getLeft(); + iter->setLeft(NULL); + } + } + else + { /* got one child, delete e and link child to grandfather */ + if (child_left) + iter->setLeft(child_left); + else + iter->setLeft(child_right); + delete node_toremove; + } + + return 0; + } + else + iter = &iter->getLeft(); + } + else + { /* root removal */ + /* assign root left subtree into lowest leaf in the right subtree */ + if ((&this->root->getLeft() == NULL) && (&this->root->getRight() == NULL)) + { + delete this->root; + this->root = NULL; + return 0; + } + + Node<T> *iter = &this->root->getRight(); + while (&iter->getLeft()) + iter = &iter->getLeft(); + iter->setLeft(&this->root->getLeft()); /* set left subtree */ + this->root = &root->getRight(); + delete this->root; + return 0; + } + } + + /* not in the tree */ + return 2; +} + +template <class T> +int Bst<T>::list(void) const +{ + if (!this->root) + return 1; + + this->traverse(this->root); + return 0; +} + +template <class T> +void Bst<T>::traverse(Node<T> *node) const +{ + if (!node) + return; + + this->traverse(&node->getLeft()); + std::cout << node->getVal() << " " << endl; + this->traverse(&node->getRight()); +} + +template <class T> +void Bst<T>::free(void) +{ + if (this->root) + this->freePostOrder(this->root); +} + +template <class T> +void Bst<T>::freePostOrder(Node<T> *node) +{ + if (!node) + return; + + this->freePostOrder(&node->getLeft()); + this->freePostOrder(&node->getRight()); + #ifdef DEBUGMSG + std::cout << "nuking " << node->getVal() << std::endl; + #endif + delete node; +} + +#endif + |