如何将数字插入到 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中的局部变量。您对其所做的任何更改都不会反映在调用函数中。

您应该从调用函数中将根指针的地址作为 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 中的任何东西。其次，这个函数应该 free 所有节点，而不是仅仅将根设置为 NULL。（也就是说，你应该写这个函数，这样你就可以在使用后释放树。）

Answer 2

你的 TREEinsert 函数中的 t 是一个局部变量，所以你有两个选择：要么你 return 它并具有如下代码，要么你的参数 t 应该是 struct node**
所以第一个选项是：

 struct node* 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;
    return t ;
  }
 else
  {
    if (x < t->info)
        return(TREEinsert(t->left, x));
    if (x > t->info)
       return(TREEinsert(t->right, x));
  }


}

第二个选项是：

void TREEinsert(struct node **t, int x)
{
    if (*t == NULL) {
        *t = malloc(sizeof(**t));
        (*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);
    }
}

旁注：您可能需要检查 malloc 是否成功。

Answer 3

首先函数TREEclear并没有把原来的三头置零。它处理头部的副本。原头没变。

函数的名称也很混乱。最好将其命名为例如 TREEinit.

可以这样看

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

递归函数TREEinsert可以看起来像

void TREEinsert( struct node * *t, int x )
{
    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 );
    }
    else if ( x > ( *t )->info )
    {
        TREEinsert( &( *t )->right, x );
    }
}

它应该被称为

TREEinsert( &root, 5 );

考虑到您还需要编写一个函数来释放所有为树分配的内存。

Answer 4

There is two way to fixed it
1. change the return type of Insert function 


Struct node * TREEinsert(){
              //your code

            return the local variable( t)
           }

2. If you don't want to change the return type of function then change the argument you are passing to Insert function
            TREEinsert(&root, intVariable);
    and in  TREEinsert(Struct node **,int);

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

How to insert numbers into a binary search tree in C?

c

malloc

binary-tree

linked-list

binary-search-tree