C++ EXERCISE (DATA STRUCTURES). I just need a code for some functions that are missing. Please help me figure out. Thanks.

C++ BST implementation (using a struct)

Enter the code below, and then compile and run the program.

After the program runs successfully, add the following functions:

postorder()

This function is similar to the inorder() and preorder() functions, but demonstrates postorder tree traversal.

displayParentsWithTwo()

This function is similar to the displayParents WithOne() function, but displays nodes having only two children.

countAllLeaves()

This function is similar to the countAllNodes() function, but counts leaves (nodes with no children).

#include

#include

#include

using namespace std;

struct TreeNode

{

int info;

TreeNode *left, *right;

};

typedef TreeNode* ptrType;

void insert(ptrType &tree, int item);

void showMenu(int & choice);

void preorder(const ptrType tree); // Demonstrates Preorder traversal

void inorder(const ptrType tree); // Demonstrates Inorder traversal

// 1.) postorder() // Add this function

void displayLeaves(const ptrType tree);

void displayParentsWithOne(const ptrType tree);

// 2.) displayParentsWithTwo() // Add this function

void displayTreeSideways(const ptrType tree, int numSpaces);

void countAllNodes(const ptrType tree, int &totalNodes);

// 3.) countAllLeaves() // Add this function

int main(

{

char answer;

int item;

int numSpaces = 0; // To format output to display BST sideways

char response;

int choice;

ptrType tree = NULL;

do {

system("cls");

int totalNodes = 0; // Used to count all nodes

int totalLeaves = 0; // Used to count all leaves

// loop to allow user to repeatedly enter data into the list

cout << "Enter positive integers into a BST (-1 to stop): ";

do {

cin >> item;

if (item == -1)

break;

// Call function to insert the node into the BST

else

insert(tree, item);

} while (item != -1);

do{

system("cls");

// Call function to display a menu of choices.

// One int argument passed & returned by reference.

showMenu(choice);

switch (choice)

{

case 1 : system("cls"); cout << "Preorder traversal: ";

preorder(tree);

break;

case 2 : system("cls"); cout << "Inorder traversal: ";

inorder(tree);

break;

case 3 : system("cls"); cout << "Postorder traversal: ";

// ADD the postorder() function call

break;

case 4 : system("cls"); cout << "Leaves only: ";

displayLeaves(tree);

break;

case 5 : system("cls"); cout << "Only parents w/ 1 child:";

displayParentsWithOne(tree);

break;

case 6 : system("cls"); cout << "Only parents with two"

<< "children: ";

// Add the displayParentsWithTwo() function call

break;

case 7 : system("cls"); cout << "BST displayed sideways ";

displayTreeSideways(tree, numSpaces);

break;

case 8 : system("cls"); countAllNodes(tree, totalNodes);

cout << "The total number of nodes

<< " in the BST: " << totalNodes;

break;

case 9 : system("cls"); countAllLeaves(tree, totalLeaves);

cout << "The total number of leaves";

<< " in the BST: ";

// Add the totalLeaves() function call

break;

case 10 : exit (1); // To exit the program

} // end switch

cout << endl << endl;

cout << "Would you like to make another selection (y/n)? ";

cin >> response;

} while (toupper(response) == 'Y');

// allows user to re-enter loop and make another selection.

cout << " Would you like to enter some new numbers (y/n)?";

cin >> answer;

} while (toupper(answer) == 'Y');

return 0;

} // end main()

// ============================================================================

// ============================================================================

void insert(ptrType &tree, int item)

{

if (tree == NULL)

{

tree = new(TreeNode);

tree -> info = item;

tree -> left = NULL;

tree -> right = NULL;

}

else if (item < tree-> info)

insert(tree->left, item);

else if (item > tree-> info)

insert(tree->right, item);

}

// ============================================================================

void showMenu(int & choice)

{

cout << "--------------- Menu --------------- ";

cout << "*\tDisplay the tree "

<< "\t\t1. Preorder traversal "

<< "\t\t2. Inorder traversal "

<< "\t\t3. Postorder traversal ";

cout << "**\tDisplay "

<< "\t\t4. Only leaves "

<< "\t\t5. Only parents with one child "

<< "\t\t6. Only parents with two children ";

cout << "***\tDisplay "

<< "\t\t7. Tree sideways ";

cout << "****\tCount the number of nodes "

<< "\t\t8. All nodes in the tree "

<< "\t\t10. Exit. ";

cout << "\t\tPlease enter your choice: ";

cin >> choice;

cout << endl << endl;

}

// ============================================================================

// ==== preorder function =====================================================

void preorder(const ptrType tree)

{

if (tree != NULL)

{

cout << tree->info << " ";

Preorder(tree->left);

Preorder(tree->right);

}

}

// ============================================================================

void inorder(const ptrType tree)

{

if (tree != NULL)

{

inorder(tree->left);

cout << tree->info << " ";

inorder(tree->right);

}

}

// ============================================================================

// ==== postorder function ====================================================

// This function displays all nodes in the tree using Postorder traversal.

// Input: Parameter1 - Address of the root node is passed.

// Output: The entire list of nodes is output to the screen.

// ============================================================================

// postorder()

// (Write this function)

// ===========================================================================

void displayLeaves(const ptrType tree)

{

if (tree != NULL)

{

displayLeaves(tree->left);

if ((tree->left == NULL) && (tree->right == NULL))

{

cout << tree->info << " ";

}

displayLeaves(tree->right);

}

}

// ===========================================================================

// ============================================================================

void displayParentsWithOne(const ptrType tree)

{

if (tree != NULL)

{

displayParentsWithOne(tree->left);

if (((tree->left == NULL) || (tree->right == NULL)) &&

!((tree->left == NULL) && (tree->right == NULL)))

{

cout << tree->info << " ";

}

displayParentsWithOne(tree->right);

}

}

// ============================================================================

// ==== displayParentsWithTwo function =======================================

// This function displays only those nodes that have two children.

// Input: Parameter1 - Address of the root node is passed.

// Output: Only parents with two children are displayed on the screen..

//

// ============================================================================

// displayParentsWithTwo()

// (Write this function)

// ==========================================================================

void displayTreeSideways(const ptrType tree, int numSpaces)

{

if (tree != NULL)

{

displayTreeSideways(tree->right, numSpaces + 6);

cout << setw(numSpaces) << tree->info << endl << endl;

displayTreeSideways(tree->left, numSpaces + 6);

}

}

// ============================================================================

// ==== countAllNodes function =========================================

// This function counts all nodes in the BST.

// Input: Parameter1 - Address of the root node is passed.

// Parameter2 - totalNodes is of integer type, and represents the total

// number of Nodes.

// Output: The value of totalNodes is changed in memory.

//

// ===========================================================================

void countAllNodes(const ptrType tree, int &totalNodes)

{

if (tree != NULL)

{

totalNodes++;

countAllNodes(tree->left, totalNodes);

countAllNodes(tree->right, totalNodes);

}

}

// ===========================================================================

// ==== countAllLeaves function =========================================

// This function counts all Leaves in the BST.

// Input:

// Parameter1 - Address of the root node is passed.

// Parameter2 - totalLeaves is of integer type, is passed by reference,

// and represents the total number of Leaves.

// Output:

// The value of totalLeaves is changed in memory.

// ===========================================================================

// countAllLeaves()

// (Write this function)

// ===========================================================================