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（这是一个函数用来导航二进制树的结构）指针变量已被清零，即使我输入函数的变量指向一个分配缓冲区。这让我困惑了很长一段时间，希望有人可以帮助我弄清楚这个问题的根源。

我的代码：

#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

Bug!

您的代码中的问题是您正在调用树中传递错误的节点。所以它会

return search(num,dt->left);

在这个地方

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

Alternative Implementation

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

正确的代码可以像这样简单

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

Answer 2

在：

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

你可能意味着：

           ...
                return search(num,dt->right);
           ...