0

このバイナリ検索ツリーでしばらく遊んでいますが、ツリーのプロパティを挿入または変更できないようです。

私の二分木は次のように定義されています：

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()、メンバーのサイズが増加し、新しいノードが作成されると予想していましたが、取得できないようです。

4

3 に答える 3

1

ループに設計上の欠陥と完全なバグの両方があります。

設計上の欠陥: 新しいノードを割り当ててcursorいますが、最初にそこに到達した左または右の子ポインターを親ノードに割り当てるという意味ではありません。設定する実際のポインターへの参照が必要です。これを行う 1 つの方法は、ポインターからポインターを使用することです。ボーナスとして、これにより、最初の is-my-root-null チェックが不要になります。

明らかなバグ: 左側の移動句 (つまり、左側のポインターを追跡する) がcursorNULL に変更される可能性があります。ただし、右側を追跡するためのロジックは、else if条件で除外されません。検索がヌルの左側に続く場合、ヌル ポインターの右側を追跡するのに失敗します。これは明らかに問題でした。

void add(int value, Tree *t)
{
    Node **pp = &(t->root);
    while (*pp)
    {
        if(value == (*pp)->value) {
            printf("value already present in BST\n");
            return;
        }
        if(value < (*pp)->value)
            pp = &(*pp)->left;

        else if(value > (*pp)->value)
            pp = &(*pp)->right;
    }
    *pp = nodeCreate(value);
    t->size++;
}

また、strict-weak 順序を想定することで、等価性チェックをスキップできることにも注意してください。つまり、次のルールは有効と見なすことができます。

if (!(a < b) && !(b < a)) then a == b is true.

これにより、挿入も簡単になります。

void add(int value, Tree *t)
{
    Node **pp = &(t->root);
    while (*pp)
    {
        if (value < (*pp)->value)
            pp = &(*pp)->left;

        else if ((*pp)->value < value)
            pp = &(*pp)->right;

        else { // must be equal.
            printf("value already present in BST\n");
            return;
        }
    }
    *pp = nodeCreate(value);
    t->size++;
}
于 2013-10-25T17:15:53.817 に答える
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;
}
于 2013-10-25T17:13:01.743 に答える