Binärbaum von Objekten für ein einzelnes Klassenmitglied durchsuchen

Question

Also arbeite ich an einem Programm, das eine binäre Baumvorlagenklasse verwendet, die ich erstellt habe, um eine Reihe von EmployeeInfo-Objekten zu halten, die eine andere Klasse ist, die ich erstellt habe. Die EmployeeInfo-Klasse verfügt über zwei Datenelemente, von denen eines die ID-Nummer des Mitarbeiters und das andere den Namen des Mitarbeiters enthält. Im Hauptprogramm erstelle ich den binären Baum von 5 Mitarbeiterinfo - Objekten und ich versuche nun herauszufinden, wie man den Binärbaum nach JUST einer Angestellten - ID - Nummer durchsuchen kann und wenn die Nummer da ist, muss ich die Nummer zusammen mit der Name der Nummer auf dem Bildschirm zugeordnet. Dies ist, wo ich in Schwierigkeiten gerate. Meine Suchfunktion gibt einen bool zurück, so dass ich nicht sicher bin, wie ich den Namen der ID-Nummer anzeigen kann, wenn sie gefunden wird.

Hier ist meine Binary Tree Template-Klasse:

// Specification file for the BinaryTree Class 
#ifndef BINARYTREE_H 
#define BINARYTREE_H 
#include <iostream> 
using namespace std; 

// BinaryTree template 
template <class T> 
class BinaryTree 
{ 
private: 
    struct TreeNode 
    { 
     T value; 
     TreeNode *left; 
     TreeNode *right; 
    }; 

    TreeNode *root; 

    // Private functions 
    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; 
    int findHeight(TreeNode *root); 
    int count1(TreeNode *); 
    int countLeft(TreeNode *); 

public: 
    // Constructor 
    BinaryTree() 
    { 
     root = nullptr; 
    } 

    // Destructor 
    ~BinaryTree() 
    { 
     destroySubTree(root); 
    } 

    // Binary Tree Operations 
    void insertNode(T); 
    bool searchNode(T); 
    void remove(T); 
    int displayCount() 
    { 
     return count1(root); 
    } 
    int displayLeftCount() 
    { 
     return countLeft(root); 
    } 
    int displayHeight() 
    { 
     return findHeight(root); 
    } 


    void displayInOrder() const 
    { 
     displayInOrder(root); 
    } 

    void displayPreOrder() const 
    { 
     displayPreOrder(root); 
    } 

    void displayPostOrder() const 
    { 
     displayPreOrder(root); 
    } 

}; 

template <class T> 
void BinaryTree<T>::insert(TreeNode *&root, TreeNode *&newNode) 
{ 
    if (root == nullptr) 
     root = newNode; 
    else if (newNode->value < root->value) 
     insert(root->left, newNode); 
    else 
     insert(root->right, newNode); 
} 

template <class T> 
void BinaryTree<T>::insertNode(T item) 
{ 
    TreeNode *newNode = nullptr; 

    newNode = new TreeNode; 
    newNode->value = item; 
    newNode->left = newNode->right = nullptr; 

    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; 
} 

template <class T> 
void BinaryTree<T>::remove(T item) 
{ 
    deleteNode(item, root); 
} 

template <class T> 
void BinaryTree<T>::deleteNode(T item, TreeNode *&nodePtr) 
{ 
    if (item < nodePtr->value) 
     deleteNode(item, nodePtr->left); 
    else if (item > nodePtr->value) 
     deleteNode(item, nodePtr->right); 
    else 
     makeDeleteion(nodePtr); 
} 

template <class T> 
void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr) 
{ 
    TreeNode *tempNodePtr = nullptr; 

    if (nodePtr == nullptr) 
     cout << "Cannot delete empty node." << endl; 
    else if (nodePtr->right == nullptr) 
    { 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->left; 
     delete tempNodePtr; 
    } 
    else if (nodePtr->left == nullptr) 
    { 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->right; 
     delete tempNodePtr; 
    } 
    else 
    { 
     tempNodePtr = nodePtr->right; 
     while (tempNodePtr->left) 
      tempNodePtr = tempNodePtr->left; 
     tempNodePtr->left = nodePtr->left; 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->right; 
     delete tempNodePtr; 
    } 
} 

template <class T> 
void BinaryTree<T>::displayInOrder(TreeNode *nodePtr) const 
{ 
    if (nodePtr) 
    { 
     displayInOrder(nodePtr->left); 
     cout << nodePtr->value << endl; 
     displayInOrder(nodePtr->right); 
    } 
} 

template <class T> 
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const 
{ 
    if (nodePtr) 
    { 
     cout << nodePtr->value << endl; 
     displayPreOrder(nodePtr->left); 
     displayPreOrder(nodePtr->right); 
    } 
} 

template <class T> 
void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const 
{ 
    if (nodePtr) 
    { 
     displayPostOrder(nodePtr->left); 
     displayPostOrder(nodePtr->right); 
     cout << nodePtr->value << endl; 
    } 
} 

template <class T> 
int BinaryTree<T>::count1(TreeNode *root) 
{ 
    int count = 1; 
    if (root->left != nullptr) 
    { 
     count += count1(root->left); 
    } 
    if (root->right != nullptr) 
    { 
     count += count1(root->right); 
    } 
    return count; 
} 

template <class T> 
int BinaryTree<T>::countLeft(TreeNode *root) 
{ 
    int count = 1; 
    if (root->left != nullptr) 
     count += countLeft(root->left); 
    return count; 
} 

template <class T> 
int BinaryTree<T>::findHeight(TreeNode *nodePtr) 
{ 
    if (nodePtr == NULL) 
    { 
     return 0; 
    } 

    int left = findHeight(nodePtr->left); 
    int right = findHeight(nodePtr->right); 

    if (left > right) 
     return 1 + left; 
    else 
     return 1 + right; 

} 

#endif 

Hier meine EmployeeInfo Klasse-Header und cav:

/* Specification file for the EmployeeInfo class which will hold two private data members, one which is an integer called empID and another which will 
be a string called empName.*/ 
#include "BinaryTree.h" 
#include <iostream> 
#include <string> 
#ifndef EMPLOYEEINFO_H 
#define EMPLOYEEINFO_H 

class EmployeeInfo 
{ 
private: 
    int empID; 
    string empName; 
public: 
    // Default Constructor 
    EmployeeInfo(); 

    // Constructor 
    EmployeeInfo(int, string); 

    // Mutator functions 
    void setEmpID(int); 
    void setEmpName(string); 

    // Accessor functions 
    int getEmpID() const; 
    string getEmpName() const; 

    // Overloaded operators 
    bool operator < (const EmployeeInfo &right); 
    bool operator > (const EmployeeInfo &right); 
    bool operator == (const EmployeeInfo &right); 
}; 
#endif 

// Declaration file for the EmployeeInfo class 
#include "BinaryTree.h" 
#include "EmployeeInfo.h" 
#include <iostream> 
#include <string> 

// Default Constructor 
EmployeeInfo::EmployeeInfo() 
{ 
    empID = 0; 
    empName = ""; 
} 

// Constructor 
EmployeeInfo::EmployeeInfo(int i, string n) 
{ 
    empID = i; 
    empName = n; 
} 

// Mutators 
void EmployeeInfo::setEmpID(int i) 
{ 
    empID = i; 
} 

void EmployeeInfo::setEmpName(string n) 
{ 
    empName = n; 
} 

// Accessors 
int EmployeeInfo::getEmpID() const 
{ 
    return empID; 
} 

string EmployeeInfo::getEmpName() const 
{ 
    return empName; 
} 

// Overloaded operators 
bool EmployeeInfo::operator > (const EmployeeInfo &right) 
{ 
    bool status; 

    if (empID > right.empID) 
     status = true; 
    else 
     status = false; 

    return status; 
} 

bool EmployeeInfo::operator < (const EmployeeInfo &right) 
{ 
    bool status; 

    if (empID < right.empID) 
     status = true; 
    else 
     status = false; 

    return status; 
} 

bool EmployeeInfo::operator == (const EmployeeInfo &right) 
{ 
    bool status; 

    if (empID == right.empID) 
     status = true; 
    else 
     status = false; 

    return status; 
} 

Und hier ist das Hauptprogramm:

#include "BinaryTree.h" 
#include "EmployeeInfo.h" 
#include <iostream> 
#include <string> 
using namespace std; 

const int NUM_EMPS = 5; 

int main() 
{ 
    BinaryTree<EmployeeInfo> staff; 
    int ID; 
    string name; 

    // Fill up the tree 
    for (int count = 0; count < NUM_EMPS; count++) 
    { 
     cout << "Enter the ID number for Employee " << count + 1 << ": "; 
     cin >> ID; 
     cout << "Name: "; 
     cin >> name; 
     EmployeeInfo newEmp(ID, name); 
     staff.insertNode(newEmp); 
    } 

    // NEED HELP WITH THIS PART!!! 
    do 
    { 
     int search; 
     cout << "Enter the ID number you'd like to search for: "; 
     cin >> search; 


    system("pause"); 
    return 0; 
} 

Ich bin in der Lage, den Baum mit den Objekten zu füllen, aber wenn es darum geht, den Baum zu suchen, bin ich verloren! Jede Hilfe wird geschätzt.

Answer 1

Zeigen Sie die Informationen mit der binären Baumklasse an.

Bearbeiten Sie Ihre searchNode Funktion im Binary Tree Klasse

template <class T> 
bool BinaryTree<T>::searchNode(T item) { 
    TreeNode *nodePtr = root; 

    while (nodePtr) { 
     if (nodePtr->value == item) { 
      cout << nodePtr->value << endl; 
      return true; 
     } 
     else if (item < nodePtr->value) 
      nodePtr = nodePtr->left; 
     else 
      nodePtr = nodePtr->right; 
     } 
    return false; 
} 

Dann ein EmployeeInfo-Objekt erstellen, weisen Sie die ID, zu suchen und zu Ihrem Baum suchen:

int search; 
cout << "Enter the ID number you'd like to search for: "; 
cin >> search; 

EmployeeInfo tempEmp; 
tempEmp.setEmpID(search); 

if (!staff.searchNode(tempEmp)) 
     cout << "Employee ID not found.\n"; 

// else if staff.searchNode(tempEmp) == true, employee info will 
// be displayed from Binary Tree searchNode method