C-二叉搜索树

Question

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

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

以下是插入函数：

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

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

Answer 1

问题出在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);
    }
}