C++ EXERCISE (DATA STRUCTURES). I just need a code for some functions that are missing. Please...
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 <iostream>
#include <cstdlib>
#include <iomanip>
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): \n";
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\n\n";
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 << "\n\nWould 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 ---------------\n\n";
cout << "*\tDisplay the tree\n"
<< "\t\t1. Preorder traversal\n"
<< "\t\t2. Inorder traversal\n"
<< "\t\t3. Postorder traversal\n\n";
cout << "**\tDisplay\n"
<< "\t\t4. Only leaves\n"
<< "\t\t5. Only parents with one child\n"
<< "\t\t6. Only parents with two children\n\n";
cout << "***\tDisplay\n"
<< "\t\t7. Tree sideways\n\n";
cout << "****\tCount the number of nodes\n"
<< "\t\t8. All nodes in the tree\n"
<< "\t\t10. Exit.\n\n";
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)
// ===========================================================================
Homework Answers
#include <iostream>
#include <cstdlib>
#include <iomanip>
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
void postorder(const ptrType tree); // Add this function
void displayLeaves(const ptrType tree);
void displayParentsWithOne(const ptrType tree);
void displayParentsWithTwo(const ptrType tree);
void displayTreeSideways(const ptrType tree, int numSpaces);
void countAllNodes(const ptrType tree, int &totalNodes);
void countAllLeaves(const ptrType tree, int &totalLeaves) ; // 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): \n";
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: ";
postorder(tree);
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: ";
displayParentsWithTwo(tree);
break;
case 7 : system("cls"); cout << "BST displayed sideways\n\n";
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: "<<totalLeaves;
// 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 << "\n\nWould 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 ---------------\n\n";
cout << "*\tDisplay the tree\n"
<< "\t\t1. Preorder traversal\n"
<< "\t\t2. Inorder traversal\n"
<< "\t\t3. Postorder traversal\n\n";
cout << "**\tDisplay\n"
<< "\t\t4. Only leaves\n"
<< "\t\t5. Only parents with one child\n"
<< "\t\t6. Only parents with two children\n\n";
cout << "***\tDisplay\n"
<< "\t\t7. Tree sideways\n\n";
cout << "****\tCount the number of nodes\n"
<< "\t\t8. Total nodes in the tree\n"
<< "\t\t9. Total Leaves in the tree\n"
<< "\t\t10. Exit.\n\n";
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);
}
}
void postorder(const ptrType tree)
{
if (tree != NULL)
{
postorder(tree->left);
postorder(tree->right);
cout << tree->info << " ";
}
}
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 =======================================
void displayParentsWithTwo(const ptrType tree)
{
if (tree != NULL)
{
displayParentsWithTwo(tree->left);
if (((tree->left != NULL) && (tree->right != NULL)) )
{
cout << tree->info << " ";
}
displayParentsWithTwo(tree->right);
}
}
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.
void countAllLeaves(const ptrType tree,int &totalLeaves)
{
if (tree != NULL)
{
countAllLeaves(tree->left,totalLeaves);
if ((tree->left == NULL) && (tree->right == NULL))
{
totalLeaves++;
}
countAllLeaves(tree->right,totalLeaves);
}
}
// 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.
// ===========================================================================
If you need any modification please let me know..
Thank you..
Add Answer to:
C++ EXERCISE (DATA STRUCTURES). I just need a code for some
functions that are missing. Please...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function. #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: //Overload the assignment operator. const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&) { if (this != &otherTree) //avoid self-copy...
Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition: class TreeNode<T>...
Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition: class TreeNode<T> T data TreeNode<T> left TreeNode<T> right Since this TreeNode is a generic Template, use any data file we've used this quarter to store the data in the BinaryTree. To do this will likely require writing a compare function or operator. Hint: Think LEFT if the index is calculate (2n+1) and RIGHT if index is (2n+2). Source code: #include<iostream> using namespace std;...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
C++ Help with Test #1 (at bottom) to work properly. May adjust code to work or...
C++ Help with Test #1 (at bottom) to work properly. May adjust code to work or add any additional code. Do not use global variables. #include <iostream> #include <string> using std::endl; using std::cout; using std::cin; using std::string; void pressAnyKeyToContinue() { printf("Press any key to continue\n"); cin.get(); } //This helps with testing, do not modify. bool checkTest(string testName, int whatItShouldBe, int whatItIs) { if (whatItShouldBe == whatItIs) { cout << "Passed " << testName << endl; return true; } else...
Hi there, I am working on a binary search tree code in c++. The program must...
Hi there, I am working on a binary search tree code in c++. The program must store and update students' academic records, each node includes the student name, credits attempted, credits earned and GPA. I have made some progress with the code and written most of the functions in the .cpp file (already did the .h file) but i am struggling with what to put in the main and how to put an update part in the insert function. I...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the word...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
Name the program for this assignment "bst_driver.cpp." In this assignment you will make several modifications to...
Name the program for this assignment "bst_driver.cpp." In this assignment you will make several modifications to the BST class in the file “bst.cpp” that I provided. Consider the following: 1. Change the declaration of treenode to class treenode //node in a BST { public: string county_name; double population_size; treenode *lchild, *rchild; //left and right children pointers }; 2. Make the following changes to the BST class: a) change the name from “BST” to “bst”; b) change default constructor from “BST”...
using java to write,show me the output. please write some common. You CAN NOT use inbuild...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
I need to make it so this program outputs to an output.txt, the program works fine,...
I need to make it so this program outputs to an output.txt, the program works fine, just need it to fprintf to output.txt #include <stdio.h> #include <string.h> #include <malloc.h> #define MAX 30 struct treeNode { char names[MAX]; struct treeNode *right; struct treeNode *left; }*node; void searchName(char names[], struct treeNode ** parent, struct treeNode ** location) { struct treeNode * ptr, * tempPtr; if(node == NULL) { *location = NULL; *parent = NULL; return; } if(strcmp(names, node->names) == 0)...
Q. write the algorithm for each function in this code: void insert(int x, node*&p) { //cheak...
Q. write the algorithm for each function in this code: void insert(int x, node*&p) { //cheak if the pointer is pointing to null. if (p==NULL) { p = new node; p->key=x; p->left=NULL; p->right=NULL; } else { //Cheak if the element to be inserted is smaller than the root. if (x < p->key) { //call the function itself with new parameters. insert(x,p->left); } //cheak if the alement to be inserted...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
Most questions answered within 3 hours.
-
Suppose the method of tree ring dating gave the following dates
A.D. for an archaeological excavation...
asked 20 minutes ago -
Network security
1. explain succinctly how a Denial of Service attack may occur
on an implementation...
asked 10 minutes ago -
Name two of the basic guidelines for business dress that women
should follow in cultures other...
asked 11 minutes ago -
How can organizations create value by implementing an advanced
information system solution paired with the appropriate...
asked 13 minutes ago -
You are designing a wastewater treatment system using a
constructed wetland. The inputs will be high...
asked 15 minutes ago -
A 43kg teen grabs onto a rope swing. The length of rope between
the teen and...
asked 23 minutes ago -
In a certain oscillating LC circuit, the total energy
is converted from electrical energy in the...
asked 26 minutes ago -
JAVA - OOP inheritance help please
I have a question,
I have 4 classes.
College, course,...
asked 26 minutes ago -
what is the distinction between the purpose of healthcare
management and the purpose od healthcare financial...
asked 40 minutes ago -
When disposable income is $1000, consumer spending is $950. The
value of the multiplier for this...
asked 49 minutes ago -
Calculate the pH of a buffer solution that is
0.116 M in
C2H5NH2
(ethylamine) and 0.403...
asked 49 minutes ago -
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>&
nums) {
int...
asked 1 hour ago