#include #include #include #define MAX_STR_LEN 100 // int strcmp (const char* st

Question

#include
#include
#include

#define MAX_STR_LEN 100

// int strcmp (const char* str1, const char* str2); // string.h
// Compares the C string str1 to the C string str2.
// This function starts comparing the first character of each string.
// If they are equal to each other, it continues with the following pairs
// until the characters differ or until a terminating null-character is reached.
// This function performs a binary comparison of the characters.
// For a function that takes into account locale-specific rules, see strcoll.

// Do not change "class CTreeNode"
using namespace std;

class CTreeNode {
public:
   char m_strKeyString [MAX_STR_LEN];  
   CTreeNode* m_pLeftChild;
   CTreeNode* m_pRightChild;
  
   CTreeNode () {
       m_strKeyString [0] = '';   // initially the key string is empty
       m_pLeftChild = NULL;
       m_pRightChild = NULL;
   };  
};

class BSTree{
   public:
       BSTree()
       {
           root = NULL;
       };
  
       void insert (char cKey [])
       {
           if(root != NULL)
           {
               insert(cKey, root);
           }
           else
           {
               root = new CTreeNode;
//               root->m_strKeyString = cKey;
               strcpy(root->m_strKeyString, cKey);
               root->m_pLeftChild = NULL;
               root->m_pRightChild = NULL;
           }
       };
      
       void inorderPrint ()
       {
           if (root!=NULL)
               inorderPrint(root);
       };
      
      
   private:
       void insert(char cKey[], CTreeNode *leaf )
       {
           if (strcmp(cKey, leaf->m_strKeyString) < 0)
           {
               if (leaf->m_pLeftChild != NULL)
                   insert(cKey, leaf->m_pLeftChild);
               else
               {
                   leaf->m_pLeftChild = new CTreeNode;
               //   leaf->m_pLeftChild->m_strKeyString = cKey;
                   strcpy(leaf->m_pLeftChild->m_strKeyString, cKey);
                   leaf->m_pLeftChild->m_pLeftChild = NULL;
                   leaf->m_pLeftChild->m_pRightChild = NULL;
               }
           }
           else if (strcmp(cKey, leaf->m_strKeyString) >= 0)
           {
               if (leaf->m_pRightChild != NULL)
                   insert(cKey, leaf->m_pRightChild);
               else
               {
                   leaf->m_pRightChild = new CTreeNode;
               //   leaf->m_pRightChild->m_strKeyString = cKey;
                   strcpy(leaf->m_pRightChild->m_strKeyString, cKey);
                   leaf->m_pRightChild->m_pLeftChild = NULL;
                   leaf->m_pRightChild->m_pRightChild = NULL;
               }
           }
       };
      
       void inorderPrint (CTreeNode *leaf)
       {
           if (leaf != NULL)
           {
               inorderPrint(leaf->m_pLeftChild);
               cout << leaf->m_strKeyString << endl;
               inorderPrint(leaf->m_pRightChild);
           }
       };
      
       CTreeNode *root;  
};

int main (int argc, char* argv [])
{
   char* pstrIntput [] = {"move", "look", "new", "apple", "printer,", "program", "special", "eagle", "cheese", "zoo", "climb", "class"};
   int nInputCount = 12;
  
   BSTree tree;
  
   for (int i = 0; i    {
       tree.insert(pstrIntput[i]);
//       cout << pstrIntput[i];
   }
   tree.inorderPrint();

   // printf ("%s ", pstrIntput [0]);
  
   /****************************** Problem 1 (10 points) ********************************/
   // Construct a Binary Search Tree (BSTree) using CTreeNode with pstrIntput as a base input.
   // Once the BSTree is constructed, print out the key strings using inorder traversal.
   // Must use "CTreeNode" to contstruct BSTree. Only print out the collect order of the string will not grant any point.
   // No Partial Credit will be given!
  
  
  
  
   /****************************** Problem 2 (10 points) ********************************/
   // Construct a Min Heap CTreeNode with pstrIntput as a base input. -- Therefore, apple should be the root
   // Once the tree is constructed is constructed, print out the key strings using preorder traversal.
   // Must use "CTreeNode" to contstruct the heap tree. Only print out the collect order of the string will not grant any point.
   // No Partial Credit will be given!
  
  
  

   return 0;
}

//Please help me with problem #2

Explanation / Answer

Problem1

#include<iostream>
#include<string.h>
#define MAX_STR_LEN 100
using namespace std;
class CTreeNode {
public:
char m_strKeyString [MAX_STR_LEN];
CTreeNode* m_pLeftChild;
CTreeNode* m_pRightChild;
  
CTreeNode () {
m_strKeyString [0] = '';   
m_pLeftChild = NULL;
m_pRightChild = NULL;
};
};
class BSTree{
public:
BSTree()
{
root = NULL;
};
  
void insert (char cKey [])
{
if(root != NULL)
{
insert(cKey, root);
}
else
{
root = new CTreeNode;
strcpy(root->m_strKeyString, cKey);
root->m_pLeftChild = NULL;
root->m_pRightChild = NULL;
}
};
  
void inorderPrint ()
{
if (root!=NULL)
inorderPrint(root);
};
  
  
private:
void insert(char cKey[], CTreeNode *leaf )
{
if (strcmp(cKey, leaf->m_strKeyString) < 0)
{
if (leaf->m_pLeftChild != NULL)
insert(cKey, leaf->m_pLeftChild);
else
{
leaf->m_pLeftChild = new CTreeNode;
strcpy(leaf->m_pLeftChild->m_strKeyString, cKey);
leaf->m_pLeftChild->m_pLeftChild = NULL;
leaf->m_pLeftChild->m_pRightChild = NULL;
}
}
else if (strcmp(cKey, leaf->m_strKeyString) >= 0)
{
if (leaf->m_pRightChild != NULL)
insert(cKey, leaf->m_pRightChild);
else
{
leaf->m_pRightChild = new CTreeNode;
strcpy(leaf->m_pRightChild->m_strKeyString, cKey);
leaf->m_pRightChild->m_pLeftChild = NULL;
leaf->m_pRightChild->m_pRightChild = NULL;
}
}
};
  
void inorderPrint (CTreeNode *leaf)
{
if (leaf != NULL)
{
inorderPrint(leaf->m_pLeftChild);
cout << leaf->m_strKeyString << endl;
inorderPrint(leaf->m_pRightChild);
}
};
  
CTreeNode *root;
};

int main ()
{
char* pstrIntput [] = {"move", "look", "new", "apple", "printer,", "program", "special", "eagle", "cheese", "zoo", "climb", "class"};
int nInputCount = 12;
  
BSTree tree;
  
for (int i = 0; i<nInputCount;i++) {
tree.insert(pstrIntput[i]);}
tree.inorderPrint();

return 0;
}
  

Problem2

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.