Блог

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

Моя древовидная структура:

 typedef struct Tree_node_ Tree_node;
typedef Tree_node* Tree;

struct Tree_node_
{
    int value;
    Tree left;
    Tree right;
};
 

Код переключения поддеревьев:

 void switch(Tree t) {
    Tree temp = malloc(sizeof(t));
    temp = t;
    t = t->left;
    temp->left = t->right;
    t->right = temp;
}
 

Ошибка возникает, когда я пытаюсь прочитать t->right

temp->left = t->right

Причина ошибки сегментации: здесь вы присваиваете t->left->right значение temp->left because t->right = t->left->right ( t = t->left ) .

Решение :
temp = t->left;
t->left = t->right;
t->right = temp

Нет необходимости в malloc temp . Фактически, выделение памяти temp приводит к утечке памяти, поскольку вы изменяете адрес, сохраненный в temp to t ( temp = t ) .
Я имею в виду, что вы потеряете указатель на malloc адрес ‘ed после выполнения temp = t . Это приведет к утечке памяти.
Valgrind выдаст вам определенно потерянную ошибку.

Давайте посмотрим:

 void switch(Tree t) {
    Tree temp = malloc(sizeof(t));
 

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

     temp = t;
 

Вы присваиваете temp указателю значение t . На этом этапе происходит утечка выделенной памяти, которая с malloc() этого момента не имеет привязки к ней.

     t = t->left;
 

Вы меняете значение t , чтобы указать на его левый дочерний элемент, но нет контекста, чтобы узнать t , существует ли левый дочерний элемент или нет (вероятно, это так NULL )

     temp->left = t->right;
 

теперь у вас есть два дочерних элемента исходного t узла, указывающих на один и тот же right дочерний элемент (в то время как исходный узел все еще указан temp )

     t->right = temp;
}
 

теперь t->right указывает на его родительский узел.

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

     Type temp = a;
    a = b;
    b = temp;
 

итак, для переключения дочерних элементов (независимо от того, что какой-либо из указателей равен null) вам нужно сделать:

 void switch(Tree t) {
    Tree temp = t->left;
    t->left = t->right;
    t->right = temp;
}
 

без malloc, без дополнительных временных переменных и т. Д. Даже если дочерние указатели являются NULL , этот код работает. Если вы также хотите проверить t , не является ли оно not null, то:

 #include <stdlib.h>  /* for EXIT_FAILURE */

void switch(Tree t) {
    if (t == NULL) {
        printf("Illegal parameter NULL passed to switch()");
        exit(EXIT_FAILURE);
    }
    Tree temp = t->left;
    t->left = t->right;
    t->right = temp;
}