C++递归实现完全二叉树插入时节点无法插入问题排查

现有代码的核心问题 #

• 编译级错误
  代码中直接调用f_height、countNumNodes两个函数，但未做类内声明与功能实现；插入函数内直接使用的height变量无定义，无法通过编译流程。
• 插入分支逻辑冗余错位
  代码重复编写两次excepted_node != left_tree_node_count的判断条件，分支顺序颠倒、覆盖逻辑冲突：正确的判断路径被重复分支打断，导致递归走向完全偏离完全二叉树的层序插入规则。
• 空指针访问风险
  递归调用插入函数时，直接传入空的子节点指针作为参数，函数分支中会尝试访问空指针的left/right成员，直接触发程序崩溃。
• 插入位置判断逻辑残缺
  完全二叉树的插入需严格按照层序从左到右的顺序，遍历到第一个空节点位置完成挂载；现有代码未在递归前判断当前节点的左右孩子是否为空，仅靠子树高度与节点数计算判断递归路径，导致新节点无法正确挂载到父节点上。

修正后的核心逻辑 #

1. 补全树高计算、子树节点数统计两个工具函数的实现：
   • 树高计算：空节点返回0，非空节点的高度为左右子树高度的最大值加1。
   • 节点数统计：空节点返回0，非空节点的节点数为1（当前节点）加左右子树节点数之和。
2. 调整插入函数的判断顺序：
   • 若根节点为空，直接将新节点设为根后返回。
   • 进入当前节点后，优先判断左右孩子是否为空，按照先左后右的顺序优先挂载空位置，仅在确定挂载时才创建新节点，避免内存泄漏。
   • 若左右孩子均非空，对比左右子树的节点数决定递归路径：左右子树节点数相等时，递归进入左子树寻找插入位置；左子树节点数比右子树多1时，递归进入右子树寻找插入位置。
3. 移除冗余重复的判断分支，避免逻辑冲突。

可运行的修正代码 #

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int data;
    node *left,*right;
};
class cbt{
node *root;
// 树高计算
int f_height(node* temp) {
    if(temp == NULL) return 0;
    int l = f_height(temp->left);
    int r = f_height(temp->right);
    return max(l, r) + 1;
}
// 子树节点数统计
int countNumNodes(node* temp) {
    if(temp == NULL) return 0;
    return 1 + countNumNodes(temp->left) + countNumNodes(temp->right);
}
public:
cbt() {
    root=NULL;
}
node* get_node() {
    return root;
}
node* newNode(int key) {
    node* temp1 = new node;
    temp1->data = key;
    temp1->left = temp1->right = NULL;
    return temp1;
}
void CBT_inseration(node* temp,int data) {
    // 根节点为空，直接挂载
    if(root == NULL) {
        root = newNode(data);
        return;
    }
    // 空节点不做访问，避免崩溃
    if(temp == NULL) return;
    // 优先挂载左空位置
    if(temp->left == NULL) {
        temp->left = newNode(data);
        return;
    }
    // 再挂载右空位置
    if(temp->right == NULL) {
        temp->right = newNode(data);
        return;
    }
    // 左右都非空，判断递归路径
    int left_cnt = countNumNodes(temp->left);
    int right_cnt = countNumNodes(temp->right);
    if(left_cnt == right_cnt) {
        CBT_inseration(temp->left, data);
    } else {
        CBT_inseration(temp->right, data);
    }
}
// 中序遍历
void print(node *root) {
    if (root == NULL)
        return;
    print(root->left);
    cout << root->data << " ";
    print(root->right);
}
};
int main()
{
cbt obj;
obj.CBT_inseration(obj.get_node(),4);
obj.CBT_inseration(obj.get_node(),3);
obj.CBT_inseration(obj.get_node(),5);
obj.CBT_inseration(obj.get_node(),8);
obj.print(obj.get_node());
return 0;
}

内容的提问来源于stack exchange，提问作者john