c - 二叉搜索树问题

Question

我正在处理一个二叉树，其中的列表附加到数据上，但我无法判断列表是否已填充。代码运行正常，但是当我尝试调用打印树时，我的代码卡住了。我相信一切都被正确指出，但很明显某个地方的逻辑存在缺陷。

结构声明

typedef struct lineList
{
    int lineNum;
    LIST *next;
}LIST;

typedef struct nodeTag{
   char data[80];
   LIST *lines;
   struct nodeTag *left;
   struct nodeTag *right;
} NODE;

声明并从 main 传递给函数

NODE *root = NULL;
readFromFile(argv[1], root);

readfromfile(工作函数)然后调用insertword

insertWord(root, keyword, lineNum);

insertWord、addToList 函数(问题区域)

NODE *allocateNode(char *data, int line)
{
    NODE *root;
    LIST *newNum;
    if(!(root = (NODE *) malloc (sizeof(NODE))))
        printf( "Fatal malloc error!\n" ), exit(1);

    strcpy(root->data, data); //copy word
    (root)->left  = (root)->right = root->lines = NULL; //initialize

    if (!(newNum =(LIST *) malloc (sizeof(LIST))))
        printf( "Fatal malloc error!\n" ), exit(1);
    newNum->lineNum = line;
    root->lines = newNum;

    return root;
}

/****************************************************************
   ITERATIVE Insert
*/
NODE *insertWord(NODE *root, char *data, int line)
{
    NODE *ptr_root = root;
    printf("inserting %s\n", data);

    if(root == NULL)
    {
        root = allocateNode(data, line);
        return root;
    }
    while(ptr_root)
    {   
      if (strcmp(data, ptr_root->data > 0))
      {
          if(ptr_root->right)
            ptr_root = ptr_root->right;  //traverse right
          else
            ptr_root->right = allocateNode(data, line);
      }
      else if (strcmp(data, ptr_root->data) < 0)
      { 
          if(ptr_root->left) //traverse left
            ptr_root = ptr_root->left;
          else
            ptr_root->left = allocateNode(data, line);
      }
      else
        {
            printf("Node already in the tree!\n");
            addToList(ptr_root, line);
        }
    }
    printf("5\n");
   return root;
}

void printTreeInorder(NODE *root)//simple print, freeze on call to function
{   
   if(root)
    {
      printTreeInorder(root->left);
      printf( "%s\n",  root->data );
      printTreeInorder(root->right);
   }
   return;
}

Answer 1

让我们看看 insertWord():

1. 在 while 循环结束时，我们知道 ptr_root == NULL。
2. 然后我们为 ptr_root 分配内存。
3. 然后我们初始化 ptr_root 的内容。
4. 然后，我们对 ptr_root 执行内存泄漏。

注意，需要保留新节点的父节点，并且需要将其左指针或右指针指向该新节点。

听起来您也了解如何使用调试器。如果确实如此，您应该能够看到 root 在调用 insertWord() 之间不会发生变化。

<小时/>

在您发布的尝试修复的代码中，您遗漏了一件关键的事情。我们来看一个函数:

void foo(NODE *root) {
    printf("before malloc:   %p\n", root);
    root = malloc(sizeof(NODE));
    printf("after malloc:    %p\n", root);
}

int main() {
    NODE *root = NULL;
    printf("before function: %p\n", root);
    foo(root);
    printf("after function:  %p\n", root);
}

此代码将产生:

before function: 0x0
before malloc:   0x0
after malloc:    0x123ab129
after function:  0x0

请注意，对 root 值的任何更改都不会传播到函数之外。不过，您更改为 *root 的内容会如此。