C:当指针实际上指向某物时，函数不断接收归零指针

Question

对于这个令人困惑的标题，我深表歉意，我希望我的解释能帮助您理清目前最有可能出现在您脑海中的迷雾。所以今天我决定尝试创建一个能够插入和搜索特定数字的二叉树程序。现在，当我完成我的搜索功能并决定对其进行测试时，我遇到了一个Segmentation Fault。然后，我使用当前使用的 IDE 运行 GDB 来查找问题的根源。然后 GDB 返回以下消息:

  Program received signal SIGSEGV, Segmentation fault.                                                             
    0x0000000000400634 in search (num=503, dt=0x0) at main.c:39                                                      
    39          if(num < dt->data) {       

我似乎注意到，由于某些奇怪的原因，我的 dt(函数用来导航的结构抛出了二叉树)指针变量已被清零，即使我输入函数的变量是指向分配的缓冲区。这让我困惑了很长一段时间，希望有人能帮助我找出这个问题的根源。

My Code:

#include <stdio.h>
#include <stdlib.h>
#define ROOT_NODE 500
typedef struct _DNode {
    int data;
    struct _DNode *right;
    struct _DNode *left;
}Node;
Node *InitNode();
void insert(int num, Node *dt);
int search(int num, Node *dt);

void insert(int num,Node *dt) {
    if(num <= dt->data) {
       if(dt->left == NULL) {
           dt->left = InitNode(num);
       }else {
           insert(num,dt->left);
            }
    }else {

        if(dt->right == NULL) {
            dt->right = InitNode(num);
        }else {
            insert(num,dt->right);
        }
    }
}

int search(int num,Node *dt) {

    if(num < dt->data) {
        if(dt->left == NULL) {
            return -1;
        }else {
           return search(num,dt->left);
        }
    }else {
        if(num > dt->data) {
            if(dt->right == NULL) {
                return -1;
            } else {
                return search(num,dt->left);
            }
        }
        if(num == dt->data) {
            return 0;
        }
    }
}

Node *InitNode(int num) {
    Node *TNode = (struct _DNode *)malloc(sizeof(Node));
    TNode->right = NULL;
    TNode->left = NULL;
    TNode->data = num;
    return (TNode);
}

int main()
{
     Node *root = InitNode(ROOT_NODE);
     root->data = ROOT_NODE;
     insert(507,root);
     insert(503,root);

     printf("%i",search(503,root));
}

Answer 1

错误!

您的代码中的问题是您调用传递树中错误的节点。就这样

return search(num,dt->left);

在这个地方

if(dt->right == NULL) {
    return -1;
} else {
    return search(num,dt->left);
                      ^^^^^^
}

替代实现

在代码中，您没有利用递归代码。您已经为左右子树重复了相同的不必要代码，这不应该是这种情况。

正确的代码可以这么简单

    int search(int num,Node *dt) {
        if(dt == NULL)  
             return -1;
        else if(dt->data == num) 
             return 0;
        else if(dt->data >= num) 
             return search(num,dt->left);
        else 
             return search(num,dt->right);
    }

还有一件事是关于在您的代码中插入。您永远不会在您的设置中将节点插入到空树中。只有当 root 不是 NULL 时，树插入才会正确工作。所以插入代码应该是

Node * insert(Node *p, int num){
   if(p == NULL)
      return initNode(num);
   else if(num <= p->data)
      return p->left = insert(p->left,num);
   else
      return p->right = insert(p->right,num); 
}

并称它为

root = insert(root, num);