时间戳

首页 > 解决方案 > 二叉搜索树的 c++ 实现中的 EXC_BAD_ACCESS 错误

c++ - 二叉搜索树的 c++ 实现中的 EXC_BAD_ACCESS 错误

问题描述

我目前正在学习 c++，为了学习它，我会实现一个简单的二叉搜索树类，以便掌握 c++ 中的概念。在实现添加函数时，我收到一个有趣的错误，其中似乎程序无法将节点识别为空，然后立即崩溃，因为节点应该为空。

//Here is my add/insert function I created.
void BinarySearchTree::insert(double x){
    if(root == NULL){
        root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
        root->val = x;
        return;
    }
    bool inserted = false;
    struct TreeNode* curr = root;
    while(curr != NULL && !inserted){
        if(curr->val == x){
            return;
        }
        if(x > curr->val){
            if(curr->right == NULL){
                curr->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
                curr->right->val = x;
                inserted = true;
            } else {
                curr = curr->right;
            }
        } else {
            if(curr->left == NULL){
                curr->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
                curr->left->val = x;
                inserted = true;
            } else {
                curr = curr->left;
            }
        }
    }
}


//This is the TreeNode struct and the BinarSearchTree class in my header file if it helps
struct TreeNode{
    double val;
    struct TreeNode *right;
    struct TreeNode *left;
};

class BinarySearchTree{
private:
    struct TreeNode *root;
public:
    void insert(double x);
};

标签： c++xcodeclassstructbinary-search-tree

解决方案

太棒了，您正在学习 C++！

不要害怕：你只需要涉水更深一点，一切都会好起来的。评论一致认为还有很多东西需要学习，但相信我们：这将是非常值得的努力。

正如一些评论所指出的，这个例子中的主要问题是你没有正确初始化你在决策过程中使用的变量，这意味着它们包含垃圾——任何旧值——而不是你的零打算他们。初始化在 C 语言中同样重要。C++ 只会更多地握住您的手，确保您这样做——如果您允许的话。

实际上，稍后您可能会研究标准库提供的专用指针类型，但起初您可能希望只专注于学习C++的处理方式。您可以使用好的 'olmalloc进行分配，但是当您这样做时，您实际上只是在为自己做不必要的工作，同时将您的代码暴露给您遇到的那种问题。C++ 为您提供，它将为operator new您完成所有繁重的工作，尤其是与适当的功能结合使用时。constructor

简单的 C++ 语句：

new TreeNode;

......做的比看起来更多。首先，它分配对象所需的内存——大多数实现都malloc在后台使用。然后它调用constructor您为该类定义的函数，以初始化结构中的数据。

所以首先，TreeNode你需要一些类似的东西：

struct TreeNode {
   double val;
   TreeNode *right;
   TreeNode *left;

   // default constructor --'ctor'
   TreeNode():right(null), left(null) {}

   // useful ctor for your particular situation
   TreeNode( double val ):TreeNode(), val(val) {}
};

然后，在您的::insert职能范围内：

// replace these lines...
if(root == NULL){
   root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
   root->val = x;
   return;
} 

// with something like these...
if( !root ) {
   root = new TreeNode;   // root->val is garbage, for now
   return;
}

// and replace the two branch creation sections...
if(curr->right == NULL){
   curr->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
   curr->right->val = x;
   inserted = true;
}

// ... with something like this
if( !curr->right ) {
   curr->right = new TreeNode( x );
   break;   // you are only setting 'inserted' here to end your loop
}

构造函数——以及作为它们补充的析构函数——是强大的工具，你可以发现它们的许多细微差别。

然后，您可以深入了解精简和优化代码的细节。

推荐阅读