二叉搜索树未处理的异常

Question

我不知道是什么原因造成的。你们能帮帮我吗？自上次人们抱怨以来，我应该只 post 一个 MCVE 而不是所有的源代码。我只是 post 什么（我认为）与问题有关。它基本上是一个二叉搜索树，未处理的异常与 BST 的 add 方法有关 class.

Node.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

Node.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方法

Answer 1

如果你在一个空的 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

Answer 2

问题似乎出在创建节点时。您在 add 方法中按值而不是按引用传递指针。函数签名应为 bool BST::add(Node*& n, int k, int x, int y)。还要将 n = NULL 更改为 n == NULL 以进行比较而不是赋值。

希望对您有所帮助！

Answer 3

一种经常被推荐的避免此类错误的方法

if (n = NULL) {

就是尝试换个风格去做

if (NULL == n) {

这应该会导致编译器给您一个错误。 L.H.S 操作数不再是左值并且对于 '=' 是非法的，但对于 '==' 则不是，以防止您不小心这样做。我在职业生涯的早期就犯过几次这个错误，然后永久地转换了。

二叉搜索树未处理的异常

Unhandled Exception with Binary Search Tree

c++

tree

visual-c++

如何解决？