Что-то я не понимаю о функции в двоичных деревьях в C

Question

Ниже приведен пример кода для вставки кода узла в дерево. Пример взят из http://cslibrary.stanford.edu/110/BinaryTrees.html Проблема заключается в следующем: у меня есть базовое понимание указателей и памяти, и я понимаю все, кроме узла вставки. вот структура узла:

struct node { 
  int data; 
  struct node* left; 
  struct node* right; 
}  

Теперь на предоставленной мною странице написано, что этот метод вставки сделан для того, чтобы избежать передачи по ссылке. поэтому вместо вызова insert(struct node** nodeptr, int some data); это называется так: nodeptr = insert(data int). так что мой вопрос Я понимаю часть назначения указателя, что указатель, возвращаемый функцией вставки, помещается в nodeptr. Предположим, что nodeptr является корнем дерева, как это может повлиять на некоторый узел, который будет указывать на новый узел.

struct node* insert(struct node* node, int data) 
{ 
  // 1. If the tree is empty, return a new, single node 
  if (node == NULL) 
  { 
     return(newNode(data)); 
  } 
  else 
  { 
     // 2. Otherwise, recur down the tree 
     if (data <= node->data) 
     {
        node->left = insert(node->left, data); 
     }
     else 
     {
        node->right = insert(node->right, data);
     }

     return(node); // return the (unchanged) node pointer 
   } 
} 

Answer 1

if (data <= node->data) 
    node->left = insert(node->left, data); 
else 
    node->right = insert(node->right, data);

Этот код вызовет insert для левого указателя узла, если данные меньше, чем данные, просматриваемые в данный момент на узле, или он вызовет insert для указателя right узла. В конце концов, когда он нашел правильное место для вставки, путем рекурсивного вызова любого из этих insert s в этом операторе if, это будет NULL-узел, так как больше нет узлов, он создаст новый и return тот, который будет добавлен к левому или правому указателю предыдущего узла. В этот момент он вернется в стек рекурсии.

Answer 2

Элементы left и right узла двоичного дерева могут иметь значение NULL, если к ним не подключено никаких других узлов.В таком узле, если мы перейдем к листу NULL, мы создадим новый узел с newNode(data).

Answer 3

Это может помочь пройти через код для нескольких вставок. Итак, предполагая, что мы вызываем insert из функции foo, наше дерево вызовов будет выглядеть примерно так:

 foo: root = NULL;
 foo: root = insert(root, 5);

     insert: if (node == NULL)
     insert: return newnode(data); // newnode = 0xff864000

 foo: root = 0xff864000

После этого первого обращения к данным наше дерево выглядит примерно так:

Address       data        left            right
-------       ----        ----            -----
0xff864000       5        0x00000000      0x00000000

Теперь мы делаем второй вызов, чтобы вставить новое значение:

foo: root = insert(root, 3);

    insert: if (node == NULL) // node == 0xff864000
    insert: if (data <= node->data)
    insert: node->left = insert(node->left, data);

Теперь мы снова звоним insert; на этот раз node является левым дочерним элементом текущего узла (который должен быть NULL):

        insert(2): if (node == NULL) // node == 0x00000000
        insert(2): return newnode(data); // newnode == 0xff86400c

    insert: node->left = 0xff86400c;
    insert: return node; 

foo: root = 0xff864000

Таким образом, результат этого второго вызова insert назначен левому потомку текущего узла, и наше дерево теперь выглядит примерно так:

Address       data        left            right
-------       ----        ----            -----
0xff864000       5        0xff86400c      0x00000000
0xff86400c       3        0x00000000      0x00000000

Добавить еще один элемент:

foo: root = insert(root, 2);

    insert: if (node == NULL)  // node = 0xff864000
    insert: if (data <= node->data)
    insert: node->left = insert(node->left, data);

        insert(2): if (node == NULL)  // node = 0xff86400c
        insert(2): if (data <= node->data)
        insert(2): node->left = insert(node->left, data);

            insert(3): if (node == NULL)
            insert(3): return newnode(data); // newnode = 0xff864018

        insert(2): node->left = 0xff864018
        insert(2): return node;

   insert: node->left = 0xff86400c
   insert: return node;

foo: root = 0xff8640000

А теперь наше дерево выглядит как

Address       data        left            right
-------       ----        ----            -----
0xff864000       5        0xff86400c      0x00000000
0xff86400c       3        0xff864018      0x00000000
0xff864018       2        0x00000000      0x00000000

И наконец:

foo: root = insert(root, 7);

    insert: if (node == NULL)  // node = 0xff864000
    insert: if (data <= node->data)
    insert: node->right = insert(node->right, data);

        insert(2): if (node == NULL)  // node = 0x0x00000000
        insert(2): return newnode(data); // newnode = 0xff864024

    insert: node->right = 0xff864024
    insert: return node;

foo: root = 0xff8640000

Address       data        left            right
-------       ----        ----            -----
0xff864000       5        0xff86400c      0xff864024
0xff86400c       3        0xff864018      0x00000000
0xff864018       2        0x00000000      0x00000000
0xff864024       7        0x00000000      0x00000000