Для каждого отца только узла листа, удалите лист и добавьте его значение с отцом - PullRequest
Новая
       15

Для каждого отца только узла листа, удалите лист и добавьте его значение с отцом

0 голосов
/ 01 июня 2019

Если я нахожу отца, у которого в детстве только лист, мне нужно убрать этот лист и добавить его значение вместе с отцом

Это мое решение, но у меня проблема при попытке удалить лист 

bool isLeaf(tree a){ //function to verify if the node is a leaf

if(a->left==NULL && a->right==NULL)
    return true;
else
    return false;
}


void removeLeaves(tree* a){

if(*a == NULL) return;

//verify if the node has only a child
 if(((*a)->left==NULL&&(*a)->right!=NULL) || ((*a)->right==NULL&&(*a)->left!=NULL)){

    if((*a)->right==NULL){ //if has only left child,verify  if it is a leaf
        if(isLeaf((*a)->left)){
            (*a)->info = (*a)->info + (*a)->left->info; 
            free((*a)->left);



        }
    }
    if((*a)->left==NULL){ //if has only right child,verify  if it is a leaf
        if(isLeaf((*a)->right)){
            (*a)->info = (*a)->info + (*a)->right->info; 
            free((*a)->right);

        }
    }
}


removeLeaves(&((*a)->left));
removeLeaves(&((*a)->right));
}

Минимальные: 

if((*a)->right==NULL){ //if has only left child,verify  if it is a leaf
        if(isLeaf((*a)->left)){
            (*a)->info = (*a)->info + (*a)->left->info; 
            free((*a)->left);

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

Edit1: Я изменил условие на: 

if(((*a)->right==NULL&&(*a)->left!=NULL) && isLeaf((*a)->left)){


        (*a)->info = (*a)->info + (*a)->left->info; 

        free((*a)->left);
        (*a)->left = NULL;  

}

И это работает, но я не понимаю, почему.

Edit2: (реализация со структурой) 

    #include <stdio.h>
#include <cstdlib>


typedef int InfoTree;

typedef struct StructTree {
  InfoTree info;
  struct StructTree* right;
  struct StructTree* left;
} NodeTree;

typedef NodeTree* Tree;

//functions
Tree createTree(InfoTree infoRoot,Tree left,Tree right);
Tree emptyTree();
void print_tree(Tree a);
bool isLeaf(Tree a);
void removeLeaves(Tree* a);

int main(){

    /* Binary Tree:                */
    /*          3               */
    /*       /     \           */
    /*      7       5          */
    /*    /   \      \         */
    /*   4    2       9        */
    /*       /                     */
    /*      6                      */

    Tree A = createTree( 6  , emptyTree(), emptyTree() ) ;
    Tree B = createTree( 2 , emptyTree(), emptyTree() ) ;
    Tree C = createTree( 9 , emptyTree(), emptyTree() ) ;

    Tree D = createTree( 5 , emptyTree(), C);
    Tree E = createTree( 4  , A, emptyTree());

    Tree F = createTree( 7 , E, B);

    Tree H = createTree( 3  , F, D);
    Tree t = H;
    print_tree(t);
    removeLeaves(&t);
    printf("\n");
    print_tree(t);
    return 0;



}

Tree createTree(InfoTree infoRoot,
              Tree left,
              Tree right) {
  Tree a = (Tree) malloc(sizeof(Tree));
  a->info = infoRoot;
  a->left = left;
  a->right = right;
  return a;
}

Tree emptyTree() {
  return NULL;
}


void print_tree(Tree a) {
    if (a==NULL) {
        printf("()");
    }
    else {
        printf("( %d ",a->info);
        print_tree(a->left);
        printf(" ");
        print_tree(a->right);
        printf(" )");
    }
}

bool isLeaf(Tree a){ //function to verify if the node is a leaf

if(a->left==NULL && a->right==NULL)
    return true;
else
    return false;
}


void removeLeaves(Tree* a){

if(*a == NULL) return;

//verify if the node has only a child
 if(((*a)->left==NULL&&(*a)->right!=NULL) || ((*a)->right==NULL&&(*a)->left!=NULL)){

    if((*a)->right==NULL){ //if has only left child,verify  if it is a leaf
        if(isLeaf((*a)->left)){
            (*a)->info = (*a)->info + (*a)->left->info; 
            free((*a)->left);
        (*a)->left = NULL;



        }
    }
    if((*a)->left==NULL){ //if has only right child,verify  if it is a leaf
        if(isLeaf((*a)->right)){
            (*a)->info = (*a)->info + (*a)->right->info; 
            free((*a)->right);
            (*a)->right = NULL;

        }
    }
}


removeLeaves(&((*a)->left));
removeLeaves(&((*a)->right));
}

Это оригинальный исходный код с древовидной структурой и функциями для работы с деревом. Если я изменяю это с вышеупомянутыми условиями (сначала Edit1), это работает, но я не понимаю почему. Спасибо

1 Ответ

0 голосов
/ 02 июня 2019

После освобождения листа вам нужно установить его запись в отце на ноль.

Ваша функция рекурсивная.Если он находит один лист, его память освобождается, но в конце функции он пытается получить доступ к этой памяти.Это называется «висячий указатель».

Редактировать:

Существует еще одна проблема, указанная здесь у вашего исходного источника: 

if((*a)->right==NULL){
    if(isLeaf((*a)->left)){
        // ... irrelevant lines removed ...
        (*a)->left = NULL;
    }
}
if((*a)->left==NULL){ // <== see text below
    if(isLeaf((*a)->right)){ // BOOM!

Если в первой части найден лист, то указатель right равен NULL.После установки указателя left на NULL отмеченный if оценивается как true, и isLeaf() вызывается с указателем NULL, указывающим на ошибку сегментации.

...