Создание BINARY SEARCH TREE

Question

Я написал простой код для создания и вставки элементов в двоичное дерево поиска, когда я пишу код следующим образом, цепочка, похоже, не происходит, может кто-нибудь помочь мне понять, что именно происходит в функции вставки? Я знаю код для вставки элементов в двоичное дерево поиска, просто любопытно узнать, почему этот не работает.

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

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



void insert(struct node *node,int x) 
{ 
    if(node==NULL) 
    {node=(struct node *)malloc(sizeof(struct node)); 
    node->element=x; 
    node->left=NULL; 
    node->right=NULL;} 

    else 
    {if(x<node->element) 
     {insert(node->left,x);} 
    else 
     {insert(node->right,x);} 
    } 
} 
void inorder(struct node *base) 
{ 
    if(base!=NULL) 
    {inorder(base->left); 
    printf("%d ",base->element); 
    inorder(base->right); 
    } 
} 


int main(int argc, char *argv[]) 
{struct node *base; 
base=(struct node *)malloc(sizeof(struct node)); 
base->element=1; 
base->left=NULL; 
base->right=NULL; 
insert(base,25); 
insert(base,30); 
inorder(base); 



    return 0; 
} 

если функция вставки написана таким образом, он работает, но до сих пор не работает для создания первого узла бинарного дерева поиска, беспорядочный/

void insert2(struct node *node,int x) 
{ 
    if(node==NULL) 
    {node=(struct node *)malloc(sizeof(struct node)); 
    node->element=x; 
    node->left=NULL; 
    node->right=NULL;} 

    else 
    {if(x<node->element) 
     {if(node->left==NULL) 
      {node->left=(struct node *)malloc(sizeof(struct node)); 
      node->left->element=x; 
      node->left->left=NULL; 
      node->left->right=NULL;} 
     else 
      {insert2(node->left,x);} 
     } 
    else 
     { 
     if(node->right==NULL) 
      {node->right=(struct node *)malloc(sizeof(struct node)); 
      node->right->element=x; 
      node->right->left=NULL; 
      node->right->right=NULL;} 
     else 
      {insert2(node->right,x);} 
     } 
    } 
} 

Answer 1

Когда вы передаете значение функции в C, вы используете значение pass-by-value. Это означает, что значение копируется в другую переменную, которая становится локальной для функции.

void change(struct node *n) { 
    n = 42; 
} 

int main(void) { 
    change(NULL); // change can't change the value of NULL, can it? 
} 

Теперь посмотрим на вашу insert функцию ... Предположим, что я называю insert(NULL,42);, вы думаете, insert пытается изменить NULL? Или он пытается изменить некоторую локальную переменную, которую ваша функция main не может видеть?

Вы знаете, что должно быть сделано уже ... Либо сделать вашу insert функции использовать дополнительный уровень указателя косвенности как вы предложили в комментариях, или вернуть корневой узел из insert, так что вы можете распространять изменения сделанный insert в структуру данных, хранящуюся в main (с использованием задания = оператора).

Answer 2

C является пропускной стоимостью. Когда вы передаете что-то в параметр функции, функция делает ее копию. Поэтому, когда вы передаете struct node pointer в функцию insert, C делает копию этого указателя.

Что вы делали в main сначала вы сделали struct node* base:

base --> struct node.

Когда вы звоните insert(base, 25), C делает копию базы. Так что теперь в вашей памяти у вас есть что-то вроде этого:

basecpy ---> [struct node] <--- base 

Так в вашем insert, вы, по сути делает

if(basecpy==NULL) 
    {basecpy=(struct node *)malloc(sizeof(struct node)); 
    basecpy->element=x; 
    basecpy->left=NULL; 
    basecpy->right=NULL;} 

Который не меняет base в любом случае на всех - это просто меняет basecpy.

Это может быть решена с помощью двойных указателей:

void insert(struct node **node, int x) { 
    if (*node == NULL) { 
     *node = malloc(sizeof(*node)); 
     (*node)->element=x; 
     (*node)->left=NULL; 
     (*node)->right=NULL; 
    } else { 
     if (x < (*node)->element) { 
      insert(&((*node)->left), x); 
     } else { 
      insert(&((*node)->right), x); 
     } 
    } 
} 

И затем использовать его, передать в адрес базы.

insert(&base, 25); 

Указатели может быть сложно :)

ideone