为什么我的二叉树覆盖了它根的叶子？

Question

我已将我的问题确定为这个特定函数，它是我的二叉树的辅助函数。在这个函数调用之前有一个节点，但它似乎只是替换了那个节点而不是增长它。当我在脑海中查看我的代码时，一切都有意义，但我无法弄清楚我做错了什么。

这里是调用add的函数：

void BSTree::Insert(Client &newClient) {
    if (isEmpty())
    {
        Node *newNode = new Node(newClient);
        this->root = newNode;
    }
    else
        add(this->root, newClient);
}

这是我的 add() 函数：

BSTree::Node* BSTree::add(Node *node, Client &newClient) // helper function for Insert()
{
    if (node == nullptr)
        {
            Node *newNode = new Node(newClient);
            //node = newNode; // already tried adding this in
            return newNode;
        }
    if (newClient.clientID < node->pClient->clientID)
        return node->left = add(node->left, newClient); // already tried just returning add()
    else
        return node->right = add(node->right, newClient);
}

Answer 1

由于这是你的问题，我将解释你的代码在做什么。想象一下，您已经有了一个成熟的二叉树，并且您正在向树中添加一个节点。当你到达这条线时

return node->left = add(node->left, newClient);

执行了三个单独的指令：

newClient通过add()添加到node的左分支。
节点的左子节点设置为 add() 的 return 值。
赋值的右侧 (RHS) return 由父函数编辑。

问题出在数字 2 上。如果您要添加的树已经成熟，则在遍历树时更改节点的左子节点将导致您观察到的覆盖效果。事实上，问题不仅仅是覆盖树叶。由于您使用了 new 关键字，被覆盖的节点仍然分配了堆 space，永远不会被删除并导致内存泄漏。

这里有一些想法可以帮助您走上正确的方向：

您的 insert() 函数确保您第一次调用 add() 时，不会将 nullptr 作为第一个参数传递。利用这一点，并通过在执行递归调用之前检查 nullptr 来确保 nullptr 永远不会传递到 add() 函数。将 add() 的 return 类型更改为 void。您不再需要检查节点是否为 nullptr。这里有一些伪代码可以指导你

void add(node, val)
    if val < node.val
        if node.left exists
            add(node.left, val)
        else
            make a new object and set node.left to that object
    else
        if node.right exists
            add(node.right, val)
        else
            make a new object and set node.right to that object

Answer 2

你的逻辑有问题。首先，有一个 insert() 方法，你应该这样写以便更好地理解：

void BSTree::Insert(const Client &newClient) // use const to prevent modification
{
    if (isEmpty()) { root = new Node(newClient); }
    else { add(this->root, newClient); }
}

这样您就可以在 BSTree 中的 'root' 指针的帮助下直接在根目录下创建一个新对象。

现在，关于 add() 方法。您作为参数传递的 'node' 是指针变量的副本，因此实际指针值不会更改。看到这个：

BSTree::Node* BSTree::add(Node *node, Client &newClient) //logical error

您需要像这样使用 'Node* &node':

通过引用传递节点*

BSTree::Node* BSTree::add(Node* &node, const Client &newClient)

为什么二叉树会覆盖其叶子的根？答案： 您使用 return 语句的递归调用是完全错误的。

return node->left = add(node->left, newClient);

add(node->left, newClient) 总是 return 叶子的地址，而您正在 returning 这个值。它进行递归调用，直到到达叶子位置。

结论：既然BUG多，建议大家慎重重写逻辑。我希望这有帮助！ :-)

为什么我的二叉树覆盖了它根的叶子？

Why Is My Binary Tree Overwriting The Leaves Of Its Root?

c++

recursion

binary-tree

insert