树结构 - 不正确 children

Question

我正在尝试用 C++ 构建简单的结构。应该类似于AVL树。

当我在 main() 函数中构建一个具有三个节点的简单树时，一切正常。

问题出在我尝试使用 insert() 函数时。此函数的第一个参数包含将第二个参数的值放在何处的信息。

代码如下：

#include <numeric>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node {
    Node* left;
    Node* right;
    Node* parent;
    int value;
    int count_leafs;
    int height;
};

Node* root;


void insert2(int p, int value, Node* node, int left) 
{
    //printf("insert %d %d - (%d, %d) %d \n", p, value, node->left, node->right, left);

    if (root == NULL) {
        //  creating a tree root

        Node new_node;
        new_node.left = NULL;
        new_node.right = NULL;
        new_node.parent = NULL;

        root = &new_node;

        root->value = value;
        root->count_leafs = 1;
        root->height = 1;
        return;
    }

    if (node->left == NULL && node->right == NULL) {
        //  joining value to the leaf

        Node new_parent;
        new_parent.count_leafs = 2;
        new_parent.height = 2;
        new_parent.value = node->value + value;
        new_parent.parent = node->parent;
        new_parent.left = NULL;
        new_parent.right = NULL;

        Node new_leaf;
        new_leaf.value = value;
        new_leaf.count_leafs = 1;
        new_leaf.left = NULL;
        new_leaf.right = NULL;
        new_leaf.height = 1;
        new_leaf.parent = &new_parent;

        new_parent.left = &new_leaf;
        new_parent.right = node;


        if (node->parent != NULL && node->parent->left != NULL && node->parent->left == node) {
            printf("a");
            node->parent->left = &new_parent;
        }

        if (node->parent != NULL && node->parent->right != NULL && node->parent->right == node) {
            printf("b");
            node->parent->right = &new_parent;  
        }

        node->parent = &new_parent;

        return;
    }

    //printf("GOTO: %d %d \n", left + node->left->count_leafs, p);

    node->value += value;
    node->count_leafs += 1;

    if (left + node->left->count_leafs + 1 >= p) {
        //printf("W left\n");
        insert2(p, value, node->left, left);
    } else {    
        //printf("W right\n");
        insert2(p, value, node->right, left + node->left->count_leafs);
    }
}


void insert(int p, int value) 
{
    insert2(p, value, root, 0);
}

int main() 
{
    Node new_root;
    root = NULL;

    new_root.value = 10;
    new_root.height = 2;
    new_root.count_leafs = 2;
    new_root.parent = NULL;
    root = &new_root;

    Node left;
    left.value = 6;
    left.height = 1;
    left.count_leafs = 1;
    left.parent = root;
    left.left = NULL;
    left.right = NULL;

    Node right;
    right.value = 4;
    right.height = 1;
    right.count_leafs = 1;
    right.parent = root;
    right.left = NULL;
    right.right = NULL;

    root->left = &left;
    root->right = &right;

    // PLACE A

    insert(0, 1);

    // PLACE B

    return 0;
}

正如您之前看到的，PLACE A 正在构建一个具有 3 个节点的树。 PLACE A 看起来像这样：

  10
 /  \
6    4

接下来，我想在 PLACE A 和 PLACE B 之间的一行中添加一个新节点。之后（在 PLACE B）树应该是这样的：

但我得到这样的结果：

            11
           /  \
  1972250912   4
     / \
    2   2

我不知道哪里出了问题。应该是insert2()函数的问题，我没找到

你看到了吗？在此先感谢您的帮助！

Answer 1

造成这种行为的原因是您在作用域外使用了作用域变量。您不得使用指向该作用域外的作用域变量的指针。范围变量仅存在于声明它们的范围内。如果决定访问范围外的范围变量，您将访问一些堆栈，其中一些其他数据会覆盖该变量，从而导致未定义的行为。

我的意思是，你不能这样做：

if (root == NULL) 
{
    Node new_node;
    root = &new_node;
    return;
}

你可以使用operator new在堆中创建一个新的struct Node实例，稍后使用。

if (root == NULL) 
{
    root = new Node;
    return;
}

但是您稍后必须删除此节点。或者您可以使用智能指针，请参阅 this.

阅读 this and this 了解更多信息。

下面的代码完全符合您的预期。但是它不会删除会导致内存泄漏的已创建节点，因此必须改进此代码，但这是一个单独的问题。

#include <numeric>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node {
    Node* left;
    Node* right;
    Node* parent;
    int value;
    int count_leafs;
    int height;
};

Node* root;


void insert2(int p, int value, Node* node, int left)
{
    //printf("insert %d %d - (%d, %d) %d \n", p, value, node->left, node->right, left);

    if (root == NULL) {
        //  creating a tree root

        Node* new_node = new Node;
        new_node->left = NULL;
        new_node->right = NULL;
        new_node->parent = NULL;

        root = new_node;

        root->value = value;
        root->count_leafs = 1;
        root->height = 1;
        return;
    }

    if (node->left == NULL && node->right == NULL) {
        //  joining value to the leaf

        Node* new_parent = new Node;
        new_parent->count_leafs = 2;
        new_parent->height = 2;
        new_parent->value = node->value + value;
        new_parent->parent = node->parent;
        new_parent->left = NULL;
        new_parent->right = NULL;

        Node* new_leaf = new Node;
        new_leaf->value = value;
        new_leaf->count_leafs = 1;
        new_leaf->left = NULL;
        new_leaf->right = NULL;
        new_leaf->height = 1;
        new_leaf->parent = new_parent;

        new_parent->left = new_leaf;
        new_parent->right = node;


        if (node->parent != NULL && node->parent->left != NULL && node->parent->left == node) {
            printf("a");
            node->parent->left = new_parent;
        }

        if (node->parent != NULL && node->parent->right != NULL && node->parent->right == node) {
            printf("b");
            node->parent->right = new_parent;
        }

        node->parent = new_parent;

        return;
    }

    //printf("GOTO: %d %d \n", left + node->left->count_leafs, p);

    node->value += value;
    node->count_leafs += 1;

    if (left + node->left->count_leafs + 1 >= p) {
        //printf("W left\n");
        insert2(p, value, node->left, left);
    }
    else {
        //printf("W right\n");
        insert2(p, value, node->right, left + node->left->count_leafs);
    }
}


void insert(int p, int value)
{
    insert2(p, value, root, 0);
}

int main()
{
    Node new_root;
    root = NULL;

    new_root.value = 10;
    new_root.height = 2;
    new_root.count_leafs = 2;
    new_root.parent = NULL;
    root = &new_root;

    Node left;
    left.value = 6;
    left.height = 1;
    left.count_leafs = 1;
    left.parent = root;
    left.left = NULL;
    left.right = NULL;

    Node right;
    right.value = 4;
    right.height = 1;
    right.count_leafs = 1;
    right.parent = root;
    right.left = NULL;
    right.right = NULL;

    root->left = &left;
    root->right = &right;

    // PLACE A

    insert(0, 1);

    // PLACE B

    return 0;
}

树结构 - 不正确 children

Tree structure - incorrect children

c++

tree