Почему указатель на указатель используется в этой проге?

Question

Следующая программа показывает, как построить двоичное дерево в программе на Си. Он использует динамическое выделение памяти, указатели и рекурсию. Бинарное дерево является очень полезной структурой данных, поскольку позволяет эффективно вставлять, искать и удалять в отсортированном списке. Поскольку такое дерево по сути является рекурсивно определенной структурой, рекурсивное программирование является естественным и эффективным способом его обработки.

tree
   empty
   node left-branch right-branch

left-branch
   tree

right-branch
   tree

Вот код:

#include <stdlib.h>
#include <stdio.h>

struct tree_el {
   int val;
   struct tree_el * right, * left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item) {
   if(!(*tree)) {
      *tree = item;
      return;
   }
   if(item->val<(*tree)->val)
      insert(&(*tree)->left, item);
   else if(item->val>(*tree)->val)
      insert(&(*tree)->right, item);
}

void printout(node * tree) {
   if(tree->left) printout(tree->left);
   printf("%d\n",tree->val);
   if(tree->right) printout(tree->right);
}

void main() {
   node * curr, * root;
   int i;

   root = NULL;

   for(i=1;i<=10;i++) {
      curr = (node *)malloc(sizeof(node));
      curr->left = curr->right = NULL;
      curr->val = rand();
      insert(&root, curr);
   }

   printout(root);
}

Почему используется указатель-указатель?

Answer 1

Поскольку метод вставки должен изменить корень дерева.

Answer 2

Белая доска это. Или измените пример кода, чтобы сделать это:

for(i=1;i<=10;i++) {
  curr = (node *)malloc(sizeof(node));
  curr->left = curr->right = NULL;
  curr->val = rand();
  printf("before: %d\n", root);
  insert(&root, curr);
  printf("after: %d\n", root);
}

// printout(root);

Напечатанный результат выглядит так:
до: 0
после: 3871888
до: 3871888
после: 3871888
до: 3871888
после: 3871888

Почему это?

Потому что он меняет указатель, который вы передаете ему.

Как работает вставка: Вставка пересекает дерево. Сначала он посещает текущий узел. Затем левый узел (через рекурсию). Затем правый узел (через рекурсию). Если речь идет о пустом узле (NULL), он заменяет этот узел элементом.

Для этого он разыменовывает внешний указатель и присваивает значение указателя «item» этому внутреннему указателю.

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

Вот еще пример кода указателя для пережевывания:

#include <cstdio>
#include <cstdlib>

void some_func(int* value)
{
  *value = 12;
}

int main(int argc, char* argv[])
{
  int a = 5;
  printf("%d\n", a); // prints 5
  some_func(&a);
  printf("%d\n", a); // prints 12

  int b = 7;
  int* c = &b;
  printf("%d\n", b); // prints 7
  printf("%d\n", c); // prints 2029440 (some random memory address)
  some_func(c);
  printf("%d\n", b); // prints 12
  printf("%d\n", c); // prints 2029440 (the same value as before)
}

И

#include <cstdio>
#include <cstdlib>

void some_other_func(int** other_value)
{
  *other_value = NULL;
}

int main(int argc, char* argv[])
{
  int b = 7;
  int* c = &b;

  printf("%d\n", c); // prints 4718288 (some random memory address)
  some_other_func(&c);
  printf("%d\n", c); // prints 0
}

Последнее, но не менее важное:

#include <cstdio>
#include <cstdlib>

void some_third_func(int* third_value)
{
  *third_value = 12;
  int** lets_modify_third_value = &third_value;
  *lets_modify_third_value = NULL;
}

int main(int argc, char* argv[])
{
  int b = 7;
  int* c = &b;

  printf("%d\n", b); // prints 7
  printf("%d\n", c); // prints 1637380 (some random memory address)
  some_third_func(c);
  printf("%d\n", b); // prints 12
  printf("%d\n", c); // prints 1637380 (same as before.  Note that the pointer was passed by value, so "third_value" was just a COPY of the address)
}

Answer 3

Альтернатива параметру 'in out' - возвращаемое значение, потребует дополнительного назначения на каждом посещаемом уровне:

typedef node* node_ref;

node_ref insert ( node_ref tree, node_ref item) {  
    if ( !tree )  
        return item;

    if ( item -> val < tree -> val ) 
        tree -> left = insert ( tree -> left, item );
    else  if ( item -> val > tree -> val )
        tree -> right = insert ( tree -> right, item );

    return tree;
}

...
// in the loop 
   root = insert ( root, curr );

Еще один недостаток этого подхода (или исходного кода) состоит в том, что невозможно определить, был ли вставлен узел; если вы добавите возвращаемое значение, чтобы указать его, вам не нужно пропускать curr, если оно не вставлено:

typedef node* node_ref;

bool insert ( node_ref *tree, node_ref item) {  
    if ( !*tree )  {
        *tree = item;
        return true;
    }

    if ( item -> val < ( *tree ) -> val ) 
        return insert ( & ( *tree ) -> left, item );

    if ( item -> val > ( *tree ) -> val )
        return insert ( & ( *tree ) -> right, item);

    return false;
}

...
// in the loop 
for ( int i = 1; i <= 10; ++i ) {
    node_ref curr = malloc ( sizeof ( node ) );

    curr -> left = curr -> right = NULL;
    curr -> val  = rand();

    if ( ! insert ( &root, curr ) )
        free ( curr );
}

Answer 4

более точный ответ будет: потому что функция должна заменить содержимое данного поля (указатель)