Hi, I need help completing my program. Try to turn a binary tree into a data ret
ID: 3912862 • Letter: H
Question
Hi,
I need help completing my program.
Try to turn a binary tree into a data retrieval program using the concept of an associative container.
Step 1: First, define a new class for storing data about some kind of entity (people, books, music albums, etc.). Make sure that one of the fields in the class is suitable for uniquely identifying an individual object of the class. For people, you could use the last name, social security number, student ID, or something like that. For books, you could use the ISBN, subject, course number (for textbooks), author. etc.
Step 2: Modify the TreeNode class so that it has four fields: a string for the key, a pointer to an object as defined above, and pointers to the left and right subtrees.
Step 3: Modify the BinaryTree class so that it properly uses the new TreeNode.
Step 4: Write a search function that accepts the value of a key as a parameter, and then returns the object associated with that key. The function should return null if the key was not found.
Step 5: Write a main function that creates a tree, fills it with data, and then allows the user to input a key and then search the tree for that key. Demonstrate that it correctly finds the data requested, and returns null for data that is not present.
Here is my code.
#include "BinaryTree.h"
#include <iostream>
void BinaryTree::add(Student *s)
{
root = add(s, root);
}
TreeNode* BinaryTree::add(Student *s, TreeNode* p)
{
if (p == 0)
{
p = new TreeNode(s);
}
else
{
if (s->id < p->key)
p->left = add(s, p->left);
else
p->right = add(s, p->right);
}
return p;
}
bool BinaryTree::contains(std::string key)
{
return contains(key, root);
}
bool BinaryTree::contains(std::string key, TreeNode* p)
{
if (p == 0)
return false;
else if (p->key == key)
return true;
else if (key < p->key)
return contains(key, p->left);
else
return contains(key, p->right);
}
void BinaryTree::displayPreOrder()
{
displayPreOrder(root);
}
void BinaryTree::displayInOrder()
{
displayInOrder(root);
}
void BinaryTree::displayPostOrder()
{
displayPostOrder(root);
}
void BinaryTree::displayPostOrder(TreeNode *p)
{
if (p != 0)
{
displayPostOrder(p->left);
displayPostOrder(p->right);
p->student->display();
}
}
void BinaryTree::displayPreOrder(TreeNode *p)
{
if (p != 0)
{
p->student->display();
displayPreOrder(p->left);
displayPreOrder(p->right);
}
}
void BinaryTree::displayInOrder(TreeNode *p)
{
if (p != 0)
{
displayInOrder(p->left);
p->student->display();
displayInOrder(p->right);
}
}
Student* BinaryTree::search(std::string key)
{
return 0;
}
#pragma once
#include "TreeNode.h"
class BinaryTree
{
private:
TreeNode* root = 0;
TreeNode* add(Student *s, TreeNode* p);
bool contains(std::string key, TreeNode* p);
void displayPostOrder(TreeNode* p);
void displayPreOrder(TreeNode* p);
void displayInOrder(TreeNode* p);
public:
BinaryTree() { root = 0; }
void add(Student *s);
void displayPreOrder();
void displayInOrder();
void displayPostOrder();
bool contains(std::string key);
bool isEmpty() { return root == 0; }
Student *search(std::string key);
};
#include <iostream>
#include "BinaryTree.h"
using namespace std;
void main()
{
BinaryTree tree;
int choice = 0;
const int QUIT = 6;
string id, fName, lName;
Student *s = 0;
tree.add(new Student("jonesd342", "Dan", "Jones"));
tree.add(new Student("rocushp", "Peter", "Rocush"));
tree.add(new Student("mendezd175", "Dora", "Mendez"));
tree.add(new Student("habbenr", "Ryan", "Habben"));
tree.add(new Student("aliy183", "Jason", "Ali"));
do
{
cout << endl << "MENU:" << endl;
cout << "1. Is tree empty?" << endl;
cout << "2. Add student." << endl;
cout << "3. Is student present?" << endl;
cout << "4. Retrieve student data." << endl;
cout << "5. Display all students." << endl;
cout << "6. End program." << endl << endl;
cin >> choice;
switch (choice)
{
case 1:
if (tree.isEmpty())
cout << "Tree is empty." << endl;
else
cout << "Tree contains data." << endl;
break;
case 2:
cout << "Student ID: ";
cin >> id;
cout << "First Name: ";
cin >> fName;
cout << "Last Name: ";
cin >> lName;
tree.add(new Student(id, fName, lName));
break;
case 3:
cout << "Enter ID of student: ";
cin >> id;
if (tree.contains(id))
cout << "Yes, student " << id << " is present." << endl;
else
cout << "No, student " << id << " is absent." << endl;
break;
case 4:
cout << "Enter ID of student: ";
cin >> id;
s = tree.search(id);
if (s == 0)
cout << "Student " << id << " was not found." << endl;
else
s->display();
break;
case 5:
cout << endl << "Preorder Display:" << endl;
tree.displayPreOrder();
cout << endl << "Inorder Display:" << endl;
tree.displayInOrder();
cout << endl << "Postorder Display:" << endl;
tree.displayPostOrder();
break;
case 6:
cout << "Ending program..." << endl;
break;
default:
cout << "ERROR: Invalid option. Try again." << endl;
}
} while (choice != QUIT);
system("pause");
}
#pragma once
#include <iostream>
#include <string>
class Student
{
public:
std::string id;
std::string firstName;
std::string lastName;
Student(std::string i, std::string f, std::string l)
{
id = i;
firstName = f;
lastName = l;
}
void display()
{
std::cout << firstName << " " << lastName << " (" << id << ")";
std::cout << std::endl;
}
};
#pragma once
#include <string>
#include "Student.h"
class TreeNode
{
public:
std::string key;
Student *student;
TreeNode* left;
TreeNode* right;
TreeNode(Student *s)
{
key = s->id;
student = s;
left = right = 0;
}
};
Explanation / Answer
Modified files are given below.... Please do rate if it helped. Thank you
BinaryTree.h
-------
#pragma once
#include "TreeNode.h"
class BinaryTree
{
private:
TreeNode* root = 0;
TreeNode* add(Student *s, TreeNode* p);
Student* search(std::string key, TreeNode* p);
void displayPostOrder(TreeNode* p);
void displayPreOrder(TreeNode* p);
void displayInOrder(TreeNode* p);
public:
BinaryTree() { root = 0; }
void add(Student *s);
void displayPreOrder();
void displayInOrder();
void displayPostOrder();
bool contains(std::string key);
bool isEmpty() { return root == 0; }
Student *search(std::string key);
};
BinaryTree.cpp
------------
#include "BinaryTree.h"
#include <iostream>
void BinaryTree::add(Student *s)
{
root = add(s, root);
}
TreeNode* BinaryTree::add(Student *s, TreeNode* p)
{
if (p == 0)
{
p = new TreeNode(s);
}
else
{
if (s->id < p->key)
p->left = add(s, p->left);
else
p->right = add(s, p->right);
}
return p;
}
bool BinaryTree::contains(std::string key)
{
return search(key) != 0;
}
void BinaryTree::displayPreOrder()
{
displayPreOrder(root);
}
void BinaryTree::displayInOrder()
{
displayInOrder(root);
}
void BinaryTree::displayPostOrder()
{
displayPostOrder(root);
}
void BinaryTree::displayPostOrder(TreeNode *p)
{
if (p != 0)
{
displayPostOrder(p->left);
displayPostOrder(p->right);
p->student->display();
}
}
void BinaryTree::displayPreOrder(TreeNode *p)
{
if (p != 0)
{
p->student->display();
displayPreOrder(p->left);
displayPreOrder(p->right);
}
}
void BinaryTree::displayInOrder(TreeNode *p)
{
if (p != 0)
{
displayInOrder(p->left);
p->student->display();
displayInOrder(p->right);
}
}
Student* BinaryTree::search(std::string key)
{
return search(key, root);
}
Student* BinaryTree::search(std::string key, TreeNode* p)
{
if(p == 0)
return 0;
else if(key == p->key)
return p->student;
else if(key < p->key)
return search(key, p->left);
else
return search(key, p->right);
}
output
-----
MENU:
1. Is tree empty?
2. Add student.
3. Is student present?
4. Retrieve student data.
5. Display all students.
6. End program.
1
Tree contains data.
MENU:
1. Is tree empty?
2. Add student.
3. Is student present?
4. Retrieve student data.
5. Display all students.
6. End program.
5
Preorder Display:
Dan Jones (jonesd342)
Ryan Habben (habbenr)
Jason Ali (aliy183)
Peter Rocush (rocushp)
Dora Mendez (mendezd175)
Inorder Display:
Jason Ali (aliy183)
Ryan Habben (habbenr)
Dan Jones (jonesd342)
Dora Mendez (mendezd175)
Peter Rocush (rocushp)
Postorder Display:
Jason Ali (aliy183)
Ryan Habben (habbenr)
Dora Mendez (mendezd175)
Peter Rocush (rocushp)
Dan Jones (jonesd342)
MENU:
1. Is tree empty?
2. Add student.
3. Is student present?
4. Retrieve student data.
5. Display all students.
6. End program.
3
Enter ID of student: habbenr
Yes, student habbenr is present.
MENU:
1. Is tree empty?
2. Add student.
3. Is student present?
4. Retrieve student data.
5. Display all students.
6. End program.
3
Enter ID of student: abc
No, student abc is absent.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.