c++ - 二叉搜索树未处理的异常

<分区>

我不知道是什么原因造成的。你们能帮帮我吗？自上次人们提示以来，因为我应该只发布 MCVE 而不是所有源代码。我只会发布(我认为)与该问题相关的内容。它基本上是一个二叉搜索树，未处理的异常与 BST 类的 add 方法有关。

节点.h

#ifndef NODE_H
#define NODE_H

#include "Button.h"

class Node
{
private:

    int key;
    Node* left;
    Node* right;
    Button nextPlay;
    bool used;

public:

    Node();
    Node(int k, int x, int y);

    void setLeft(Node* n);
    Node* getLeft();
    void setRight(Node* n);
    Node* getRight();
    Button getPlay();
    int getKey();
    void setUsed();
    bool getUsed();

};

#endif

节点.cpp

#include "Node.h"

Node::Node()
{
    key = 0;
    left = NULL;
    right = NULL;
    //nextPlay = NULL;
    used = false;
}

Node::Node(int k, int x, int y)
{
    key = k;
    left = NULL;
    right = NULL;
    nextPlay.getPosition()->x = x;
    nextPlay.getPosition()->y = y;
    used = false;
}

void Node::setLeft(Node* n)
{
    left = n;
}

Node* Node::getLeft()
{
    return left;
}

void Node::setRight(Node* n)
{
    right = n;
}

Node* Node::getRight()
{
    return right;
}

Button Node::getPlay()
{
    return nextPlay;
}

int Node::getKey()
{
    return key;
}

void Node::setUsed()
{
    used = true;
}

bool Node::getUsed()
{
    return used;
}

BST.h

#ifndef BST_H
#define BST_H

#include "Node.h"

class BST
{
private:

    Node* root;

    bool add(Node* n, int k, int x, int y);
    int remAll(Node* n);
    Button get(Node* n);

public:

    BST();
    ~BST();

    bool add(int k, int x, int y);
    int remAll();
    Button get();

};

#endif

BST.cpp

#include "BST.h"

BST::BST()
{
    root = NULL;
}

BST::~BST()
{
    remAll();
}

bool BST::add(Node* n, int k, int x, int y)
{
    bool success;
    if (n = NULL)
    {
        n = new Node(k, x, y);
        success = true;
    }
    else
    {
        if (k == n->getKey())
        {
            success = false;
        }
        else
        {
            if (k < n->getKey())
            {
                Node* leftTree = n->getLeft();
                success = add(leftTree, k, x, y);
                n->setLeft(leftTree);
            }
            else
            {
                Node* rightTree = n->getRight();
                success = add(rightTree, k, x, y);
                n->setRight(rightTree);
            }
        }
    }
    return success;
}

int BST::remAll(Node* n)
{
    int number;
    if (n == NULL)
    {
        number = 0;
    }
    else
    {
        number = remAll(n->getLeft());
        number += remAll(n->getRight());
        delete n;
        number++;
    }
    return number;
}

Button BST::get(Node* n)
{
    if (n != NULL)
    {
        if (!n->getUsed())
        {
            n->setUsed();
            return n->getPlay();
        }
        else
        {
            Node* rightTree = n->getRight();
            if (rightTree != NULL)
            {
                return get(rightTree);
            }
            else
            {
                Node* leftTree = n->getLeft();
                if (leftTree != NULL)
                {
                    return get(leftTree);
                }
            }
        }
    }
}

bool BST::add(int k, int x, int y)
{
    return add(root, k, x, y);
}

int BST::remAll()
{
    int number = remAll(root);
    root = NULL;
    return number;
}

Button BST::get()
{
    return get(root);
}

当我运行程序时，未处理的异常指向:

int Node::getKey()
{
    return key;
}

在BST的add方法中使用。

最佳答案

如果您向空 BST 添加注释，则执行将是:

bool BST::add(int k, int x, int y)
{
    return add(root, k, x, y);
}

由于 root 为 NULL，因此在 add(root, k, x, y) 中将发生以下情况:

   bool success;
   if (n = NULL) {      // <=== OUCH !!! you set n to NULL if if wasn't 
       ...              // this is ignored because the condition is always NULL
   }
   else {               // so the else part is executed       
       if (k == n->getKey()) {  //  <======OUCH !!! remember n is NULL

所以在这个阶段，由于这两个错误(请参阅上面的 OUCH 评论)，您取消引用空指针 n。这会导致您的段错误。

备注:从技术上讲，由于 getKey() 不是虚拟的，该函数实际上可能会在 this 为 NULL 的情况下被调用，因此段错误将仅在访问 key 时触发。但这取决于实现。

如何解决？

首先纠正节点为NULL的情况:

if (n == NULL)   // == instead of =

但这还不够。您的递归算法期望以下语句修改树中的指针。不幸的是，实际上它只修改了一个局部指针变量，并让树保持原样:

    n = new Node(k, x, y);   // store the newly created node, but... n is local

您的方法只有在 n 是对树中原始指针的引用时才有效。您可以通过更改函数的签名来实现此目的:

bool BST::add(Node*& n, int k, int x, int y)  // pass n by reference

关于c++ - 二叉搜索树未处理的异常，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30551132/

上一篇：c++ - 如果我删除类(class)，shared_ptr 会被删除吗

下一篇：c++ - 委托(delegate)给另一个对象的运算符(operator)->

相关文章：

c++ - 已删除的构造函数/运算符的可访问性是否重要？

c++ - 如何在使用 Windows API 下载文件时创建进度条？

c++ - 合并八叉树中的叶子

java - 二叉树的 hasPathSum() 实现

c++ - Cmake 在使用目标 target_include_directories 时无法指定包含目录

c++ - 何时使用引用与指针

c++ - 在 OpenGL 中的 3D 模型上创建 AABB

c++ - 模板化的 Pointer 类可以有一个虚拟析构函数吗？

c++ - 为什么我可以在初始化后重新绑定(bind)引用？

java - Level Order tree 遍历通用树，逐层显示树