Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Rewrite method inserthelp() to take advantage of the modified BSTNode in which a pointer can be either a regular pointer or a thread. Modify method printhelp() to work with threaded nodes. Add method printInorder() to do an inorder printing of your tree without the use of recursion. Add printReverse() to do a reverse order printing of your tree without resorting to recursion. You may add private helper methods as needed to make modifying or creating the methods above easier.

Rewrite method inserthelp() to take advantage of the modified BSTNode in which a pointer can be either a regular pointer or a thread. Modify method printhelp() to work with threaded nodes. Add method printInorder() to do an inorder printing of your tree without the use of recursion. Add printReverse() to do a reverse order printing of your tree without resorting to recursion. You may add private helper methods as needed to make modifying or creating the methods above easier.

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
  • Rewrite method inserthelp() to take advantage of the modified BSTNode in which a pointer can be either a regular pointer or a thread.
  • Modify method printhelp() to work with threaded nodes.
  • Add method printInorder() to do an inorder printing of your tree without the use of recursion.
  • Add printReverse() to do a reverse order printing of your tree without resorting to recursion.
  • You may add private helper methods as needed to make modifying or creating the methods above easier.
// multiple records match "k", E* find (const Key& k) const { return findhelp (root, k); } 86 return an arbitrary one. 87 88 // Return the number of records in the dictionary. int size () { return nodecount; } 89 90 91 void print () const { // Print the contents of the BST if (root == NULL) cout << "The BST is empty. \n"; else printhelp (root, 0); 92 93 94 95 } 96 97 }; 98 // Visit prints out root template <typename Key, typename E> 99 100 pvoid BST<Key, E>::vist (BSTNode<Key, E>* r) const { " <« r->element () << endl; 101 102 cout << "Node 103 } 104 // Clean up BST by releasing space back free store template <typename Key, typename E> void BST<Key, E>: : clearhelp (BSTNode<Key, E>* root) { if (root == NULL) return; clearhelp (root->left ()); clearhelp (root->right () ); 105 106 107 108 109 110 111 112 delete root; 113 114 // Insert a node into the BST, returning the updated tree template <typename Key, typename E> pBSTNode<Key, E>* BST<Key, E>::inserthelp ( BSTNode<Key, E>* root, const Key& k, const E& it) { if (root == NULL) return new BSTNode<Key, E> (k, it, NULL, NULL); if (k < root->key ()) root->setLeft (inserthelp (root->left (), k, it)); else root->setRight (inserthelp (root->right(), k, it)); 115 116 117 118 119 // Empty tree: create node 120 121 122 123 124 return root; // Return tree with node inserted 125 126 // Delete the minimum value from the BST, returning the revised BST template <typename Key, typename E> BSTNode<Key, E>* BST<Key, E>:: getmin (BSTNode<Key, E>* rt) { if (rt->left() == NULL) 127 128 129 130 131 132 return rt; 133 else return getmin (rt->left()); 134 135 template <typename Key, typename E> BSTNode<Key, E>* BST<Key, E>:: edeletemin (BSTNode<Key, E>* rt) { if (rt->left () == NULL) // Found min return rt->right(); 136 137 138 139 140 else { // Continue left 141 rt->setLeft (deletemin (rt->left () )); 142 return rt; 143 144 145 // Remove a node with key value k // Return: The tree with the node removed template <typename Key, typename E> BSTNode<Key, E>* BST<Key, E>:: removehelp (BSTNode<Key, E>* rt, const Keys k) { if (rt == NULL) return NULL; 146 147 148 149 150 151 // k is not in tree else if (k < rt->key ()) rt->setLeft (removehelp (rt->left (), k)); else if (k > rt->key () ) rt->setRight (removehelp (rt->right(), k)); 152 153 154 155 156 else { // Found: remove it BSTNode<Key, E>* temp = if (rt->left () rt = rt->right(); delete temp; 157 rt; // Only a right child // so point to right 158 == NULL) { 159 160
Transcribed Image Text:// multiple records match "k", E* find (const Key& k) const { return findhelp (root, k); } 86 return an arbitrary one. 87 88 // Return the number of records in the dictionary. int size () { return nodecount; } 89 90 91 void print () const { // Print the contents of the BST if (root == NULL) cout << "The BST is empty. \n"; else printhelp (root, 0); 92 93 94 95 } 96 97 }; 98 // Visit prints out root template <typename Key, typename E> 99 100 pvoid BST<Key, E>::vist (BSTNode<Key, E>* r) const { " <« r->element () << endl; 101 102 cout << "Node 103 } 104 // Clean up BST by releasing space back free store template <typename Key, typename E> void BST<Key, E>: : clearhelp (BSTNode<Key, E>* root) { if (root == NULL) return; clearhelp (root->left ()); clearhelp (root->right () ); 105 106 107 108 109 110 111 112 delete root; 113 114 // Insert a node into the BST, returning the updated tree template <typename Key, typename E> pBSTNode<Key, E>* BST<Key, E>::inserthelp ( BSTNode<Key, E>* root, const Key& k, const E& it) { if (root == NULL) return new BSTNode<Key, E> (k, it, NULL, NULL); if (k < root->key ()) root->setLeft (inserthelp (root->left (), k, it)); else root->setRight (inserthelp (root->right(), k, it)); 115 116 117 118 119 // Empty tree: create node 120 121 122 123 124 return root; // Return tree with node inserted 125 126 // Delete the minimum value from the BST, returning the revised BST template <typename Key, typename E> BSTNode<Key, E>* BST<Key, E>:: getmin (BSTNode<Key, E>* rt) { if (rt->left() == NULL) 127 128 129 130 131 132 return rt; 133 else return getmin (rt->left()); 134 135 template <typename Key, typename E> BSTNode<Key, E>* BST<Key, E>:: edeletemin (BSTNode<Key, E>* rt) { if (rt->left () == NULL) // Found min return rt->right(); 136 137 138 139 140 else { // Continue left 141 rt->setLeft (deletemin (rt->left () )); 142 return rt; 143 144 145 // Remove a node with key value k // Return: The tree with the node removed template <typename Key, typename E> BSTNode<Key, E>* BST<Key, E>:: removehelp (BSTNode<Key, E>* rt, const Keys k) { if (rt == NULL) return NULL; 146 147 148 149 150 151 // k is not in tree else if (k < rt->key ()) rt->setLeft (removehelp (rt->left (), k)); else if (k > rt->key () ) rt->setRight (removehelp (rt->right(), k)); 152 153 154 155 156 else { // Found: remove it BSTNode<Key, E>* temp = if (rt->left () rt = rt->right(); delete temp; 157 rt; // Only a right child // so point to right 158 == NULL) { 159 160
// Binary Search Tree implementation for the Dictionary ADT template <typename Key, typename E> class BST : public Dictionary<Key,E> { private: BSTNode<Key,E>* root; // Root of the BST int nodecount; // Number of nodes in the BST // Private "helper" functions void clearhelp (BSTNode<Key, E>*); BSTNode<Key,E>* inserthelp (BSTNode<Key, E>*, const Key&, const E&); BSTNode<Key, E>* deletemin (BSTNode<Key, E>*); BSTNode<Key,E>* getmin (BSTNode<Key, E>*); BSTNode<Key,E>* removehelp (BSTNode<Key, E>*, const Key&) ; E* findhelp (BSTNode<Key, E>*, const Key&) const; void printhelp (BSTNode<Key, E>*, int) const; void vist (BSTNode<Key, E>*) const; public: BST () { root = NULL; nodecount = 0; } // Constructor -- I've commented out the destructor //Note from Prof Sipantzi //since you would have to change clearhelp () to make it work with //doubly-threaded trees and that is not part of the assignment. // ~BST () { clearhelp(root); } // Destructor void clear() // Reinitialize tree { clearhelp(root); root = NULL; nodecount = 0; } // Insert a record into the tree. // k Key value of the record. // e The record to insert. void insert(const Key& k, const E& e) { root = inserthelp (root, k, e); nodecount++; } // Remove a record from the tree. // k Key value of record to remove. // Return: The record removed, or NULL if there is none. E* remove (const Key& k) { E* temp = if (temp != NULL) { root = removehelp (root, k); findhelp (root, k); // First find it nodecount--; } return temp; } // Remove and return the root node from the dictionary. // Return: The record removed, null if tree is empty. E* removeAny() { // Delete min value if (root != NULL) { E* temp = new E; *temp = root->element (); root = removehelp (root, root->key()); nodecount--; return temp; } else return NULL; }
Transcribed Image Text:// Binary Search Tree implementation for the Dictionary ADT template <typename Key, typename E> class BST : public Dictionary<Key,E> { private: BSTNode<Key,E>* root; // Root of the BST int nodecount; // Number of nodes in the BST // Private "helper" functions void clearhelp (BSTNode<Key, E>*); BSTNode<Key,E>* inserthelp (BSTNode<Key, E>*, const Key&, const E&); BSTNode<Key, E>* deletemin (BSTNode<Key, E>*); BSTNode<Key,E>* getmin (BSTNode<Key, E>*); BSTNode<Key,E>* removehelp (BSTNode<Key, E>*, const Key&) ; E* findhelp (BSTNode<Key, E>*, const Key&) const; void printhelp (BSTNode<Key, E>*, int) const; void vist (BSTNode<Key, E>*) const; public: BST () { root = NULL; nodecount = 0; } // Constructor -- I've commented out the destructor //Note from Prof Sipantzi //since you would have to change clearhelp () to make it work with //doubly-threaded trees and that is not part of the assignment. // ~BST () { clearhelp(root); } // Destructor void clear() // Reinitialize tree { clearhelp(root); root = NULL; nodecount = 0; } // Insert a record into the tree. // k Key value of the record. // e The record to insert. void insert(const Key& k, const E& e) { root = inserthelp (root, k, e); nodecount++; } // Remove a record from the tree. // k Key value of record to remove. // Return: The record removed, or NULL if there is none. E* remove (const Key& k) { E* temp = if (temp != NULL) { root = removehelp (root, k); findhelp (root, k); // First find it nodecount--; } return temp; } // Remove and return the root node from the dictionary. // Return: The record removed, null if tree is empty. E* removeAny() { // Delete min value if (root != NULL) { E* temp = new E; *temp = root->element (); root = removehelp (root, root->key()); nodecount--; return temp; } else return NULL; }
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Hash Table
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS