Двоичный поиск Вставка дерева не работает

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

Answer 2

У вас есть как дефект дизайна, так и ошибка в вашей петле.

Недостаток дизайна: вы назначаете новый узел, но присвоение cursor не означает, что вы назначаете родительский узел левого или правого дочернего указателя, который доставил вас туда в первую очередь. Вам нужна ссылка на фактический указатель, который вы собираетесь заполнить. Один из способов сделать это - с указателем на указатель, и в качестве бонуса это исключает проверку is-my-root-null в начале.

Исключительная ошибка: ваше предложение о левом движении (то есть, преследующее левый указатель) потенциально изменит cursor на NULL. но логика для преследования правой стороны не исключается с условием 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++; 
} 

Следует также отметить, что вы можете пропустить проверку равенства, приняв строго-слабый порядок. То есть следующее правило может считаться действительным:

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

Answer 3

Вы не назначаете никому из существующих узлов, чтобы указывать на новый узел. Вы ходите по дереву, создаете новый узел, когда вы дойдете до конца, но вы не устанавливаете, чтобы существующие узлы указывали на новый узел.

Вы можете изменить свою структуру на что-то вроде:

if (value < cusor->value) 
{ 
    if (cursor->left) 
    { 
    cursor = cursor->left; 
    } 
    else 
    { 
    cursor->left = newNode(value); 
    break; 
    } 
} 

с подобной логикой для правого курсора.