C malloc 指向 NULL 的指针不起作用

Question

我正在编写一个在二叉搜索树中插入新节点的函数。为了避免有太多 if-else，我使用了一个名为 nodeSide 的指针，它指向节点的左侧或右侧，如下所示：

void insertHelper(Node *node, int val) {

  Node *nodeSide;
  if (val < node->val) {
    nodeSide = node->left;
  } else {
    nodeSide = node->right;
  }

  if (nodeSide == NULL) {
    nodeSide = (Node *)malloc(sizeof(Node));
    nodeSide->val = val;
    nodeSide->left = NULL;
    nodeSide->right = NULL;
    return;
  }
  else {
    insertHelper(nodeSide, val);
  }
}

但是，实际上并没有添加该节点。好像是这样做的：

Node *node =  malloc(...);
node->left = NULL;
Node *anotherNode = nodeLeft;
anotherNode = malloc(...);

实际上并没有向树添加新节点。任何想法为什么？指针应该指向正确的位置，无论它是否为空。还是我错了？

这是我的完整代码：

#include <stdlib.h>
#include <stdio.h>

typedef struct _node {
  int val;
  struct _node * left;
  struct _node * right;
  int ht;
} Node;


void insertHelper(Node *node, int val) {

  Node *nodeSide;
  if (val < node->val) {
    nodeSide = node->left;
  } else {
    nodeSide = node->right;
  }

  if (nodeSide == NULL) {
    nodeSide = (Node *)malloc(sizeof(Node));
    nodeSide->val = val;
    nodeSide->left = NULL;
    nodeSide->right = NULL;
    return;
  }
  else {
    insertHelper(nodeSide, val);
  }
}

Node * getNode(int value) {
  Node * node = (Node * )malloc(sizeof(Node));
  node->val = value;
  node->left = NULL;
  node->right = NULL;
  node->ht = 0;
  return node;
}

Node * getTree() {
  Node *root = getNode(3);
  Node *rootLeft = getNode(2);
  root->left = rootLeft;
  Node *rootRight = getNode(4);
  root->right = rootRight;
  Node *rootRightRight = getNode(5);
  rootRight->right = rootRightRight;
  return root;
}

int main() {

  Node * root = getTree();

  insertHelper(root, 6);

  // to verify:
  printf("%d", root->right->right->right->val);

  return 0;
}

Answer 1

您的代码不会存储您在树中任何位置创建的新节点。

也许你可以做，例如

if (nodeSide == NULL) {
    nodeSide = (Node *)malloc(sizeof(Node));
    nodeSide->val = val;
    nodeSide->left = NULL;
    nodeSide->right = NULL;
    if (val < node->val)
       node->left = nodeSide;
    } else {
       node->right = nodeSide;
    }
    return;
  }

但是你可以使用双指针，以避免额外的 if/else：

  Node **nodeSide;
  if (val < node->val) {
    nodeSide = &node->left;
  } else {
    nodeSide = &node->right;
  }

  if (*nodeSide == NULL) {
    *nodeSide = (Node *)malloc(sizeof(Node));
    (*nodeSide)->val = val;
    (*nodeSide)->left = NULL;
    (*nodeSide)->right = NULL;
    return;
  }
  else {
    insertHelper(*nodeSide, val);
  }
}

Answer 2

您 insertHelper 似乎在 return 之前缺少一行相关代码：

node->left = nodeSide;

但请记住要在哪一侧添加值。也许您应该在函数内将相关端作为变量进行跟踪。

C malloc 指向 NULL 的指针不起作用

C malloc to pointer to NULL not working

c

pointers

binary-search-tree