c - 二进制搜索树插入不起作用

Question

我已经研究这个二叉搜索树一段时间了，但我似乎无法插入或更改任何树属性。

我的二叉树定义为:

struct tree{
    Node * root;
    int size;
};
struct node{
    int value;
    Node * left;
    Node * right;
};

因此我的二叉树由节点组成。现在不起作用的部分:

void add(int value, Tree *t){
    //1. if root is null create root
    if(t->root == NULL){
        t->root = nodeCreate(value);
        t->size ++;
        return;
    }
    Node * cursor = t->root;

    while(cursor != NULL){
        if(value == cursor->value){
            printf("value already present in BST\n");
            return;
        }
        if(value < cursor->value){
            cursor = cursor->left;
        }
        if(value > cursor->value){
            cursor = cursor->right;
        }
    }
    //value not found in BST so create a new node.
    cursor = nodeCreate(value);
    t->size = t->size + 1;
}

有人能告诉我哪里错了吗？我预计对 add() 的调用会增加成员的大小并创建新节点，但我似乎无法理解。

Answer 1

我相信以下更改会解决您的问题。

void add(int value, Tree *t){
    if(t->root == NULL){
        t->root = nodeCreate(value);
        t->size ++;
        return;
    }
    Node * cursor = t->root;
    Node * last = null;
    while(cursor != NULL){
        last = cursor;
        if(value == cursor->value){
            printf("value already present in BST\n");
            return;
        }
        if(value < cursor->value){
            cursor = cursor->left;
        }
        if(value > cursor->value){
            cursor = cursor->right;
        }
    }
    //value not found in BST so create a new node.
    cursor = nodeCreate(value);
    if (value > cursor->value)
    {
        last->right = cursor;
    }
    else
    {
        last->left = cursor;
    }
    t->size = t->size + 1;
}