c - 在 BST 中插入节点的问题(迭代方法)

Question

下面是我在 BST 中插入节点的代码。我面临段错误。我尝试使用 gdb 进行调试，发现在插入第二个节点时崩溃，即 insert(&root,9) at

current->left = newNode(key);

在 if 条件下的 while 循环内。我无法找到根本原因。请帮助我并告诉我问题是什么。

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

struct Node
{
  int data;
  struct Node *left;
  struct Node *right;
 };

struct Node* newNode(int item)
{
  struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
  temp->data = item;
  temp->left = temp->right = NULL;
  return temp;
}


void insert(struct Node **root_ref,int key)
{
  struct Node *current;
  struct Node *parent;

  if(*root_ref == NULL)
  {
    *root_ref = newNode(key);
  }
  else
  {
    parent = *root_ref;
    while(1)
    {
      current = parent;
      if(current->data > key)
      {
        current = current->left;
        if(current == NULL)
        {
          current->left = newNode(key);
          // break;
          return;
     }
  }
  else
  {
    current = current->right;
    if(current == NULL)
    {
       current->right = newNode(key);
       //break;
       return;
    }
  }
} //End of while
}
 return;
 }

int main()
{
  struct Node *root=NULL;
  insert(&root,10);
  insert(&root,9);
  insert(&root,11);
  insert(&root,12);
  insert(&root,8);
  insert(&root,7);

  return 0;
 }

Answer 1

您尝试访问元素的属性，仅当元素为 NULL !!

current = current->left;
if(current == NULL)
{
  current->left = newNode(key);
  // break;
  return;
}

这就是出现段错误的原因。

您应该测试 left 属性是否为 NULL。如果是，则添加新元素，否则转到左侧。

if(current->left == NULL)
{
  current->left = newNode(key);
  return;
}
else
{
  current = current->left;
}