c - BST 二叉树删除 C 中值 = 0 的叶子的函数

Question

我正在尝试在 C 中创建一个函数，该函数应该能够从二叉树 (BST) 中移除(删除)所有叶子，该树作为参数传递，具有零值 (0) 并且返回结果将是删除的叶子的数量。注意:不是 value = 0 的节点，而是只有叶子。以图中的BST为例:

该函数将返回 2(在删除红色圆圈零之后)。

Answer 1

这是一个伪代码:

int delete_zero_leaves (node){
    int deleted
    delete_zero_leaves_aux (node, &deleted);
    return deleted
}

pointer delete_zero_leaves_aux (node, deleted){
    boolean is_leaf = true
    // if there is a child
    if (node->left != NULL){
            // passing deleted by reference
            node->left = delete_zero_leaves_aux (node->left, &deleted)
            is_leaf = false
    }
    // if there is a child on the right side
    if (node->right != NULL){
            // passing deleted by reference
            node->right = delete_zero_leaves_aux (node->right, &deleted)
            is_leaf = false
    }
    if (is_leaf AND node->value == 0){
        free(node)
        deleted += 1
        return NULL
    }
    return node
}

既然你说节点没有指向它自己父亲的指针，你可以返回一个指针并设置父亲指针的值(左或右)。