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);
  }
}