5

我最近写了一段相当简单的代码，试图用 C 语言实现一个带有插入、搜索、删除和显示操作的二叉搜索树。不幸的是，代码似乎不起作用。

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

struct TreeNode {
    int data;
    struct TreeNode *leftChildNode;
    struct TreeNode *rightChildNode;
};

typedef struct TreeNode node;
node *rootNode = NULL;

void insertNode(int i, node *n) {
    if(n == NULL) {
        n = (node*)malloc(sizeof(node));
        n->leftChildNode = NULL;
        n->rightChildNode = NULL;
        n->data = i;
    }
    else 
    if(n->data == i)
        printf("\nThis value already exists in the tree!");
    else
    if(i > n->data)
        insertNode(i, n->rightChildNode);
    else
        insertNode(i, n->leftChildNode);
    }

void searchNode(int i, node *n) {
    if(n == NULL)
        printf("\nValue does not exist in tree!");
    else
    if(n->data == i)
        printf("\nValue found!");
    else
    if(i > n->data)
        searchNode(i, n->rightChildNode);
    else
        searchNode(i, n->leftChildNode);
    }

void deleteNode(int i, node *n) {
    if(n == NULL)
        printf("\nValue does not exist in tree!");
    else
    if(n->data == i) {
        if(n->leftChildNode == NULL)
            n = n->rightChildNode;
        else
        if(n->rightChildNode == NULL)
            n = n->leftChildNode;
        else {
            node *temp = n->rightChildNode;
            while(temp->leftChildNode != NULL)
                temp = temp->leftChildNode;
            n = temp;
        }
    }
    else
    if(i > n->data)
        deleteNode(i, n->rightChildNode);
    else
        deleteNode(i, n->leftChildNode);
    }

void displayPreOrder(node *n) {
    if(n != NULL) {
        printf("%d ", n->data);
        displayPreOrder(n->leftChildNode);
        displayPreOrder(n->rightChildNode);
    }
}

void displayPostOrder(node *n) {
    if(n != NULL) {
        displayPostOrder(n->leftChildNode);
        displayPostOrder(n->rightChildNode);
        printf("%d ", n->data);
    }
}

void displayInOrder(node *n) {
    if(n != NULL) {
        displayInOrder(n->leftChildNode);
        printf("%d ", n->data);
        displayInOrder(n->rightChildNode);
    }
}

int main(void) {
    int ch, num, num1;
    do {
        printf("\nSelect a choice from the menu below.");
        printf("\n1. Insert a node.");
        printf("\n2. Search for a node.");
        printf("\n3. Delete a node.");
        printf("\n4. Display the Binary Search Tree.");
        printf("\nChoice: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1: printf("\nEnter an element: ");
                    scanf("%d", &num);
                    //printf("YESYES");
                    insertNode(num, rootNode);
                    break;

            case 2: printf("\nEnter the element to be searched for: ");
                    scanf("%d", &num);
                    searchNode(num, rootNode);
                    break;

            case 3: printf("\nEnter the element to be deleted: ");
                    scanf("%d", &num);
                    deleteNode(num, rootNode);
                    break;

            case 4: printf("\nSelect an order for the elements to be display in.");
                    printf("\n1. Pre-order.");
                    printf("\n2. Post-order.");
                    printf("\n3. In-order.");
                    printf("\nChoice: ");
                    scanf("%d", &num1);
                    switch(num1) {
                        case 1: printf("\nPre-order Display: ");
                                displayPreOrder(rootNode);
                                break;

                        case 2: printf("\nPost-order Display: ");
                                displayPostOrder(rootNode);
                                break;

                        case 3: printf("\nIn-order Display: ");
                                displayInOrder(rootNode);
                                break;

                        default: exit(0);
                    }
                    break;

            default: exit(0);
            }
        //printf("%d", rootNode->data);
        printf("\nIf you want to return to the menu, press 1.");
        printf("\nChoice: ");
        scanf("%d", &num);
    } while(num == 1);

    return 0;
}

事实上，请注意块 in结束printf("%d", rootNode->data);之前的注释行。如果我取消注释这一行，编译程序并运行它，程序会引发分段错误。谁能告诉我为什么会发生这个错误以及为什么整个代码没有运行？提前致谢。do-whilemain()

4

4 回答 4

5

您对 C 处理参数的方式有误解。在 C 中，所有参数都按值传递，包括指针。当您重新分配函数内部的指针时，您正在重新分配该指针的副本。

例如：

void f ( int *p );

int *p;

f(p);

指针的地址（&p）在函数中是不同的。它们都指向同一个位置（具有相同的值），但每个都有不同的地址。当您将指针分配给 的返回值时malloc，它只是分配该指针的函数本地副本。

解决此问题的一种方法是引入另一个级别的间接，并传递指针的地址：void insertNode(int i, node **n)，您可以将其称为insertNode(0, &n)。当您想将其更改为其他内容时，请取消引用一次，然后分配：*p = malloc(sizeof(node))。

另一种解决方案是让函数返回指针并在调用代码中分配它：return malloc(sizeof(node)). （注意：您实际上会在初始化代码之后返回它......也不要malloc在 C 中转换返回值）。

于 2013-05-09T01:46:14.077 回答
1

在顶部，您声明

node *rootNode = NULL;

如果您不运行insertNode（成功 - 请参阅 Matt 的回答），则该节点在尝试打印时仍将为 NULL，这就是您遇到段错误的原因。

于 2013-05-09T01:41:02.920 回答
1

取消注释 printf 语句时代码段错误的原因是因为 rootNode 是一个 NULL 指针。在函数调用中取消引用此 NULL 指针会导致段错误。

rootNode 是 NULL 指针的原因是它永远不会被代码更改。调用insertNode() 会导致将局部变量n设置为存储在其中的值rootNode（在本例中为 NULL）。n函数中的更改insertNode()不会改变rootNode。

要修复代码，您可以更改insertNodeanddeleteNode函数以接受指向根节点指针的指针。例如，insertCode()函数将变为：

void insertNode(int i, node **n) {
    if(*n == NULL) {
        (*n) = (node*)malloc(sizeof(node));
        (*n)->leftChildNode = NULL;
        (*n)->rightChildNode = NULL;
        (*n)->data = i;
    }
    else
    {
        if((*n)->data == i)
        {
            printf("\nThis value already exists in the tree!");
        }
        else
        {
            if(i > (*n)->data)
                insertNode(i, &(*n)->rightChildNode);
            else
                insertNode(i, &(*n)->leftChildNode);
        }
    }
}

您还必须更改代码以insertNode()使用对 rootNode 的引用进行调用insertNode(num, &rootNode);

我还建议您检查各种 scanf 调用的返回值。如果scanf("%d",x)返回 0，则该值不会转换为 int，并且 x 的内容未定义。理想情况下，代码会优雅地处理这种情况。

于 2013-05-09T02:24:26.500 回答
0

我认为问题在于插入函数的签名尝试下面的代码，它会起作用

void insertNode(int i, node **n) {
    if(*n == NULL) {
        *n = (node*)malloc(sizeof(node));
        (*n)->leftChildNode = NULL;
        (*n)->rightChildNode = NULL;
        (*n)->data = i;
    }
    else 
    if((*n)->data == i)
        printf("\nThis value already exists in the tree!");
    else
    if(i > (*n)->data)
        insertNode(i, &((*n)->rightChildNode));
    else
        insertNode(i, &((*n)->leftChildNode));
    }

并使用插入功能作为

insertNode(num, &rootNode);

之前的更改仅保留在功能插入中。在里面使用双指针。

于 2013-05-09T02:44:26.637 回答