对于只有一个叶节点的每个父亲，删除叶子并将其值与父亲相加

Question

如果我找到只有一片叶子的父亲 child 我必须移除叶子并将其值与父亲相加

这是我的解决方案，但我在尝试移除叶子时遇到问题

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);

如果我到达这一点（左边只有一个child，它是一片叶子），我将它的值与父亲相加然后释放它。没有免费我得到总和但免费我得到分段错误。同样的事情，右边只有一个 child。

编辑1：我将条件更改为：

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）修改它，它可以工作，但我不明白为什么。谢谢

Answer 1

释放叶节点后，您需要将其在父节点中的条目设置为空。

你的函数是递归的。如果它找到一个叶子，它的内存就会被释放，但在函数结束时它会尝试访问该内存。这被称为 "dangling pointer."

编辑：

还有另一个问题，此处显示在您的初始来源中：

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，并使用 NULL 指针调用 isLeaf()，从而给出分段错误。

对于只有一个叶节点的每个父亲，删除叶子并将其值与父亲相加

For every father of only a leaf node, remove the leaf and add its value with the father

c

recursion

binary-tree