C语言 在链表树的实现过程中出现错误

Question

enter code here
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int data;
struct _node* rightChild;
struct _node* leftChild;
}Node;

Node* create(int data) { // create node function
Node* node = (Node*)malloc(sizeof(node));
node->rightChild = NULL;
node->leftChild = NULL; 
node->data = data;
return node;
}
void Inorder(Node* ptr) { // travel
if (ptr) 
{
printf("%c ", ptr->data);
Inorder(ptr->leftChild);
Inorder(ptr->rightChild); 
}
}
int main(void)
{
Node* node[300];
for (int i = 1; i < 300; i++) {
if (i == 1) {
node[i] = create(i);
}
else {
if (i % 2 == 0) {
node[i / 2]->leftChild = create(i);
}
else {
node[i / 2]->rightChild = create(i);
}
}
}
Inorder(node[10]);
}

我想使用Node*数组实现一个二叉树，而不是一个接一个地接受变量输入。但我总是在这方面出错。谢谢你的建议。我需要修改哪一部分才能使该部分通过for语句实现?据我所知，节点数组的左右部分都传递了值，那么为什么我得到一个错误?

Answer 1

唯一分配给node[i]的是node[1]。所有其他节点通过leftChild或rightChild字段连接。

你可以这样做，例如:

node[i] = create(i);
node[i / 2]->leftChild = node[i];

但是这有点迂回，因为您现在在两个不同的地方拥有相同的数据-节点的句柄。

我猜你真正想要的是一个普通的节点结构数组，然后通过指针链接到数组:

Node node[300] = {{0}};
node[1].data = 1;
for (int i = 2; i < 300; i++) {
node[i].data = i;        
if (i % 2 == 0) {
node[i / 2].leftChild = &node[i];
} else {
node[i / 2].rightChild = &node[i];
}
}

这将创建一个平面的节点数组，其中的节点像二叉树一样被链接。例如，node[1].leftChild是指向node[2]的指针。您可以通过传递&node[1]作为头来使用常规树函数:

Inorder(&node[1]);

(你所说的Inorder实际上是一个预序遍历。)

优点是您不需要create和分配任何东西。当main结束时，不需要free，整个树就消失了。(它还消除了create中的一个bug，即只为指针分配空间，而不是为节点分配空间;应该是node = malloc(sizeof(*node));。)

也许这不是你想要的，但是你的代码中的bug来自于在未设置node[2]时访问它。