C：如何在循环中向树添加节点？

Question

我制作了一个只有根的树结构。然后由用户来创建节点并将它们作为子节点添加到根节点或其他现有节点。结构如下：

#define MAXCHILDREN 5      //max children a node can have

typedef struct node{
    unsigned int id;
    struct node* parent;
    struct node* children[MAXCHILDREN];
}node;

typedef struct spantree{
    node root;
}spantree;

现在我想要实现的是创建 4 个节点并将它们作为子节点添加到根。这是我所做的，但不能正常工作：

for (i=0; i<4; i++){
        node newNode;
        newNode.id=i;
        addChild(&newNode, &Root);  
    }

当我运行时，这不起作用

showChildId(0, &root); //其中第一个数字表示第一个孩子、第二个孩子等。

showChildId(1, &root);

等等

我得到相同的 id，这意味着只添加了一个孩子。那么我该如何继续创建 4 个不同节点并将它们添加到循环中的父节点（在本例中为根节点）？

Answer 1

您正在将临时值添加到子列表中：

node newNode;

这会在堆栈上创建一个值，该值仅存在于以下“}”之前。下一次迭代很可能会为新对象重新使用相同的内存块。您需要动态创建对象而不是堆栈分配它：

node *newNode = malloc sizeof (node);
newNode->id = i;
addChild (newNode, &Root);

您确实需要确保正确释放节点，否则您将泄漏内存。释放节点内存的函数应该为每个子节点递归调用自身。

Answer 2

这对我来说就像是家庭作业，所以我会尽力提供指导而不是明确的答案。

在此循环中：

for (i=0; i<4; i++){
    node newNode;   // <-- newNode is created on the stack here .
    newNode.id=i;
    addChild(&newNode, &Root);  
                    // <-- and is removed from the stack here.
}

newNode 在循环的每次迭代中都会在堆栈上创建，并且仅在迭代结束之前有效。

为了让它活得更久，你需要在堆上为其分配一些内存。看一下 malloc() 和 free()。

Answer 3

与亚历克西斯不同，我在算法的这个级别上看不到任何东西，但我不确定您是否正在跳过细节或感到困惑。

for (i=0; i<4; i++){ // I think you mean 5 here -- or rather MAXCHILDREN.
        node newNode; // This is a temporary on the stack.
        newNode.id=i;
        addChild(&newNode, &Root);   // &newNode is a pointer to that temporary.
    }

所以addChild每次都会得到一个指向临时newNode的指针。它恰好位于堆栈上的同一地址，因此它们都指向同一位置。所以他们都有相同的 ID。不过，该堆栈位置可能已被覆盖，因此它可能是一些完全随机的值。

for (i=0; i<MAXCHILDREN; i++){
        node *newNode = new node(); // C++, or use malloc if you're stuck in C
        newNode->id=i;
        addChild(newNode, &Root);  
    }

应该让你更接近你想做的事情。