C语言 二叉搜索树 C 实现

Binary Search Tree C implementation

提问by Pastafarian

I recently wrote a fairly simple piece of code attempting to implement a Binary Search Tree in C with insertion, search, deletion and display operations. Unfortunately, the code does not seem to work.

我最近写了一段相当简单的代码，试图用 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 fact, notice the commented line printf("%d", rootNode->data);just before the do-whileblock in main()ends. If I uncomment this line, compile the program and run it, the program throws a segmentation fault. Could anyone tell me why this error is occurring and why the code as a whole isn't running? Thanks in advance.

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

回答by Matt Eckert

You have a misconception about the way C handles arguments. In C, all arguments are passed by value, including pointers. When you reassign a pointer inside of a function you are reassigning a copy of that pointer.

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

For instance:

例如：

void f ( int *p );

int *p;

f(p);

The address (&p) of the pointer is different in the function. They both point to the same location (have the same value), but each has a different address. When you assign the pointer to the return value of malloc, it is only assigning the function local copy of that pointer.

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

One way to fix this is to introduce another level of indirection, and pass the address of the pointer: void insertNode(int i, node **n), which you can call like insertNode(0, &n). When you want to change it to something else, dereference it once and thenassign: *p = malloc(sizeof(node)).

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

Another solution is to have the function return the pointer and assign it in the calling code: return malloc(sizeof(node)). (Note: You would actually return it after the initialization code... also don't cast the return value of mallocin C).

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

回答by Joe

The reason why the code segfaults when you uncomment the printf statement is because rootNode is a NULL pointer. Dereferencing this NULL pointer in the function call causes the segfault.

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

The reason that rootNode is a NULL pointer is that it is never changed by the code. Calling insertNode()results in the local variable nbeing set to the value that is stored in rootNode(in this case NULL). The changes to nin the insertNode()function do not change rootNode.

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

To fix the code you could change the insertNodeand deleteNodefunctions to accept a pointer to the root node pointer. For example the insertCode()function would become:

要修复代码，您可以更改insertNode和deleteNode函数以接受指向根节点指针的指针。例如，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);
        }
    }
}

You would also have to change the code to call insertNode()with a reference to rootNode insertNode(num, &rootNode);

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

I also recommend that you check the return values of the various scanf calls. If scanf("%d",x)returns 0 then the value not be converted to an int and the contents of x are undefined. Ideally the code would handle this case gracefully.

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

回答by Victor Sand

At the top, you declare

在顶部，您声明

node *rootNode = NULL; 

If you don't run insertNode(successfully - See Matt's answer), the node will still be NULL when trying to print it and that's why you're getting the segfault.

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

回答by dead programmer

I think the probblem is with the signature for Insert function Try the below code and It will work

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

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

And use Insert Function as

并使用插入函数作为

insertNode(num, &rootNode);

Earlier the changes remain in the function Insert only. Use double pointer inside.

之前的更改仅保留在函数 Insert 中。在里面使用双指针。