二叉树实现异常：Print函数中根节点子节点丢失问题排查

问题描述 #

将二叉树的root传入Print函数时，其左右子节点均为Null；但调试for (size_t i = 0; i < tree.GetTreeDepth(); ++i)代码段时，能看到root存在子节点，传入Print函数后子节点却消失，仅保留根节点值。

代码问题分析 #

核心问题出在BinaryTree构造函数中root_的初始化错误：

BinaryTree()
    : root_()
    , tree_depth_(Type())
{}

对于指针类型Node<Type>* root_，root_()是默认初始化，不会将其设置为nullptr，而是生成一个野指针。这会导致：

• 第一次调用tree.Push(tree.GetRoot(), ...)时，Push函数的if (root == nullptr)条件不成立（野指针不等于nullptr），程序错误进入后续分支，操作野指针的value、lhs、rhs，触发未定义行为。
• 后续插入的节点无法正确挂载到根节点上，最终导致Print函数遍历到的树只有根节点（甚至可能引发更严重的内存问题）。

此外还有两个次要问题：

• tree_depth_的类型定义为Type不合理，树的深度是整数类型，和节点值类型无关，建议改为int或size_t。
• Push函数未处理new_value == root->value的情况，重复值会被直接忽略，若需要支持重复值，需补充对应逻辑。

修复方案 #

1. 修正构造函数的root_初始化 #

将BinaryTree的构造函数改为：

BinaryTree()
    : root_(nullptr)
    , tree_depth_(0)
{}

确保root_初始化为合法空指针，让Push函数的初始插入逻辑正常执行。

2. 优化tree_depth_的类型 #

将BinaryTree中的Type tree_depth_;改为整数类型，避免节点值类型影响树深度存储：

template <typename Type>
struct BinaryTree {
private:
    Node<Type>* root_;
    int tree_depth_; // 替换原Type类型
    // ... 其他代码
};

3. 可选：处理重复值插入（若业务需要） #

修改Push函数，补充重复值的处理逻辑，比如将重复值挂载到右子树：

Node<Type>* Push(Node<Type>* root, Type new_value) {
    if (root == nullptr) {
        return new Node<Type>(new_value);
    }
    else if (new_value < root->value) {
        root->lhs = Push(root->lhs, new_value);
    }
    else { // 包含等于的情况
        root->rhs = Push(root->rhs, new_value);
    }
    return root;
}

修复后验证 #

修正后，main函数中的循环会正确将随机值插入二叉树，Print函数可以正常遍历所有节点，不会出现子节点消失的情况。

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