Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- using namespace std;
- template <class T>
- struct Node {
- // ##data memebers##
- T value;
- Node *left;
- Node *right;
- // ##constructors##
- Node(T val) {
- this->value = val;
- }
- Node(T val, Node<T> left, Node<T> right) {
- this->value = val;
- this->left = left;
- this->right = right;
- }
- };
- template <class T>
- class BST {
- private:
- // ## data members ##
- Node<T> *root;
- // ## private access methods ##
- //add a new node starting at root
- void addHelper(Node<T> *root, T val) {
- if (root->value > val) {
- if (!root->left) {
- root->left = new Node<T>(val);
- } else {
- addHelper(root->left, val);
- }
- } else {
- if (!root->right) {
- root->right = new Node<T>(val);
- } else {
- addHelper(root->right, val);
- }
- }
- }
- //print tree using In-Order traversal
- //left - parent - right
- void inOrderPrint(Node<T> *root) {
- //TODO create this method
- }
- //print tree using Post-Order traversal
- //parent - left - right
- void postOrderPrint(Node<T> *root) {
- //TODO create this method
- }
- //count nodes in tree
- int nodesCountHelper(Node<T> *root) {
- if (!root) return 0;
- else return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right);
- }
- //get height of tree
- int heightHelper(Node<T> *root) {
- if (!root) return 0;
- else return 1 + max(heightHelper(root->left), heightHelper(root->right));
- }
- //return longest path
- void printMaxPathHelper(Node<T> *root) {
- if (!root) return;
- cout<<root->value<<' ';
- if (heightHelper(root->left) > heightHelper(root->right)) {
- printMaxPathHelper(root->left);
- } else {
- printMaxPathHelper(root->right);
- }
- }
- //delete a value from true by providing NULL, ROOT, VAL
- //traverse tree, remove node, and fix pointers
- //return false if value is not found
- bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) {
- if (!current) return false;
- if (current->value == value) {
- if (current->left == NULL || current->right == NULL) {
- Node<T>* temp = current->left;
- if (current->right) temp = current->right;
- if (parent) {
- if (parent->left == current) {
- parent->left = temp;
- } else {
- parent->right = temp;
- }
- } else {
- this->root = temp;
- }
- } else {
- Node<T>* validSubs = current->right;
- while (validSubs->left) {
- validSubs = validSubs->left;
- }
- T temp = current->value;
- current->value = validSubs->value;
- validSubs->value = temp;
- return deleteValueHelper(current, current->right, temp);
- }
- delete current;
- return true;
- }
- return deleteValueHelper(current, current->left, value) ||
- deleteValueHelper(current, current->right, value);
- }
- public:
- //Public access methods
- //Use default constructor
- //add value to tree
- void add(T val) {
- if (root) {
- this->addHelper(root, val);
- } else {
- root = new Node<T>(val);
- }
- }
- void printInOrder() {
- //TODO create this method
- }
- void printPostOrder() {
- //TODO create this method
- }
- int nodesCount() {
- return nodesCountHelper(root);
- }
- void printNodeCount() {
- //TODO create this method
- }
- int height() {
- return heightHelper(this->root);
- }
- void printHeight() {
- //TODO create this method
- }
- void printMaxPath() {
- printMaxPathHelper(this->root);
- }
- bool deleteValue(T value) {
- return this->deleteValueHelper(NULL, this->root, value);
- }
- };
- int main() {
- //create binary search tree
- BST<int> *bst = new BST<int>();
- //array of values to add to tree
- int vals [6] = {11, 1, 6, -1, -10, 100};
- //add values
- for(const int &val : vals) {
- bst->add(val);
- }
- bst->printInOrder();
- bst->printPostOrder();
- bst->printNodeCount();
- bst->printHeight();
- bst->printMaxPath();
- //remove values
- for(const int &val : vals) {
- bst->deleteValue(val);
- std::cout << val << " removed: ";
- bst->printInOrder();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement