二叉搜索树模板

Question

我是 c++ 的新手，我最近收到了一个使用模板创建我自己的二进制搜索树的项目。目标是让二叉树能够接受任何类型的数据。 IntBinaryTree.h 应该可以接收EmployeeInfo对象。我已经让它编译了，但我收到一条错误消息 glibc detected double free or corruption (fasttop) 我不太确定这是什么意思。另外我不确定我是否正确设置了程序。另请注意，我正在 main.cpp 中逐一测试函数，这就是为什么只使用插入函数的原因。

Update 我通过 TreeNode *newNode = new TreeNode 为 insertNode 函数分配了内存，现在我得到错误消息 "in instantiation of void IntBinaryTree::insertNode(T) [with T = EmployeeInfo]: main.cpp:22:29 required from here "

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

Answer 1

在你的 insertNode 方法中，你没有为你的节点分配任何 space 并且你使用了一个未初始化的指针：

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 class

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

请注意，无需设置左右指针，因为构造函数现在会为您完成。

二叉搜索树模板

Binary Search Tree Template

c++

binary-search-tree