c - 如何将数字插入到 C 中的二叉搜索树中？

Question

我试图通过从主函数调用 TREEinsert 函数来将数字列表插入到二叉搜索树中，但是无论何时我的程序运行，它都不会打印插入到二叉搜索树中的任何数字。我已经检查了我的 TREEinsert 函数和 Displayinorder 函数，但似乎无法发现这两个函数的功能有任何问题。我对二叉搜索树有基本的了解，并查看了许多示例，试图深入了解 BST 的工作原理。任何指导都会非常有帮助。

struct node
 {
     int info;
     struct node *left;
     struct node *right;
 };



void TREEclear(struct node* t)
{
     t = NULL;
}

void TREEinsert(struct node*  t, int x)
{

    //insert in BST
    if(t == NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        t->info = x;
        t->left = NULL;
        t->right = NULL;
    }
    else
    {
        if (x < t->info)
        TREEinsert(t->left, x);
        if (x > t->info)
            TREEinsert(t->right, x);
    }
}

void Displayinorder(struct node* t)
{
    //in order: (LC)(P)(RC)
    if (t != NULL)
    {
        Displayinorder(t->left); //LC
        printf("%d\t", t->info); //P
        Displayinorder(t->right); //RC
    }
}

struct node *root;

int main()
{
    TREEclear(root);

    TREEinsert(root, 5);
    TREEinsert(root, 8);
    TREEinsert(root, 2);
    TREEinsert(root, 6);

    Displayinorder(root);

    printf("\n\n");
    system("PAUSE");
    return 0;
 }

Answer 1

节点指针t 是TREEinsert 中的局部变量。您对其所做的任何更改都不会反射(reflect)在调用函数中。

您应该从调用函数中将根指针的地址作为 struct node *p 传递。递归时，分别传入当前节点的左指针或右指针的地址。

方法如下:

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

struct node {
    int info;
    struct node *left;
    struct node *right;
};


void TREEclear(struct node *t)
{
    t = NULL;
}

void TREEinsert(struct node **t, int x)
{
    if (*t == NULL) {
        *t = malloc(sizeof(**t));
        // TODO: check allocation success

        (*t)->info = x;
        (*t)->left = NULL;
        (*t)->right = NULL;
    } else {
        if (x < (*t)->info) TREEinsert(&(*t)->left, x);
        if (x > (*t)->info) TREEinsert(&(*t)->right, x);
    }
}

void Displayinorder(struct node *t)
{
    if (t != NULL) {
        Displayinorder(t->left);
        printf("%d\n", t->info);
        Displayinorder(t->right);
    }

}

int main()
{
    struct node *root = NULL;

    TREEinsert(&root, 5);
    TREEinsert(&root, 8);
    TREEinsert(&root, 2);
    TREEinsert(&root, 6);

    Displayinorder(root);

    // TODO: need to free the tree nodes

    return 0;
}

请注意，您将 &root 传递给插入函数，这可能需要对其进行修改，但只需将 root 传递给显示函数，它只需对其进行检查。

我已经摆脱了你的 TREEclear 功能。首先，它与您原来的 TREEinsert 存在相同的问题:它修改了一个局部变量，但不更改 main 中的任何内容。其次，此函数应该释放所有节点，而不仅仅是将根节点设置为NULL。 (也就是说，你应该写这个函数，这样你就可以在使用后释放树。)