二叉树 class 创建随机节点，中断

Question

所以我将模板化的二叉树字典实现为继承自抽象字典 class 的 class，我的添加函数有一个问题，我无法弄清楚.

基本上，我的树的节点具有键和值，以及指向其父节点、左子节点和右子节点的指针。节点的代码是

struct bNode {
    K key;
    V value;
    bNode* left;
    bNode* right;
    bNode* parent;
};

（我知道使用 shared_ptr 比原始指针更好，但这个项目不需要它）该树还有一个成员指针bNode* root.

为了测试我的树，我向其中添加元素并在每个元素之后调用显示。到目前为止，显示一个空列表可以正常工作，显示一个包含一个元素和两个元素的列表也是如此。但是，当我添加第三个并调用显示时，它中断了...

这是添加函数的代码

void add(K key, V value) override {
    // if list is empty, create new root node
    if (!root){
        root = new bNode;
        root->key = key;
        root->value = value;
        return;
    }
    bNode* node = root;
    // travel down tree, checking each node on the way
    while (true){
        // if node exists with passed-in key, change value to passed-in value
        if (node->key == key){
            node->value = value;
            return;
        }
        // if key < or > node and node has a left / right child, travel left / right branch
        // if node doesn't have a left / right child, create one and pass in key
        if (key < node->key){
            if (node->left){
                node = node->left;
            } else {
                node->left = new bNode;
                node->left->parent = node;
                node->left->key = key;
                node->left->value = value;
                return;
            }
        } else {
            if (node->right){
                node = node->right;
            } else {
                node->right = new bNode;
                node->right->parent = node;
                node->right->key = key;
                node->right->value = value;
                return;
            }
        }
    }
}

此处显示

void display() const override {
    if (!root){
        return;
    }
    displayHelper(root);
    cout << endl;
}

这里是 displayHelper

void displayHelper(bNode* node) const {
    cout << "(" << node->key << ", " << node->value << ") ";
    if (node->left){
        cout << "displaying left... <" << node->key << "> ";
        displayHelper(node->left);
    }
    if (node->right){
        cout << "displaying right... <" << node->key << "> ";
        displayHelper(node->right);
    }
}

cout "displaying right" 和 "displaying left" 的行是我试图修复错误，因为它不应该运行除非该函数即将显示另一个节点。在显示前 2 个节点后，这一切都按预期工作；然而，在第三个节点，它会显示那个元素，然后打印 "displaying left <*3rd node's key>..."，然后崩溃并给我一个分段错误。

据我所知，这意味着由于某种原因，代码运行ning 好像第三个添加的节点（应该是叶节点）实际上有子节点，但是当它崩溃时尝试读取不存在节点的成员变量。

我不知道是什么导致了这个错误，因为这都是非常简单的代码！任何帮助将不胜感激！

编辑：这是演示该问题的示例代码片段；

BSTDictionary<string, int> t;
t.display();
t.add("e", 5);
t.display();
t.add("b", 20);
t.display();
t.add("c", 12);
t.display();
return 0;

当运行时，输出看起来像

(e,5)

(e,5) 显示左侧... (e) (b,20)

(e,5) 显示左侧... (e) (b,20) 显示右侧... (b) (c,12) 显示左侧... (c)

进程返回 -1073741819 (0xC0000005) 执行时间：1.993 秒

应该没有包含 (c,12) 的节点的左子节点，但编译器试图运行就好像有。

Answer 1

您需要确保将对象中的所有叶节点指针初始化为 nullptr，除非您立即将它们分配给有意义的东西。

二叉树 class 创建随机节点，中断

Binary tree class creating random node, breaking

c++

debugging

tree

binary-tree

dictionary