Untitled
unknown
plain_text
3 years ago
3.6 kB
3
Indexable
#include <iostream> #include <string> #include "BinaryTree.h" using namespace std; /** * Constructor. * Binary tree is initialized. */ template <class T> BinaryTree<T>::BinaryTree() { root = NULL; length = 0; } /** * Destructor. * All node pointers freed and root points to NULL. */ template <class T> BinaryTree<T>::~BinaryTree() { freeNodes(root); } /** * freeNodes. * Delete tree nodes recursively. * Helper method for ~BinaryTree(). */ template <class T> void BinaryTree<T>::freeNodes(NodeType<T>* &tree) { if (tree != NULL) { freeNodes(tree->left); freeNodes(tree->right); delete tree; } } /** * insert. * Insert a node with the value of key into the tree. * No duplicates are allowed. */ template <class T> void BinaryTree<T>::insert(T &key) { insertNode(root, key); length++; } /** * insertNode. * insert a Node into the right position recursively. * Helper method for insert */ template <class T> void BinaryTree<T>::insertNode(NodeType<T>* &tree, T &key) { if (tree == NULL) { tree = new NodeType<T>; tree->right = NULL; tree->left = NULL; tree->key = key; } else if (key < tree->key) { insertNode(tree->left, key); } else { insertNode(tree->right, key); } } /** * deleteItem * Remove a node with a key value equal to the parameters key value * Otherwise leave the tree unchanged * In situations where the node has to be deleted has two children. * replace the deletedNode with its immediate predecessor or successor */ template <class T> void BinaryTree<T>::deleteItem(T &key) { bool found; retrieve(root, key, found); if (!found) { cout << "Item is not found!" << endl; return; } else { if (key < root->key) { deleteNode(root->left, key); } else if (key > root->key) { deleteNode(root->right, key); } else { deleteNode(root, key); } length--; } } template<class T> void BinaryTree<T>::getPredecessor(NodeType<T>* &tree, T &item) { while (tree->right != NULL) { tree = tree->right; } item = tree->key; } template<class T> void BinaryTree<T>::deleteNode(NodeType<T>* &tree, T &item) { T tempItem; NodeType<T>* tempPtr; tempPtr = tree; if (tree->left == NULL) { tree = tree->right; delete tempPtr; } else if (tree->right == NULL) { tree = tree->left; delete tempPtr; } else { getPredecessor(tree->left, tempItem); tree->key = tempItem; deleteNode(tree->left, tempItem); } } /** * Item should refer to a key of a Node n in the tree where the value of * n.key is equal to the value of item * Found is true if n exists otherwise false */ template<class T> void BinaryTree<T>::retrieve(NodeType<T>* &tree, T &item, bool &found) const { if (tree == NULL) { found = false; } else if (item < tree->key) { retrieve(tree->left, item, found); } else if (item > tree->key) { retrieve(tree->right, item, found); } else { item = tree->key; found = true; } } template<class T> void BinaryTree<T>::preOrder() const { } template<class T> void BinaryTree<T>::inOrder() const { } template<class T> void BinaryTree<T>::postOrder() const { } template<class T> int BinaryTree<T>::getLength() const { return length; } template class BinaryTree<int>; template class BinaryTree<float>; template class BinaryTree<std::string>;
Editor is loading...