Using C++ Create a class (BinaryTree) template that will create a binary tree th

Question

Using C++

Create a class (BinaryTree) template that will create a binary tree that can hold values of any data type. The class should provide functions to insert a node, a function to delete a node, functions to display the tree In Order, Pre Order and Post Order. It should also provide a member function to search the tree for a value. The class should provide a function that counts the number of nodes in the tree, a function to count the number leaf nodes in the tree, and a function that determines the height of the tree. The height of a tree is the number of levels the tree has. Write a program that shows all these functions work.

Explanation / Answer

#ifndef STUDENTINFO_H

#define STUDENTINFO_H

#include <string>

#include <iostream>

using namespace std;

// class has two data members Student ID and name of the STUDENT.

class StudentInfo

{

private:

int studID; // student ID number

string studName; // student name

public:

StudentInfo();

StudentInfo(int, string);

void setStudID(int);

void setStudName(string);

int getStudID();

string getStudName();

bool operator < (const StudentInfo &s)

{

if (studID < s.studID)

return true;

return false;

}

bool operator == (const StudentInfo &s)

{

if (studID == s.studID)

return true;

return false;

}

};

#endif

#include "StudentInfo.h"

StudentInfo::StudentInfo()

{

studName = "";

studID = 0;  

}

StudentInfo::StudentInfo(int ID, string name)

{

studName = name;

studID = ID;

}

void StudentInfo::setStudID(int ID)

{

studID = ID;

}

void StudentInfo::setStudName(string name)

{

studName = name;

}

int StudentInfo::getStudID()

{

return studID;

}

string StudentInfo::getStudName()

{

return studName;

}

#ifndef BINARYTREE_H

#define BINARYTREE_H

#include <iostream>

using namespace std;

// template class that creates a binary tree holds the values of any data type. It has functions to insert, delete a node, display the tree In Order, Pre Order and Post Order, search for a value, count total nodes, left nodes, and a function to check height of the tree.

template <class T>

class BinaryTree

{

private:

struct TreeNode

{

T value; // The node value

TreeNode *left; // left child node pointer

TreeNode *right; // right child node pointer

};

TreeNode *root; // Pointer to root node

void insert(TreeNode *&, TreeNode *&);

void destroySubTree(TreeNode *);

void deleteNode(T, TreeNode *&);

void makeDeletion(TreeNode *&);

void displayInOrder(TreeNode *) const;

void displayPreOrder(TreeNode *) const;

void displayPostOrder(TreeNode *) const;

public:

BinaryTree()

{ root = NULL; }

~BinaryTree()

{ destroySubTree(root); }

void insertNode(T);

bool searchNode(T);

void remove(T);

void displayPreOrder() const

{ displayPreOrder(root); }

void displayInOrder() const

{ displayInOrder(root); }

void displayPostOrder() const

{ displayPostOrder(root); }

};

template <class T>

void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)

{

if (nodePtr == NULL)

nodePtr = newNode; // Insert node

else if (newNode->value < nodePtr->value)

insert(nodePtr->left, newNode); // Search left branch

else

insert(nodePtr->right, newNode);// Search right branch

}

template <class T>

void BinaryTree<T>::insertNode(T item)

{

TreeNode *newNode; // Pointer to a new node

// Create new node and store number

newNode = new TreeNode;

newNode->value = item;

newNode->left = newNode->right = NULL;

insert(root, newNode);

}

template <class T>

void BinaryTree<T>::destroySubTree(TreeNode *nodePtr)

{

if (nodePtr)

{

if (nodePtr->left)

destroySubTree(nodePtr->left);

if (nodePtr->right)

destroySubTree(nodePtr->right);

delete nodePtr;

}

}

template <class T>

bool BinaryTree<T>::searchNode(T item)

{

TreeNode *nodePtr = root;

while (nodePtr)

{

if (nodePtr->value == item)

return true;

else if (item < nodePtr->value)

nodePtr = nodePtr->left;

else

nodePtr = nodePtr->right;

}

return false;

}

#endif

#include "StudentInfo.h"

#include "BinaryTree.h"

#include <iostream>

using namespace std;

int main()

{

BinaryTree<StudentInfo> tree;

StudentInfo stud1(1531, "Hari Krishna");

StudentInfo stud2(1082, "Ajay Sharma");

StudentInfo stud3(2562, "Sesidhar Mahanto");

StudentInfo stud4(3099, "Ravi Raja");

StudentInfo stud5(1123, "Spartacus Yarragunta");

StudentInfo stud6(4553, "Avinash Konathala");

StudentInfo stud7(5655, "Prathap Gullipilli");

StudentInfo stud8(4123, "Praveen Kosaraju");   

tree.insertNode(stud1);

tree.insertNode(stud2);

tree.insertNode(stud3);

tree.insertNode(stud4);

tree.insertNode(stud5);

tree.insertNode(stud6);

tree.insertNode(stud7);

tree.insertNode(stud8);

// Searching for student

char again = 'y'; // yes

int id; // holding ID from user

cout << "Would you like to search for an student? ";

cout << "Enter Y for yes or N for No: ";

cin >> again;

if (again)

{

do

{

cout << "Enter the ID number of the student: ";

cin >> id;

// Create an StudentInfo object to store the user's

// search parameters

StudentInfo info;

info.setStudID(id);

// If search finds what the user entered display the

// corresponding student

if (tree.searchNode(info))

{

cout << info.getStudName() << endl;

}

else

cout << "ID not found!" << endl;

cout << "Would you like to search for an student? ";

cout << "Enter Y for yes or N for No: ";

cin >> again;

}while (again == tolower('Y'));

}

// Display in order

tree.displayInOrder();

cout << endl;

tree.displayPreOrder();

cout << endl;

tree.displayPostOrder();

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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