已访问未知的NULL值

Question

这是AVL树的部分程序，但现在只是更多的BST

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
typedef struct node node;

struct node
{
    int data;
    int height;
    node *left;
    node *right;
} *root = NULL, *temp = NULL;

int max(int n1, int n2)
{
    return n1 > n2 ? n1 : n2;
}

node *new_node(int value)
{
    temp = (node *)malloc(sizeof(node));
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;
    temp->height = 0;
    return temp;
}
int get_height(node *x)
{
    if (x == NULL)
    {
        return -1;
    }

    return x->height;
}

node *insert(node *r, int value)
{
    if (r == NULL)
    {
        return new_node(value);
    }
    else
    {
        if (value < r->data)
            r->left = insert(r->left, value);
        else
            r->right = insert(r->right, value);

        int height = max(get_height(r->left), get_height(r->right)) + 1;
}

void inorder(node *r)
{
    if (r == NULL)
        return;
    inorder(r->left);
    printf("node = %d, height = %d\n", r->data, r->height);
    inorder(r->right);
}

void main()
{
    root = insert(root, 10);
    root = insert(root, 20);
    inorder(root);
}

此程序的输出如下，因为我没有访问任何NULL值-

node = 10, height = 1
node = 20, height = 0

仅添加一行之后，我正在访问NULL值

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
typedef struct node node;

struct node
{
    int data;
    int height;
    node *left;
    node *right;
} *root = NULL, *temp = NULL;

int max(int n1, int n2)
{
    return n1 > n2 ? n1 : n2;
}

node *new_node(int value)
{
    temp = (node *)malloc(sizeof(node));
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;
    temp->height = 0;
    return temp;
}
int get_height(node *x)
{
    if (x == NULL)
    {
        return -1;
    }

    return x->height;
}

node *insert(node *r, int value)
{
    if (r == NULL)
    {
        return new_node(value);
    }
    else
    {
        if (value < r->data)
            r->left = insert(r->left, value);
        else
            r->right = insert(r->right, value);

        int height = max(get_height(r->left), get_height(r->right)) + 1;
    int balance_factor = get_height(r->left)- get_height(r->right); // extra line added

  }
}

void inorder(node *r)
{
    if (r == NULL)
        return;
    inorder(r->left);
    printf("node = %d, height = %d\n", r->data, r->height);
    inorder(r->right);
}

void main()
{
    root = insert(root, 10);
    root = insert(root, 20);
    inorder(root);
}

现在我的程序刚刚挂起，它不是无限的调用/循环。它肯定是NULL值访问。但这怎么可能呢？

Answer 1

在函数不返回任何内容时，如果insert收集返回值，函数r != NULL不返回任何指针是未定义的行为。

即

root = insert(root, 10);//it is returning valid pointer
root = insert(root, 20);//unknown value copied to root

请更新

node *insert(node *r, int value)
{
    if (r == NULL)
    {
        return new_node(value);
    }
    //rest of the logic     
    return r;//missing from both of your snippet
}

Answer 2

通过论坛/问答进行调试从没有效率。使用调试器：

例如在https://onlinegdb.com/S1ZansZNU

Reading symbols from a.out...done.                                                                                   
/usr/share/gdb/gdbinit: No such file or directory.                                                                   
(gdb) run                                                                                                            
Starting program: /home/a.out                                                                                        

Program received signal SIGSEGV, Segmentation fault.                                                                 
0x0000000000400703 in inorder (r=0xffffffff) at main.c:62                                                            
62          inorder(r->left);                                                                                        
(gdb)  

r不为NULL，但也不是有效地址。

问题显然在：

root = insert(root, 10);

当插入未显式返回值时