指针实现的二叉堆递归查找插入节点位置的算法优化问题
原有代码核心问题
- 第一版代码的else分支中,左子树处理逻辑结束后直接执行了return,右子树的查找代码是死代码永远不会执行,这就是你最初堆的右侧完全为空、高度无法超过两层的根本原因。
- 第二版实现存在三个问题:
function_a递归调用左右子节点时没有捕获返回值,找到的有效父节点无法向上传递,函数最终只会返回初始的空指针function_b没有做空指针校验,访问a->L、b->R这类成员前没有判断a、b是否为空,树高超过4层后访问空节点成员会直接触发段错误- 硬编码检查3层孙节点的逻辑没有通用性,树高超过限制后就会失效
优化方案
因为二叉堆是完全二叉树,插入位置一定是层序遍历的第一个空位,我们可以利用完全二叉树的结构特性实现通用递归查找:
思路
- 递归过程中先判断当前节点是否存在空子节点,存在则直接返回当前节点作为插入父节点
- 若当前节点左右子节点都存在,分别计算左右子树的高度:
- 左子树高度大于右子树:说明左子树还存在空位,递归到左子树查找
- 左右子树高度相等:说明左子树已经全满,空位在右子树,递归到右子树查找
代码实现
首先实现子树高度计算辅助函数:
template<typename T> int heap<T>::get_height(node<T> *x) { if (x == nullptr) return 0; int left_h = get_height(x->left); int right_h = get_height(x->right); return 1 + max(left_h, right_h); }
然后实现查找插入父节点的主函数:
template<typename T> node<T> * heap<T>::find_insert_pos(node<T> *x) { // 终止条件:当前节点有空子节点,直接作为父节点返回 if (x->left == nullptr) return x; if (x->right == nullptr) return x; int left_h = get_height(x->left); int right_h = get_height(x->right); if (left_h > right_h) { return find_insert_pos(x->left); } else { return find_insert_pos(x->right); } }
该实现没有层数限制,所有节点访问前都做了空判断,不会触发段错误,完全符合完全二叉堆的插入规则。
若要保留原有的遍历思路,只需修改两个点即可:
- 递归调用子节点时捕获返回值,找到有效结果就向上传递
- 所有访问节点成员的位置先判断节点不为空
修改后的示例代码:
node * function_a (node *x, int &res) { if (x == ptr_null) return ptr_null; // 先检查当前节点是否符合父节点要求 int state = function_c(x, res); if (state != 2) return x; // 优先查左子树 node *left_res = function_a(x->L, res); if (left_res != ptr_null) return left_res; // 左子树无空位再查右子树 return function_a(x->R, res); } int & function_c (node *x, int &res) { if (x == ptr_null) return res = -1; if(x->L == ptr_null && x->R == ptr_null) return res = 0; else if(x->L != ptr_null && x->R == ptr_null) return res = 1; else return res = 2; }
内容的提问来源于stack exchange,提问作者jfo420
相关产品推荐
相关产品推荐

