c - 我无法将节点插入到 bin 搜索树中

Question

我想写一个BST，但是插入功能不起作用。调试它，我发现它没有插入。

/* Binary Search Tree (BST).demo */
#include <stdio.h>
#include <stdlib.h>

typedef struct treeNode{
    int data;
    struct treeNode* lChild;
    struct treeNode* rChild;
 } treeNode;

treeNode* createNode(){
        treeNode *nNode;
        nNode=(struct treeNode*)malloc(sizeof(treeNode));
        nNode->data=0;
        nNode->lChild=NULL;
        nNode->rChild=NULL;

        return nNode;
}

void insert(treeNode* rt,int idata)
{
  if(rt==NULL){
    treeNode* nNode;
    nNode=createNode();
    nNode->data=idata;
    rt=nNode;
    rt->lChild=NULL;
    rt->rChild=NULL;
  }else{
    if(idata < rt->data)
        insert(rt->lChild,idata);
    else insert(rt->rChild,idata);

  }
}

int main()
{
    treeNode *root;
    root=(treeNode*)malloc(sizeof(treeNode));
    root->data=15;
    root->lChild=NULL;
    root->rChild=NULL;

    insert(root,13);
    if(root->lChild==NULL)
          printf("root no l child\n");
     // printf("root lchild data :%d",root->lChild->data);
   return 0;
}

Answer 1

使用它作为插入函数：

void insert(treeNode** rt,int idata)
{
     if((*rt)==NULL)
     {
       treeNode* nNode;
       nNode=createNode();
       nNode->data=idata;
       *rt=nNode;
       (*rt)->lChild=NULL;
       (*rt)->rChild=NULL;
     }
     else
     {
         if(idata < (*rt)->data)
             insert(&((*rt)->lChild),idata);
         else 
             insert(&((*rt)->rChild),idata);
     }
}

和 main() 中的插入函数调用为：

insert(&root,13);

Answer 2

我通常是这样实现的：

void insert(treeNode* rt, int idata) {
    // assert( rt != NULL );
    if(idata < rt->data){
        if( rt->lChild != NULL)
            insert(rt->lChild, idata);
        else {
            rt->lChild = createNode();
            rt->lChild->data = idata;
        }
    } else {
        if( rt->rChild != NULL)
            insert(rt->rChild, idata);
        else {
            rt->rChild = createNode();
            rt->rChild->data = idata;
        }
    }
}

---

此外，我更愿意为createNode()

treeNode* createNode(int idata){
    // ...
    nNode->data = idata;
    // ...
}

所以insert会看起来像：

void insert(treeNode* rt, int idata) {
    // ...
            rt->lChild = createNode(idata);
    // ...
            rt->rChild = createNode(idata);
    // ...
}