c - C-二进制搜索树

我试图建立一个二叉搜索树。但是在执行不同的遍历时，我没有得到正确的输出。

typedef struct binary_search_tree{
    struct binary_search_tree *lchild;
    int data;
    struct binary_search_tree *rchild;
}bst_t;

#define ALLOCATE (bst_t*)malloc(sizeof(bst_t))

下面是insert函数：

void insert(bst_t *ptr,int data){
    if( ptr->data < data){
        if ( ptr->lchild == NULL ){
            ptr->lchild = ALLOCATE;
            ptr->lchild->data = data;
            return;
        }else
            insert(ptr->lchild,data);
    }else{
        if ( ptr->rchild == NULL ){
            ptr->rchild = ALLOCATE;
            ptr->rchild->data = data;
            return;
        }else
            insert(ptr->rchild,data);
    }
}

这个功能正确吗？
调用该函数时，我正在发送根的地址。

最佳答案

问题是ALLOCATE宏。它没有足够的能力正确分配和初始化一个新节点。我建议创建一个newNode函数，为节点分配内存，然后初始化结构的所有成员，如下所示

bst_t *newNode(int data)
{
    // allocation and error checking
    bst_t *node = malloc(sizeof(bst_t));
    if ( node == NULL )
    {
        fprintf(stderr, "out of memory\n");
        exit( 1 );
    }

    // initialize the members of the structure
    node->lchild = NULL;
    node->data = data;
    node->rchild = NULL;

    return node;
}

然后insert函数可以简化为

void insert(bst_t *ptr,int data)
{
    if( ptr->data < data){
        if ( ptr->lchild == NULL )
            ptr->lchild = newNode(data);
        else
            insert(ptr->lchild,data);
    }else{
        if ( ptr->rchild == NULL )
            ptr->rchild = newNode(data);
        else
            insert(ptr->rchild,data);
    }
}