Question: 2. Requirements: Using the above code, you are asked to extend the TreeType class to support the following member functions: 1. Implement a member function
2. Requirements: Using the above code, you are asked to extend the TreeType class to support the following member functions:
1. Implement a member function IsFullTree to test whether the tree is full or not.
Implement a member function IsBST to test whether the tree is a binary search tree, i.e., whether for each node in the tree, its value is larger than values stored in nodes in its left subtree, and smaller than values stored in nodes in its right subtree.
Write a member function GetNodesAtLevel that returns an array of items stored in the given level of the tree:
/* return the number of nodes in the given level, itemArray[0...] stores the items values precondition: level <= 0 */ int TreeType::GetNodesAtLevel (ItemType * itemArray, int level) { //Todo by you... } Write a member function Ancestors that prints the ancestors of a given node (whose info field contains the given value)
//Display the items stored in the parent of the node, the grandparent, and so on //starting from root (ancestor of all nodes), ... all the way to the parent of the node void TreeType::PrintAncestors (ItemType value) { } Add a member function GetSmallest that returns the value of the smallest item stored in the tree. Note that in doing so, you should introduce a helper (recursive) function that takes a TreeType pointer as parameter:
void GetSmallest (TreeType * root, ItemType & smallest) { //... } void TreeType::GetSmallest (ItemType & smallest) const { // ... } Modify DeleteNode function in the TreeType.cpp, so that in case (Case 3 in the code below) the node has left and right child, it will replace the node's value with that of its successor (i.e., the smallest value in its right tree), and then delete the successor node from the right subtree. You should use the function GetSmallest to find the sucessor of the node.
void DeleteNode(TreeNode*& tree) // Deletes the node pointed to by tree. // Post: The user's data in the node pointed to by tree is no // longer in the tree. If tree is a leaf node or has only one // non-NULL child pointer the node pointed to by tree is // deleted, and tree is updated to point to the non-NULL child, // otherwise, the user's data is replaced by its // logical predecessor and the predecessor's node is deleted. { ItemType data; TreeNode* tempPtr; tempPtr = tree; if (tree->left == NULL) { tree = tree->right; delete tempPtr; } else if (tree->right == NULL) { tree = tree->left; delete tempPtr; } else { //Case 3: If the node has left child and right child ... //find the predecessor value, i.e., the largest value in the left subtree GetLargest(tree->left, data); //store the predessor value in the curret node ... tree->info = data; // delete the predecessor value from the left subtree Delete(tree->left, data); // Delete predecessor node. } } In the main.cpp, add an option for creating a balanced BST from an array of char, such that the medium value in the array is the root of the tree, and the left and right subtrees have same number of nodes...
TreeType::TreeType (ItemType items[], int len) { //Initialize the tree (binary search tree) with items given in the // array (length of the array is passed as "len" // You need to make the tree so that it's height is as short as possible // You should consider calling a recursive function to do so } // in main() main() { ... case 'O': //declare earler in main... char words[26]; cout <<"Enter a string..."; cin >> words; //sort the char array (using bubble sort or selection sort) //call the above constructor function of TreeType to build the optimal BST tree (the implementation of the member function shall make use of a recursive function): break;
________________________________________________________
//TreeType.h
#include
#include
typedef char ItemType;
struct TreeNode;
#include "QueType.h"
enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};
class TreeType
{
public:
TreeType(); // constructor
~TreeType(); // destructor
TreeType(const TreeType& originalTree);
void operator=(const TreeType& originalTree);
// copy constructor
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
int GetLength() const;
int GetHeight() const;
ItemType GetItem(ItemType item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetTree(OrderType order);
ItemType GetNextItem(OrderType order, bool& finished);
void Print(std::ostream& out) const;
void PrettyPrint() const;
void SimplePrettyPrint() const;
private:
TreeNode* root;
QueType preQue;
QueType inQue;
QueType postQue;
};
//TreeType.cpp
#include
#include
#include
#include
#include "TreeType.h"
using namespace std;
struct TreeNode
{
ItemType info;
TreeNode* left;
TreeNode* right;
};
bool TreeType::IsFull() const
// Returns true if there is no room for another item
// on the free store; false otherwise.
{
TreeNode* location;
try
{
location = new TreeNode;
delete location;
return false;
}
catch(std::bad_alloc exception)
{
return true;
}
}
bool TreeType::IsEmpty() const
// Returns true if the tree is empty; false otherwise.
{
return root == NULL;
}
int CountNodes(TreeNode* tree);
int TreeType::GetLength() const
// Calls recursive function CountNodes to count the
// nodes in the tree.
{
return CountNodes(root);
}
int CountNodes(TreeNode* tree)
// Post: returns the number of nodes in the tree.
{
if (tree == NULL)
return 0;
else
return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}
void Retrieve(TreeNode* tree,
ItemType& item, bool& found);
ItemType TreeType::GetItem(ItemType item, bool& found)
// Calls recursive function Retrieve to search the tree for item.
{
Retrieve(root, item, found);
return item;
}
void Retrieve(TreeNode* tree,
ItemType& item, bool& found)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item's,
// found is true and item is set to a copy of someItem;
// otherwise found is false and item is unchanged.
{
if (tree == NULL)
found = false; // item is not found.
else if (item < tree->info)
Retrieve(tree->left, item, found); // Search left subtree.
else if (item > tree->info)
Retrieve(tree->right, item, found);// Search right subtree.
else
{
item = tree->info; // item is found.
found = true;
}
}
void Insert(TreeNode*& tree, ItemType item);
void TreeType::PutItem(ItemType item)
// Calls recursive function Insert to insert item into tree.
{
Insert(root, item);
}
void Insert(TreeNode*& tree, ItemType item)
// Inserts item into tree.
// Post: item is in tree; search property is maintained.
{
if (tree == NULL)
{// Insertion place found.
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if (item < tree->info)
Insert(tree->left, item); // Insert in left subtree.
else
Insert(tree->right, item); // Insert in right subtree.
}
void DeleteNode(TreeNode*& tree);
void Delete(TreeNode*& tree, ItemType item);
void TreeType::DeleteItem(ItemType item)
// Calls recursive function Delete to delete item from tree.
{
Delete(root, item);
}
void Delete(TreeNode*& tree, ItemType item)
// Deletes item from tree.
// Post: item is not in tree.
{
if (item < tree->info)
Delete(tree->left, item); // Look in left subtree.
else if (item > tree->info)
Delete(tree->right, item); // Look in right subtree.
else
DeleteNode(tree); // Node found; call DeleteNode.
}
void GetLargest(TreeNode* tree, ItemType& data);
void DeleteNode(TreeNode*& tree)
// Deletes the node pointed to by tree.
// Post: The user's data in the node pointed to by tree is no
// longer in the tree. If tree is a leaf node or has only one
// non-NULL child pointer the node pointed to by tree is
// deleted, and tree is updated to point to the non-NULL child,
// otherwise, the user's data is replaced by its
// logical predecessor and the predecessor's node is deleted.
{
ItemType data;
TreeNode* tempPtr;
tempPtr = tree;
if (tree->left == NULL)
{
tree = tree->right;
delete tempPtr;
}
else if (tree->right == NULL)
{
tree = tree->left;
delete tempPtr;
}
else
{
GetLargest(tree->left, data);
tree->info = data;
Delete(tree->left, data); // Delete predecessor node.
}
}
void GetLargest(TreeNode* tree, ItemType& data)
// Sets data to the info member of the right-most node in tree.
// i.e., the largest item
{
while (tree->right != NULL)
{
tree = tree->right;
}
data = tree->info;
}
void PrintTree(TreeNode* tree, std::ostream& outFile)
// Prints info member of items in tree in sorted order on outFile.
{
if (tree != NULL)
{
PrintTree(tree->left, outFile); // Print left subtree.
outFile << tree->info;
PrintTree(tree->right, outFile); // Print right subtree.
}
}
void TreeType::Print(std::ostream& outFile) const
// Calls recursive function Print to print items in the tree.
{
PrintTree(root, outFile);
}
///////////////////////////////
//Pretty print
//
//Return the height of the tree that is rooted at the rootNode
int getHeight (TreeNode * rootNode)
{
if (rootNode==NULL)
return 0;
else {
int left = getHeight (rootNode->left);
int right = getHeight (rootNode->right);
if (left<=right)
return right+1;
else
return left+1;
}
}
int TreeType::GetHeight() const
{
return (getHeight(root));
}
//Store the nodes at the depth-level of the tree (given at root)
//in the vector of vals
//Precondition: root!=NULL, depth >= 0
void getLine (TreeNode * root, int depth, vector
{
assert (root!=NULL && depth>=0);
if (depth==0){ //base case
vals.push_back (root->info);
}
else { //general case ...
if (root->left != NULL)
getLine (root->left, depth-1, vals);
else //EZ if (depth-1<=0)
{
int cnt=1;
for (int i=0;i cnt*=2; for (int i=0;i vals.push_back ('#'); } if (root->right!=NULL) getLine (root->right, depth-1, vals); else //if (depth-1<=0) { int cnt=1; for (int i=0;i cnt*=2; for (int i=0;i vals.push_back ('#'); } } } void printRow (TreeNode * p, int height, int depth) { vector getLine(p, depth, vec); /* for (int i=0;i if (vec[i] != ' ') cout << vec[i] << " "; else { assert (false); cout << "# " ; } cout < */ cout << setw((height - depth)*2); // scale setw with depth bool toggle = true; // start with left if (vec.size() > 1) { //for (int v : vec) { for (int i=0; i if (vec[i] != ' ') { if (toggle) cout << "/" << " "; else cout << "\\" << " "; //this will display } toggle = !toggle; } cout << endl; cout << setw((height - depth)*2); } for (int i=0;i if (vec[i] != ' ') cout << vec[i] << " "; cout << endl; } void SimplePrintRow (TreeNode * p, int height, int depth) { vector getLine(p, depth, vec); for (int i=0;i if (vec[i] != ' ') cout << vec[i]; else { assert (false); cout << "# " ; } cout < } void TreeType::PrettyPrint () const { int height = getHeight (root); //*2; for (int i=0;i { printRow (root, height, i); } } void TreeType::SimplePrettyPrint () const { int height = getHeight (root); //*2; for (int i=0;i { SimplePrintRow (root, height, i); } } //Pretty print /////////////////////////////// TreeType::TreeType() { root = NULL; } void Destroy(TreeNode*& tree); TreeType::~TreeType() // Calls recursive function Destroy to destroy the tree. { Destroy(root); } void Destroy(TreeNode*& tree) // Post: tree is empty; nodes have been deallocated. { if (tree != NULL) { Destroy(tree->left); Destroy(tree->right); delete tree; } } void TreeType::MakeEmpty() { Destroy(root); root = NULL; } void CopyTree(TreeNode*& copy, const TreeNode* originalTree); TreeType::TreeType(const TreeType& originalTree) // Calls recursive function CopyTree to copy originalTree // into root. { CopyTree(root, originalTree.root); } void TreeType::operator= (const TreeType& originalTree) // Calls recursive function CopyTree to copy originalTree // into root. { { if (&originalTree == this) return; // Ignore assigning self to self Destroy(root); // Deallocate existing tree nodes CopyTree(root, originalTree.root); } } void CopyTree(TreeNode*& copy, const TreeNode* originalTree) // Post: copy is the root of a tree that is a duplicate // of originalTree. { if (originalTree == NULL) copy = NULL; else { copy = new TreeNode; copy->info = originalTree->info; CopyTree(copy->left, originalTree->left); CopyTree(copy->right, originalTree->right); } } // Function prototypes for auxiliary functions. void PreOrder(TreeNode*, QueType&); // Enqueues tree items in preorder. void InOrder(TreeNode*, QueType&); // Enqueues tree items in inorder. void PostOrder(TreeNode*, QueType&); // Enqueues tree items in postorder. void TreeType::ResetTree(OrderType order) // Calls function to create a queue of the tree elements in // the desired order. { switch (order) { case PRE_ORDER : PreOrder(root, preQue); break; case IN_ORDER : InOrder(root, inQue); break; case POST_ORDER: PostOrder(root, postQue); break; } } void PreOrder(TreeNode* tree, QueType& preQue) // Post: preQue contains the tree items in preorder. { if (tree != NULL) { preQue.Enqueue(tree->info); PreOrder(tree->left, preQue); PreOrder(tree->right, preQue); } } void InOrder(TreeNode* tree, QueType& inQue) // Post: inQue contains the tree items in inorder. { if (tree != NULL) { InOrder(tree->left, inQue); inQue.Enqueue(tree->info); InOrder(tree->right, inQue); } } void PostOrder(TreeNode* tree, QueType& postQue) // Post: postQue contains the tree items in postorder. { if (tree != NULL) { PostOrder(tree->left, postQue); PostOrder(tree->right, postQue); postQue.Enqueue(tree->info); } } ItemType TreeType::GetNextItem(OrderType order, bool& finished) // Returns the next item in the desired order. // Post: For the desired order, item is the next item in the queue. // If item is the last one in the queue, finished is true; // otherwise finished is false. { finished = false; ItemType item; switch (order) { case PRE_ORDER : preQue.Dequeue(item); if (preQue.IsEmpty()) finished = true; break; case IN_ORDER : inQue.Dequeue(item); if (inQue.IsEmpty()) finished = true; break; case POST_ORDER: postQue.Dequeue(item); if (postQue.IsEmpty()) finished = true; break; } return item; } bool TreeType::IsBST(TreeNode *rootNode, int & smallest, int & largest) { if (rootNode->left == NULL && right == NULL) { smallest = largest = rootNode->info; return; } else { if (rootNode-> left != NULL) { if (IsBST(rootNode->left, ls, ll)); //declare another variable { if (rootNode->value>ll) { } } } } } /* return the number of nodes in the given level, itemArray[0...] stores the items values precondition: level <= 0 */ int TreeType::GetNodesAtLevel (ItemType * itemArray, int level) { //Todo by you... } //Display the items stored in the parent of the node, the grandparent, and so on //starting from root (ancestor of all nodes), ... all the way to the parent of the node void TreeType::PrintAncestors (ItemType value) { } //Test whether tree is full or not void TreeType::IsFullTree (ItemType ) { } //QueType.h #include #include class FullQueue {}; class EmptyQueue {}; typedef char ItemType; struct NodeType; class QueType { public: QueType(); // Class constructor. // Because there is a default constructor, the precondition // that the queue has been initialized is omitted. QueType(int max); // Parameterized class constructor. ~QueType(); // Class destructor. QueType(const QueType& anotherQue); // Copy constructor void MakeEmpty(); // Function: Initializes the queue to an empty state. // Post: Queue is empty. bool IsEmpty() const; // Function: Determines whether the queue is empty. // Post: Function value = (queue is empty) bool IsFull() const; // Function: Determines whether the queue is full. // Post: Function value = (queue is full) void Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue. // Post: If (queue is full) FullQueue exception is thrown // else newItem is at rear of queue. void Dequeue(ItemType& item); // Function: Removes front item from the queue and returns it in item. // Post: If (queue is empty) EmptyQueue exception is thrown // and item is undefined // else front element has been removed from queue and // item is a copy of removed element. private: NodeType* front; NodeType* rear; }; //QueType.cpp #include #include #include "QueType.h" struct NodeType { ItemType info; NodeType* next; }; QueType::QueType() // Class constructor. // Post: front and rear are set to NULL. { front = NULL; rear = NULL; } void QueType::MakeEmpty() // Post: Queue is empty; all elements have been deallocated. { NodeType* tempPtr; while (front != NULL) { tempPtr = front; front = front->next; delete tempPtr; } rear = NULL; } // Class destructor. QueType::~QueType() { MakeEmpty(); } bool QueType::IsFull() const // Returns true if there is no room for another ItemType // on the free store; false otherwise. { NodeType* location; try { location = new NodeType; delete location; return false; } catch(std::bad_alloc) { return true; } } bool QueType::IsEmpty() const // Returns true if there are no elements on the queue; false otherwise. { return (front == NULL); } void QueType::Enqueue(ItemType newItem) // Adds newItem to the rear of the queue. // Pre: Queue has been initialized. // Post: If (queue is not full) newItem is at the rear of the queue; // otherwise a FullQueue exception is thrown. { if (IsFull()) throw FullQueue(); else { NodeType* newNode; newNode = new NodeType; newNode->info = newItem; newNode->next = NULL; if (rear == NULL) front = newNode; else rear->next = newNode; rear = newNode; } } void QueType::Dequeue(ItemType& item) // Removes front item from the queue and returns it in item. // Pre: Queue has been initialized and is not empty. // Post: If (queue is not empty) the front of the queue has been // removed and a copy returned in item; // othersiwe a EmptyQueue exception has been thrown. { if (IsEmpty()) throw EmptyQueue(); else { NodeType* tempPtr; tempPtr = front; item = front->info; front = front->next; if (front == NULL) rear = NULL; delete tempPtr; } } QueType::QueType (const QueType& anotherQue) { NodeType* ptr1; NodeType* ptr2; if (anotherQue.front == NULL) front = NULL; else { front = new NodeType; front->info = anotherQue.front->info; ptr1 = anotherQue.front->next; ptr2 = front; while (ptr1 != NULL) { ptr2->next = new NodeType; ptr2 = ptr2->next; ptr2->info = ptr1->info; ptr1 = ptr1->next; } ptr2->next = NULL; rear = ptr2; } } //main.cpp // Test driver #include #include #include #include #include #include "TreeType.h" using namespace std; int main() { char command; // operation to be executed char item; char ret; string orderItem; TreeType tree; OrderType order; bool found; bool finished; int numCommands; string str; do { cout <<"Choose what to do: "; cout <<"------------------------- "; cout <<"A: PutItem "; cout <<"D: DeleteItem "; cout <<"S: GetItem "; cout <<"I: info. length, IsFull, height... "; cout <<"P: PrintTree "; cout <<"Q: SimplePrintTree "; cout <<"R: (Iterator) ResetTree, GetNextItem "; cout <<"C: MakeEmpty "; cout <<"B: Build Tree from array "; cout <<"E: Quit "; cout <<"------------------------- "; cin >> command; switch (command) { case 'B': cout <<"Enter a string of chars to build a tree: "; cin >> str; tree.MakeEmpty(); for (int i=0;i { ret = tree.GetItem(str[i], found); if (!found) tree.PutItem (str[i]); } break; case 'A': cout <<"Enter a char to insert: "; cin >> item; item = tree.GetItem(item, found); if (found) cout << item << " already in list." << endl; else { tree.PutItem(item); cout << item; cout << " is inserted" << endl; } break; case 'D': cout <<"Enter a char to delete: "; cin >> item; tree.DeleteItem(item); cout << item; cout << " is deleted" << endl; break; case 'S': cout <<"Enter a char to search: "; cin >> item; item = tree.GetItem(item, found); if (found) cout << item << " found in list." << endl; else cout << item << " not in list." << endl; break; case 'I': cout << "Number of nodes is " << tree.GetLength() << endl; cout << "Height of tree is " << tree.GetHeight() << endl; if (tree.IsEmpty()) cout << "Tree is empty." << endl; else cout << "Tree is not empty." << endl; if (tree.IsFull()) cout << "Tree is full." << endl; else cout << "Tree is not full." << endl; break; case 'P': tree.PrettyPrint(); cout << endl; break; case 'Q': tree.SimplePrettyPrint(); cout << endl; break; case 'R': cout <<"traversal order (preorder, inorder or postorder)"; cin >> orderItem; if (orderItem == "preorder") order = PRE_ORDER; else if (orderItem == "inorder") order = IN_ORDER; else order = POST_ORDER; cout <<"traversing nodes in the given order:"; tree.ResetTree(order); do { item = tree.GetNextItem(order,finished); cout << item; } while (!finished); cout << endl; break; case 'C': tree.MakeEmpty(); cout << "Tree has been made empty." << endl; break; case 'E': cout <<"Ok, Exiting "; break; default: cout << " Command not recognized." << endl; } } while (command != 'E'); return 0; }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help