In this assignment, you are going to implement GeneralTree, a class similar to t

Question

In this assignment, you are going to implement GeneralTree, a class similar to the tree class I implemented in class but with the following differences:

The value of each node is a character, not an integer.

Each node can have any number of children.

Inserting a node requires specifying the parent node under which it is inserted.

There is no find() method.

Your class is expected to implement the following methods. Please read the comments below very carefully so that you understand what is expected!

// A default constructor. This should explicitly set

// the start node to be NULL.

GeneralTree();

// A copy constructor. This should also explicitly

// set the start node to be NULL, and then it should

// copy the contents of other into the current tree.

GeneralTree(const GeneralTree& other);

// A destructor. This should traverse the tree, freeing

// all nodes. Remember to free children before you

// free parents!

~GeneralTree();

// An assignment operator. This should behave like the

// example I gave in class. If other is not the same

// as the current tree, remove everything from the current

// tree and copy the contents of other into the current

// tree.

GeneralTree& operator=(const GeneralTree& other);

// An insert method. This method is tricky. If the parent

// given is NULL and the start node of the current tree

// is not NULL, you should throw an exception called

// NoParentException that you define in the header

// file. MAKE SURE THAT NO MEMORY GETS LEAKED HERE!

// If you created a node already and you’re about to

// throw an exception, delete the node first!

//

// If the parent given is NULL and the start node

// of the current tree is also NULL, this is fine. You

// should just create a new node with the given value

// and make it the start node.

//

// If the parent given is not NULL, make a new node with

// the given value and add it to the parent node’s children.

// Return the node you just inserted.

Node* insert(char value, Node* parent);

// A method to print the tree. You should print it using the

// following syntax: for non-leaf nodes (nodes that have

// more than zero children), print an open parenthesis, then

// the node’s children, then a close parenthesis. For leaf

// nodes (nodes with zero children), just print the node’s

// character value. This should appear all on one line,

// with a newline at the end.

//

//

// Notice that the character values of non-leaf nodes

// are ignored, so the periods never get printed.

void print() const;

You should also probably have the following helper methods:

// Basically the same as in my example. Just make a call to

// copyFrom (see below - copyFrom looks different!).

void copyOther(const GeneralTree& other);

// Also same as the example. Make a call to clearFrom

// (again, see below).

void clear();

// Recursivley print a subtree whose root is the given start node.

// Use the notation described above for print().

void printFrom(Node* start) const;

// Recursively copy into the current tree from another tree.

// The starting point for the other tree is start. The parent

// argument is the argument to be passed to a call to insert().

//

// Just to clarify:

//   - The variable “start” corresponds to a node in the tree

//     you are copying FROM.

//   - The variable “parent” corresponds to a node in the

//     tree you are copying TO.

void copyFrom(Node* start, Node* parent)

// Recursively delete all nodes in the tree.

void clearFrom(Node* start);

Since this is a fairly substantial assignment, I have provided a main.cpp for you to use to test your program, linked to from this week’s section on iLearn. It contains a recursive parser that reads a string corresponding to the print of some tree and then reconstructs the tree. Check it out! Make sure this program prints what it says it should print in its comments. Note that this file is not sufficient to test your whole class! You should add tests to make sure each of your methods works in all cases.

Some general reminders:

Don’t let your program crash anywhere in your GeneralTree code.

Don’t allow any memory leaks! (Make sure your destructor and the helper methods it uses are correct, and make sure any node you create either gets attached to a parent node or freed.)

HERE is the main.cpp file to start from which includes the main method and a recursive parser :

#include "GeneralTree.h"
#include
using namespace std;

void parseRecursive(stringstream& ss, GeneralTree& gt, Node* parent)
{
   char nextChar;
   while (true) {
       ss >> nextChar;
       if (ss.fail())
           return;

       if (nextChar == ')')
           return;

       if (nextChar == '(') {
           Node* newNode = gt.insert(' ', parent);
           parseRecursive(ss, gt, newNode);
       } else {
           gt.insert(nextChar, parent);
       }
   }
}

void parseExpression(const string& expr, GeneralTree& gt)
{
   stringstream ss;
   ss << expr;

   parseRecursive(ss, gt, NULL);
}

int main()
{
   // This should print:
   // (c(ab))
   GeneralTree gt;
   Node* grandparent = gt.insert('.', NULL);
   Node* parent1 = gt.insert('c', grandparent);
   Node* parent2 = gt.insert('.', grandparent);
   Node* kid1 = gt.insert('a', parent2);
   Node* kid2 = gt.insert('b', parent2);
   gt.print();

   // This should print:
   // (abab(cd)d(ef(g(h))))
   GeneralTree gt2;
   parseExpression("(abab(cd)d(ef(g(h))))", gt2);
   gt2.print();

   // This should print:
   // (c(ab))
   GeneralTree gt3 = gt;
   gt3.print();

   // This should print:
   // (abab(cd)d(ef(g(h))))
   GeneralTree gt4(gt2);
   gt4.print();

   return 0;
}

Explanation / Answer

Answer :

#include <iostream>
using namespace std;

struct TreeNode
{
int Key;
float fValue;
int iValue;
char cArray[7];
TreeNode *left;
TreeNode *right;
};

class Code_Tree
{
private:
TreeNode *root;

public:
Code_Tree();
~Code_Tree();
bool isEmpty();
TreeNode *SearchTree(int Key);
int Insert(TreeNode *newNode);
int Insert(int Key, float f, int i, char *cA);
int Delete(int Key);
void PrintOne(TreeNode *T);
void PrintTree();
private:
void ClearTree(TreeNode *T);
TreeNode *DupNode(TreeNode * T);
void PrintAll(TreeNode *T);
};

#include <iostream>
#include <string.h>
#include "Code_Tree.h"

using namespace std;

Code_Tree::Code202_Tree()
{
root = NULL;
return;
}
Code_Tree::~Code202_Tree()
{
ClearTree(root);
return;
}

void Code_Tree::ClearTree(TreeNode *T)
{
if(T==NULL) return; // Nothing to clear
if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree
if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree
delete T;
return;
}

bool Code_Tree::isEmpty()
{
return(root==NULL);
}

TreeNode *Code_Tree::DupNode(TreeNode * T)
{
TreeNode *dupNode;

dupNode = new TreeNode();
*dupNode = *T; // Copy the data structure
dupNode->left = NULL; // Set the pointers to NULL
dupNode->right = NULL;
return dupNode;
}

TreeNode *Code_Tree::SearchTree(int Key)
{
int ValueInTree = false;
TreeNode *temp;

temp = root;
while((temp != NULL) && (temp->Key != Key))
{
if(Key < temp->Key)
temp = temp->left; // Search key comes before this node.
else
temp = temp->right; // Search key comes after this node
}
if(temp == NULL) return temp; // Search key not found
else
return(DupNode(temp)); // Found it so return a duplicate
}

int Code_Tree::Insert(TreeNode *newNode)
{
TreeNode *temp;
TreeNode *back;

temp = root;
back = NULL;

while(temp != NULL) // Loop till temp falls out of the tree
{
back = temp;
if(newNode->Key < temp->Key)
temp = temp->left;
else
temp = temp->right;
}

if(back == NULL)
root = newNode;
else
{
if(newNode->Key < back->Key)
back->left = newNode;
else
back->right = newNode;
}
return(true);
}

int Code_Tree::Insert(int Key, float f, int i, char *cA)
{
TreeNode *newNode;

// Create the new node and copy data into it
newNode = new TreeNode();
newNode->Key = Key;
newNode->fValue = f;
newNode->iValue = i;
strcpy(newNode->cArray, cA);
newNode->left = newNode->right = NULL;

return(Insert(newNode));
}

int Code_Tree::Delete(int Key)
{
TreeNode *back;
TreeNode *temp;
TreeNode *delParent;
TreeNode *delNode;

temp = root;
back = NULL;

  
while((temp != NULL) && (Key != temp->Key))
{
back = temp;
if(Key < temp->Key)
temp = temp->left;
else
temp = temp->right;
}

if(temp == NULL)
{
cout << "Key not found. Nothing deleted. ";
return false;
}
else
{
if(temp == root)
{
delNode = root;
delParent = NULL;
}
else
{
delNode = temp;
delParent = back;
}
}
if(delNode->right == NULL)
{
if(delParent == NULL)
{
root = delNode->left;
delete delNode;
return true;
}
else
{
if(delParent->left == delNode)
delParent->left = delNode->left;
else
delParent->right = delNode->left;
delete delNode;
return true;
}
}
else
{
if(delNode->left == NULL)
{
if(delParent == NULL)
{
root = delNode->right;
delete delNode;
return true;
}
else
{
if(delParent->left == delNode)
delParent->left = delNode->right;
else
delParent->right = delNode->right;
delete delNode;
return true;
}
}
else
{
  
temp = delNode->left;
back = delNode;
while(temp->right != NULL)
{
back = temp;
temp = temp->right;
}
  
delNode->Key = temp->Key;
delNode->fValue = temp->fValue;
delNode->iValue = temp->iValue;
strcpy(delNode->cArray, temp->cArray);

if(back == delNode)
back->left = temp->left;
else
back->right = temp->left;
delete temp;
return true;
}
}
}

void Code_Tree::PrintOne(TreeNode *T)
{
cout << T->Key << " " << T->fValue << " " << T->iValue << " "
<< T->cArray << " ";
}

void Code_Tree::PrintAll(TreeNode *T)
{
if(T != NULL)
{
PrintAll(T->left);
PrintOne(T);
PrintAll(T->right);
}
}

void Code_Tree::PrintTree()
{
PrintAll(root);
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects