我试图在C中创建一个函数,该函数应该能够从二叉树(BST)中删除(删除)所有叶子,该二叉树是作为参数传递的,其值为0,返回的结果将是删除的叶数。注意:不是值=0的节点,而是叶。例如,图上的BST:
该函数将返回2(在移除红色圆圈零之后)。
发布于 2014-12-07 14:45:30
这是一个伪代码:
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
}
由于您说节点没有它自己的父节点指针,所以您可以返回一个指针并设置父指针的值(左或右)。
https://stackoverflow.com/questions/27348482
复制