Атрибут указателя: обход дерева huffman

Question

Я запутался в арифметике указателя, я хочу сделать функцию обхода дерева, но я не совсем уверен в арифметике указателя, чтобы получить удаленные узлы в дереве. Это будет намного понятнее, если вы увидите в коде, так что вот оно.

node **root = huffman_tree(probabilities); // I can only return that as a double ptr 

Теперь, если я хочу данные от моего корневого узла:

printf("%lf", (*root)->data); 

Если я хочу данные из корней детей:

printf("%lf", (*root)->left->data); // or (*root)->right->data 

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

printf("%lf", (*root)->left->left->data); // thats not working 

Кроме того, для обхода дерева это не работает: программа вылетает.

node **root = huffman_tree(probabailities); 
preorder(*root); 

void preorder(node *n){ 
if(n == NULL) return; 
printf("%lf", n->data); 
preorder(n->left); 
preorder(n->right); 

}

Для приведенных выше примеров, программа падает.

Update 1:

Похоже huffman_tree() действительно возвращает дерево с поврежденными узлами, я должен делать выделение памяти для них неправильно.

Функция передается массив вероятностей, а затем получает шаги, как это следующим образом:

1) создает узлы с заданными вероятностями (п вероятностей -> п новых узлов) [хорошо работает]

2) находит два узла с самыми низкими вероятностями [работает отлично] 3) создает новый узел, который является родителем двух нижних вероятностей узлов

4) назначить новую вероятность узла, равную сумме это детские вероятности

5) повтор с шага 2) до тех пор, пока только один без родителей узел покинул

node **huffman_tree(double *probabs){ 


int num_of_nodes = NUM_OF_SYMBOLS; 
int num = NUM_OF_SYMBOLS; 

// 1) create nodes for given probabilities 
node *leafs = (node*) malloc(num_of_nodes*sizeof(node)); 
int i; 
for(i=0; i<num_of_nodes; i+=1){ 
    node *n = (node *) malloc(sizeof(node)); 
    n->probab = *(probabs + i); 
    n->symbol = *(SYMBOLS + i); 
    n->left = NULL; 
    n->right = NULL; 
    *(leafs+i) = *n; 
    //free(n); 
} 

node **root; 

while(num_of_nodes > 1){ 

    // 2) Find the two nodes with lowest probabilities 
    node *two_mins =(node *)malloc(2*sizeof(node)); 
    two_mins = find_two_mins(leafs, num_of_nodes); 
    node min_n1 = two_mins[0]; 
    node min_n2 = two_mins[1]; 


    // 3) Create a parent node with probability equals to sum of its children probabilities 
      // add a parent node to leafs 
    node *new_node = (node *) malloc(sizeof(node)); 
    new_node->probab = min_n1.probab + min_n2.probab; 
    new_node->left = &min_n1; 
    new_node->right = &min_n2; 

    leafs = add_node(leafs, new_node, num); 
    num += 1; 
    leafs = remove_node(leafs, &min_n1, num); 
    num -= 1; 
    leafs = remove_node(leafs, &min_n2, num); 
    num -= 1; 

    num_of_nodes -= 1; 

    root = &new_node; 
} 

return root; 

Function add_node() [кажется, работает нормально]

node *add_node(node *nodes, node *n, int num){ 
nodes = realloc(nodes, (num+1)*sizeof(node)); 
nodes[num] = *n; 
return nodes; 

Функция remove_node() [кажется, работает отлично]

node *remove_node(node *nodes, node *n, int num){ 
int i; 
int index = 0; 
for(i=0; i<num; i+=1){ 
    if(nodes_are_equal(nodes[i], *n)) index = i; 
} 

for(i=index; i<num-1; i+=1){ 
    nodes[i] = nodes[i+1]; 
} 

nodes = realloc(nodes, (num-1)*sizeof(node)); 

return nodes; 

Update 2

Я изменил некоторые вещи в функции huffman_tree().

Функция find_two_mins() больше не существует, но заменяется двумя вызовами другой функции find_min(), которая находит только один минимальный узел за раз. Кроме того, эта функция принимает указатель на динамически выделенный узел, а после того, как минимальное значение найдено, возвращает его обратно.

node *root; 

while(num_of_nodes > 1){ 

    // 2) Find two min nodes 
    node *min_n1= (node *)malloc(sizeof(node)); 
    node*min_n2= (node *)malloc(sizeof(node)); 

    *min_n1= *find_min(leafs, num, min_n1); 
    leafs = remove_node(leafs, min_n1, num); 
    num -= 1; 

    *min_n2= *find_min(leafs, num, min_n2); 
    leafs = remove_node(leafs, min_n2, num); 
    num -= 1; 

    printf("\nTwo Min Nodes: %lf\t%lf", min_n1->probab, min_n2->probab); 
    printf("\nSum Of All: %lf", s); 


    // 3) Create parent node of two min nodes 

    node *new_node = (node *) malloc(sizeof(node)); 
    new_node->probab= min_n1->probab+ min_n2->probab; 
    new_node->left = min_n1; 
    new_node->right = min_n2; 

    leafs = add_node(leafs, new_node, num); 
    num += 1; 

    free(min_n1); 
    free(min_n2); 

    num_of_nodes -= 1; 

    root = new_node; 

    printf("root=%p\n", root); 
    printf("*root=%p\n", *root); 
} 

return root; 

А вот функция find_min():

node *find_min(node *nodes, int num, node *min_node){ 

double min_probab = nodes[0].probab; 
*min_node= nodes[0]; 

int i; 
for(i=0; i<num; i+=1){ 
    if(nodes[i].probab< min_probab){ 
     min_probab = nodes[i].probab; 
     *min_node = nodes[i]; 
    } 
} 

return min_node; 

Похоже, что проблема что-то об этом выходе:

 printf("root=%p\n", root); 
    printf("*root=%p\n", *root); 

Поскольку он выводит "корень = 003A17F0" и "* root = 00000000"

Кроме того, я предоставляю скриншот о том, как работает программа, где значения корня в любом точка видна.

Answer 1

(*root)->left->left->data правильный способ доступа к внучатая дочерних узлов, до тех пор, пока ребенок не равно нулю, и предполагается, что ваш узел выглядит примерно так:

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

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

Собирает следующий сразу после проверки нуля в предзаказе должна сделать проблему более очевидной:

printf("processing node %p", n); fflush(stdout); 
printf(" left=%p\n", n->left); fflush(stdout); 
printf(" right=%p\n", n->right); fflush(stdout); 

Вы ищете указатели, которые не «выглядят как» другие, в частности, как раз перед он выходит из строя ,

Наиболее вероятные причины для проблем находятся внутри самого huffman_tree. Я подозреваю, что у вас есть что-то там, которое берет адрес узла из стека, а не динамически выделяет его с помощью malloc.

Редактировать на основе дополнительной информации, предоставленной в вашем «ответ»:

Ваша проблема, вероятно, в вашей find_two_mins функции. Следующий код

node *two_mins =(node *)malloc(2*sizeof(node)); 
two_mins = find_two_mins(leafs, num_of_nodes); 
node min_n1 = two_mins[0]; 
node min_n2 = two_mins[1]; 

является (правильно) динамическим распределением памяти для узлов, но тогда вы бросаете указатель на эту динамическую память прочь и заменить его с результатом find_two_mins.

У вас также есть другие утечки памяти вокруг того места, которое я думаю (хотя это не вызывает проблемы). В пределах начального цикла

node *n = (node *) malloc(sizeof(node)); 

, который не освобождается. Вы копируете эту структуру в правильно выделенный массив leafs, поэтому просто сделайте это node n;.

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