二進制搜索樹模板

我對C++相當陌生，最近我收到了一個使用模板創建自己的二進制搜索樹的項目。目標是讓Binary Tree能夠接受任何類型的數據類型。 IntBinaryTree.h應該能夠接受EmployeeInfo的對象。我已經得到它編譯，但我得到一個錯誤消息glibc檢測到雙免費或腐敗（fasttop）我不完全確定這是什麼意思。此外，我不確定是否已正確設置程序。另外請注意，我正在main.cpp中測試函數1，這就是爲什麼只有插入函數被使用。二進制搜索樹模板

更新我分配的內存由樹節點* newNode的insertNode功能=新的TreeNode，現在我得到的錯誤消息「空隙IntBinaryTree的實例:: insertNode（T）與T = EmployeeInfo]：主的.cpp：22：29從這裏開始「

#ifndef EMPLOYEEINFO_H 
#define EMPLOYEEINFO_H 

#include<iostream> 
#include<string> 
#include<cstdlib> 

using namespace std; 

class EmployeeInfo 
{ 
public: 
    EmployeeInfo(int, string); 
    ~EmployeeInfo(); 
    //void print(); 
    int getEmployeeID(); 
    string getEmployeeName(); 
    void setEmployeeID(int); 
    void setEmployeeName(string); 
    bool operator ==(const EmployeeInfo &eO1) {return EmployeeID == eO1.EmployeeID;} 
    bool operator >(const EmployeeInfo &eO1) {return EmployeeID > eO1.EmployeeID;} 
    bool operator <(const EmployeeInfo &eO1) {return EmployeeID < eO1.EmployeeID;} 

private:  
    int EmployeeID; 
    string EmployeeName; 
}; 

#endif 


#include"EmployeeInfo.h" 
#include<iostream> 
#include<string> 
#include<cstdlib> 

using namespace std; 

EmployeeInfo::EmployeeInfo(int empID, string name) 
{ 
    EmployeeID = empID; 
    EmployeeName = name; 
} 

EmployeeInfo::~EmployeeInfo() 
{ 
} 

int EmployeeInfo::getEmployeeID() 
{ 
    return EmployeeID; 
} 

string EmployeeInfo::getEmployeeName() 
{ 
    return EmployeeName; 
} 

void EmployeeInfo::setEmployeeID(int empID) 
{ 
    EmployeeID = empID; 
} 

void EmployeeInfo::setEmployeeName(string name) 
{ 
    EmployeeName = name; 
} 


#ifndef INTBINARYTREE_H 
#define INTBINARYTREE_H 

#include <iostream> 
#include<string> 
#include<cstdlib> 
#include <iomanip> 

using namespace std; 

template<class T> 
struct TreeNode 
{ 
    T value; 
    TreeNode<T> *left; 
    TreeNode<T> *right; 
}; 

template<class T> 
class IntBinaryTree 
{ 
    private: 
     TreeNode<T>* root; 
     void insert(TreeNode<T> *&, TreeNode<T> *&); 
     void destroySubTree(TreeNode<T> *); 
     void deleteNode(T, TreeNode<T> *&); 
     void makeDeletion(TreeNode<T> *&); 
     void displayInOrder(TreeNode<T> *) const; 
     void displayPreOrder(TreeNode<T> *) const; 
     void displayPostOrder(TreeNode<T> *) const; 
    public: 
     //Constructor 
     IntBinaryTree(); 
    ~IntBinaryTree(){destroySubTree(root);} 

     //Binary Tree Operations 
     void insertNode(T); 
     bool searchNode(T); 
     void remove(T); 

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

}; 

template<class T> 
IntBinaryTree<T>::IntBinaryTree() 
{ 
    root = NULL; 
} 

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

template<class T> 
void IntBinaryTree<T>::insertNode(T val) 
{ 
    TreeNode<T> *newNode; 

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

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

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

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

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

template<class T> 
void IntBinaryTree<T>::destroySubTree(TreeNode<T> *nodePtr){ 
    if(nodePtr != NULL) 
    { 
     if(nodePtr->left != NULL) 
     { 
      destroySubTree(nodePtr->left); 
     } 
     if(nodePtr->right != NULL) 
     { 
      destroySubTree(nodePtr->right); 
     } 
     delete nodePtr; 
    } 

    cout << "Binary Tree Destroyed\n"; 
} 

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

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

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

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

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

    if (nodePtr == NULL) 
     cout << "Cannot delete empty node\n"; 
    else if(nodePtr->right == NULL) 
    { 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->left; 
     delete tempNodePtr; 
    } 
    else if(nodePtr->left == NULL) 
    { 
     tempNodePtr = nodePtr; 
     nodePtr = nodePtr->right; 
     delete tempNodePtr; 
    } 
    //If the node has two Children 
    else 
    { 
     //Move one node to the right 
     tempNodePtr = nodePtr->right; 
     //Go to the end left node 
     while(tempNodePtr->left) 
      tempNodePtr = tempNodePtr->left; 
     //Reattach the left subtree 
     tempNodePtr->left = nodePtr->left; 
     tempNodePtr = nodePtr; 
     //Reattach the right subtree 
     nodePtr = nodePtr->right; 
     delete tempNodePtr; 
    } 
} 

#endif 



#include"EmployeeInfo.cpp" 
#include"IntBinaryTree.h" 
#include<iostream> 
#include<string> 
#include<cstdlib> 

using namespace std; 

int main() 
{  
    IntBinaryTree<EmployeeInfo> mytree; 

    EmployeeInfo employee1(1021, "John Williams"); 
    EmployeeInfo employee2(1057, "Bill Witherspoon"); 
    EmployeeInfo employee3(2487, "Jennifer Twain"); 
    EmployeeInfo employee4(3769, "Sophia Lancaster"); 
    EmployeeInfo employee5(1017, "Debbie Reece"); 
    EmployeeInfo employee6(1275, "George McMullen"); 
    EmployeeInfo employee7(1899, "Ashley Smith"); 
    EmployeeInfo employee8(4218, "Josh Plemmons"); 

    mytree.insertNode(employee1); 
    mytree.insertNode(employee2); 
    mytree.insertNode(employee3); 
    mytree.insertNode(employee4); 
    mytree.insertNode(employee5); 
    mytree.insertNode(employee6); 
    mytree.insertNode(employee7); 
    mytree.insertNode(employee8); 

    return 0; 
}

來源

2015-05-03 Stupore

需要在你insertNode方法，你不分配爲您節點的任何空間，並使用未初始化的指針：

TreeNode<T> *newNode; 

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

您需要分配一些內存爲您的節點：

TreeNode<T> *newNode = new TreeNode<T>;

我強烈建議學習使用調試器，這樣你就可以通過線通過您的代碼行跟蹤，看看它在做什麼。沒有人每次都寫完美的代碼，而調試器是查看錯誤的最簡單方法。

編輯：以上將無法正常工作，因爲您沒有Employee的默認構造函數，但您只有TreeNode的默認構造函數。這意味着您無法創建包含Employee的TreeNode。

解決這個問題的最好辦法，就是增加一個構造函數來TreeNode接受一個參數是一個T對象的引用，以便它可以從參數初始化自己的value對象。

添加到您的TreeNode類

TreeNode(T &val) : value(val), left(NULL), right(NULL) { }

這段代碼複製val參數爲value並初始化left和right指針。

然後將您的insert代碼更改爲。

TreeNode<T> *newNode = new TreeNode <T> (val) ; 
//Insert the Node 
insert(root, newNode);

請注意，不需要設置左指針和右指針，因爲構造函數現在可以爲您設置。

來源

2015-05-04 00:21:45

好的，謝謝你的提示！但是現在我得到這個錯誤信息：「在實例化void IntBinaryTree :: insertNode（T）[with T = EmployeeInfo] main.cpp：22：29這裏需要解釋這是什麼意思，以及如何解決這個問題？ 'm不知道我是否在main中正確調用insertNode函數.. – Stupore

這不是真正的錯誤，只是出現錯誤。我會嘗試編譯我的機器上的代碼以查看實際錯誤並編輯我的回答 –

再次感謝您的幫助！我真的想了解正在發生的事情以及我做錯了什麼。 – Stupore

二進制搜索樹模板

回答

相關問題