如何在C中的二进制搜索树中插入数字？

Question

我试图通过调用TREEinsert函数frim主函数插入一个数字列表到二进制搜索树，但是每当我的程序运行它不打印任何数字插入二进制搜索树。我已经完成了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到显示functon，其中只有检查它。

我已经摆脱了您的TREEclear功能。首先，它具有与原始TREEinsert相同的问题：它会修改局部变量，并且不会更改main中的任何内容。其次，这个功能应该是free所有节点，而不仅仅是将根设置为NULL。在TREEinsert功能（这就是说，你应该写这个功能，这样就可以在使用后解除分配树）

Answer 2

的t是一个局部变量，因此从那里，你有两个选择：要么你回吧，并有如下图所示，或您的参数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);