Невозможно понять логику вставки в бинарное дерево поиска

Question

Я изучал бинарное дерево поиска, и я пришел через этот код, который я не могу понять

// голова является корневым узлом & Num является ключевым элементом

void generate(struct node **head, int num) 
{ 
    struct node *temp = *head, *prev = *head; 
    if (*head == NULL) 
    { 
     *head = (struct node *)malloc(sizeof(struct node)); 
     (*head)->a = num; 
     (*head)->left = (*head)->right = NULL; 
    } 
    else 
    { 
     while (temp != NULL) 
     { 
      if (num > temp->a) 
      { 
       prev = temp; 
       temp = temp->right; 
      } 
      else 
      { 
       prev = temp; 
       temp = temp->left; 
      } 
     } 
     temp = (struct node *)malloc(sizeof(struct node)); 
     temp->a = num; 

// Я не в состоянии понять следующие строки

 if (num >= prev->a) 
     { 
      prev->right = temp; 
     } 
     else 
     { 
      prev->left = temp; 
     } 
    } 

} 

Answer 1

в бинарном дереве поиска левый ребенок имеет более низкое значение, что родитель, и вышка ht имеет более высокое значение родительского. Затем, если вы хотите вставить новый узел, вы должны найти его сайт. Хотя значение узлов дерева меньше вашего num, вы перемещаетесь по дереву справа. Когда значение одного узла больше, чем ваше число, вы перемещаете дерево слева, а не вправо. Это цикл до тех пор, пока вы не достигнете NULL-узла, который будет местом вашего нового узла со значением num.

Answer 2

В этом блоке кода.

prev указатель указывает на листовой узел после прохождения всего дерева на основе значения num.

Темп является NULL, так что пространство было выделено с помощью таНос так, что он может содержать узел со значением, как NUM.

Теперь, если значение num больше значения его родителя, то есть prev-> a, temp станет правильным ребенком prev.

Если значение num больше значения его родителя i.e prev-a, temp станет левым ребенком prev.

Answer 3

Чуть выше кода, который вы не понимаете, программа идет по дереву, идущему влево или вправо. Когда num меньше, чем значение, хранящееся в узле temp, исследование продолжается на левой ветви, иначе оно продолжается в правой ветви. Во время этого процесса он отслеживает prev, который является родительским узлом temp.

Поиск заканчивается, когда temp - null. Это означает, что нет узла, прикрепленного к левой или правой ветке, куда мы хотели идти. Здесь нужно указать num.

Затем он создает новый узел с именем temp, сохраняет в нем num. Обратите внимание, что здесь есть небольшая ошибка. Не следует указывать возвращаемое значение malloc. Этот malloc работает, но считается плохой практикой.

Затем он проверяет, должен ли узел быть присоединен как левая или правая ветвь родительского узла prev и приложить его соответствующим образом. Это то, что делает код, который вы не понимаете.

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

temp = (struct node *)malloc(sizeof(struct node)); 
temp->a = num; 
temp->right = temp->left = NULL; // <-- missing instruction