BinaryTree搜索功能

Question

程序應該要求用戶輸入他或她想要搜索的員工的ID號。如果發現該ID號的僱員被顯示。我只能使用顯示功能顯示身份證號碼和員工，但我無法弄清楚如何使搜索功能起作用並顯示員工。

二叉樹

#ifndef BINARYTREE_H 
#define BINARYTREE_H 
#include <iostream> 
using namespace std; 

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

template <class T> 
class BinaryTree 
{ 
private: 
    struct TreeNode 
    { 
     T value;   // The value in the node 
     TreeNode *left;  // Pointer to left child node 
     TreeNode *right; // Pointer to right child node 
    }; 

    TreeNode *root;   // Pointer to the root node 

    // Private member 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; 

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

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

    // Binary tree operations 
    void insertNode(T); 
    bool searchNode(int); 
    void remove(T); 

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

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

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

}; 

//********************************************************* 
// insert function accepts a TreeNode pointer and a  * 
// pointer to a node. The function inserts the node into * 
// the tree pointer to by the TreeNode pointer. This  * 
// function is call recursively.       * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode) 
{ 
    if (nodePtr == NULL) 
     nodePtr = newNode;    // Insert the node 
    else if (newNode->value < nodePtr->value) 
     insert(nodePtr->left, newNode); // Search the left branch 
    else 
     insert(nodePtr->right, newNode);// Search the right branch 
} 

//********************************************************* 
// insertNode creates a new node to hold item as its value* 
// and passes it to the insert function.     * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::insertNode(T item) 
{ 
    TreeNode *newNode;  // Pointer to a new node 

    // Create anew node and store num in it 
    newNode = new TreeNode; 
    newNode->value = item; 
    newNode->left = newNode->right = NULL; 

    // Insert the node 
    insert(root, newNode); 
} 

//********************************************************** 
// destroySubTree is called by the destructor. It deletes * 
// all nodes in the tree.         * 
//********************************************************** 
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; 
    } 
} 

//********************************************************** 
// searchNode determines if a value is present in the tree.* 
// If so, the function returns true. Otherwise it returns * 
// false. 
//********************************************************** 
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; 
} 

//********************************************************* 
// remove calls deleteNode to delete the node whode value * 
// member is the same as num        * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::remove(T item) 
{ 
    deleteNode(item, root); 
} 

//********************************************************* 
// deleteNode deletes the node whose value member is the * 
// same as num           * 
//********************************************************* 
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 
     makeDeletion(nodePtr); 
} 

//********************************************************* 
// makeDeletion takes a reference to apointer to the node * 
// that is to be deleted. The node is removed and the  * 
// branches of the tree below the node are reattached  * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr) 
{ 
    // Define a temporary pointer to use in reattaching 
    // the left subtree 
    TreeNode *tempNodePtr; 

    if (nodePtr == NULL) 
     cout << "Cannot delete empty node.\n"; 
    else if (nodePtr->right == NULL) 
    { 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->left; // Reattach the left child 
     delete tempNodePtr; 
    } 
    else if (nodePtr->left == NULL) 
    { 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->right; // Reattach the right child 
     delete tempNodePtr; 
    } 

} 
//********************************************************* 
// The displayInOrder function displays the values in the * 
// subtree pointed to by nodePtr, via inorder traversal * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::displayInOrder(TreeNode *nodePtr) const 
{ 
    if (nodePtr) 
    { 
     displayInOrder(nodePtr->left); 
     cout << nodePtr->value.getEmpID() << " " 
      << nodePtr->value.getEmpName() << endl; 
     displayInOrder(nodePtr->right); 
    } 
} 
//********************************************************* 
// The displayPreOrder function displays the values in the* 
// subtree pointed to by nodePtr, via Preorder traversal * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const 
{ 
    if (nodePtr) 
    { 
     cout << nodePtr->value.getEmpID() << " " 
      << nodePtr->value.getEmpName() << endl; 
     displayInOrder(nodePtr->left); 
     displayInOrder(nodePtr->right); 
    } 
} 
//********************************************************* 
// displayPostOrder function displays the values in the * 
// subtree pointed to by nodePtr, via Postorder traversal * 
//********************************************************* 
template <class T> 
void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const 
{ 
    if (nodePtr) 
    { 
     displayInOrder(nodePtr->left); 
     displayInOrder(nodePtr->right); 
     cout << nodePtr->value.getEmpID() << " " 
      << nodePtr->value.getEmpName() << endl; 
    } 
} 
#endif 

EMPLOYEEINFO

#ifndef EMPLOYEEINFO_H 
#define EMPLOYEEINFO_H 
#include <string> 
#include <iostream> 
using namespace std; 

// This class has two data members to hold the employee ID 
// and the name of the employee. 

class EmployeeInfo 
{ 
private: 
    int empID;  // To hold employee ID number 
    string empName; // To hold employee name 

public: 
    // Default Constructor 
    EmployeeInfo(); 

    // Constructor 
    EmployeeInfo(int, string); 

    // Mutators 
    void setEmpID(int); 
    void setEmpName(string); 

    // Accessors 
    int getEmpID(); 
    string getEmpName(); 

    // Overloaded operator. This works directly with 
    // the insert function of BinaryTree.h more specifically 
    // line 71. *For my knowledge* 
    bool operator < (const EmployeeInfo &e) 
    { 
     if (empID < e.empID) 
      return true; 
     return false; 
    } 

    // Overloaded operator for the search function 
    bool operator == (const EmployeeInfo &e) 
    { 
     if (empID == e.empID) 
      return true; 
     return false; 
    } 

}; 
#endif 

#include "EmployeeInfo.h" 

//********************************************************* 
// Default constructor intializes the data members  * 
//********************************************************* 
EmployeeInfo::EmployeeInfo() 
{ 
    empName = ""; 
    empID = 0; 
} 

//********************************************************* 
// Constructor sets the data members      * 
//********************************************************* 
EmployeeInfo::EmployeeInfo(int ID, string name) 
{ 
    empName = name; 
    empID = ID; 
} 

//********************************************************* 
// setEmpID stores the employee ID number     * 
//********************************************************* 
void EmployeeInfo::setEmpID(int ID) 
{ 
    empID = ID; 
} 

//********************************************************* 
// setEmpName stores the full name of the employee  * 
//********************************************************* 
void EmployeeInfo::setEmpName(string name) 
{ 
    empName = name; 
} 

//********************************************************* 
// getEmpID returns the employee ID number    * 
//********************************************************* 
int EmployeeInfo::getEmpID() 
{ 
    return empID; 
} 

//********************************************************* 
// getEmpName returns the full name of the employee  * 
//********************************************************* 
string EmployeeInfo::getEmpName() 
{ 
    return empName; 
} 

主要

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

int main() 
{ 

    // Create an instance of BinaryTree 
    BinaryTree<EmployeeInfo> tree; 

    // Create an EmployeeInfo object 
    EmployeeInfo emp1(1021, "John Williams"); 
    EmployeeInfo emp2(1057, "Bill Witherspoon"); 
    EmployeeInfo emp3(2487, "Jennifer Twain"); 
    EmployeeInfo emp4(3769, "Sophia Lancaster"); 
    EmployeeInfo emp5(1017, "Debbie Reece"); 
    EmployeeInfo emp6(1275, "George McMullen"); 
    EmployeeInfo emp7(1899, "Ashley Smith"); 
    EmployeeInfo emp8(4218, "Josh Plemmons");  

    tree.insertNode(emp1); 
    tree.insertNode(emp2); 
    tree.insertNode(emp3); 
    tree.insertNode(emp4); 
    tree.insertNode(emp5); 
    tree.insertNode(emp6); 
    tree.insertNode(emp7); 
    tree.insertNode(emp8); 

    // Search for an employee 
    char again = 'y';  // To hold yes 
    int id;     // To hold ID number from user 

    cout << "Would you like to search for an employee?\n"; 
    cout << "Enter Y for yes or N for No: "; 
    cin >> again; 
    if (again) 
    { 
     do 
     { 
      cout << "Enter the ID number of the employee: "; 
      cin >> id; 
      // Create an EmployeeInfo object to store the user's 
      // search parameters 
      EmployeeInfo info; 
      info.setEmpID(id); 

      // If search finds what the user entered display the 
      // corresponding employee 
      if (tree.searchNode(info)) 
      { 
       cout << info.getEmpName() << endl; // Not right? 
      } 
      else 
       cout << "ID not found!" << endl; 

      cout << "Would you like to search for an employee?\n"; 
      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(); 
} 

好吧，我改變了代碼，使其獲得布爾上班，if (tree.searchNode(info))，但我不認爲cout聲明是正確的。有人可以看看我的searchNode函數，以及我如何調用它，讓我知道我在做什麼錯了？

Answer 1

問題就在這裏

info.setEmpID(1021); 
    info.setEmpID(1057); 
    info.setEmpID(2487); 
    info.setEmpID(3769); 
    info.setEmpID(1017); 
    info.setEmpID(1275); 
    info.setEmpID(1899); 
    info.setEmpID(4218); 

    info.setEmpName("John Williams"); 
    info.setEmpName("Bill Witherspoon"); 
    info.setEmpName("Jennifer Twain"); 
    info.setEmpName("Sophia Lancaster"); 
    info.setEmpName("Debbie Reece"); 
    info.setEmpName("George McMullen"); 
    info.setEmpName("Ashley Smith"); 
    info.setEmpName("Josh Plemmons"); 

您不添加任何東西的信息，但每次通話時間setEmpName()要更新info對象。

可以使在searchNode方法一些變化如下

template <class T> 

布爾二叉樹:: searchNode（T &項） { 樹節點* NODEPTR =根;

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

}

在main()方法

do 
     { 
      cout << "Enter the ID number of the employee: "; 
      cin >> id; 
      BinaryTree<EmployeeInfo> temp; 
      if ((temp=tree.searchNode(id))!=NULL) 
      { 
       cout << temp.getEmpName() << endl; 
      } 
      else{ 
       cout<<"ID not found"<<endl; 
      } 
      cout << "Would you like to search for an employee?\n"; 
      cout << "Enter Y for yes or N for No: "; 
      cin >> again; 
     }while (again == tolower('Y')); 

//新變化......在searchNode(T)聲明 製造變化searchNode(T &) ...在你的新代碼僱員的姓名發現沒有設置在info這就是爲什麼當你試圖打印EmpName沒有輸出......所以這個變化是通過EmployeeInfo的參考searchitem(T &)

模板 布爾二叉樹:: searchNode（T &項） { 樹節點* NODEPTR =根;

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

}