C++二叉树迭代器适配int正常，适配std::string时崩溃

核心错误点 #

1. data()函数的未定义行为 #

你的data()函数在data_node为空时没有返回值，触发未定义行为。更严重的是，iterator::operator*()返回const T&，但data()返回的是值拷贝，这会导致引用绑定到临时对象，临时对象在表达式结束后销毁，进而产生悬空引用——对于std::string这种需要内存管理的类型，直接引发段错误。

2. 迭代器拷贝构造函数的根节点初始化错误 #

迭代器的拷贝构造函数中，root被错误初始化为tree_iterator.current，而非原迭代器的root。这会导致遍历过程中root指向当前节点而非整棵树的根，完全破坏中序遍历逻辑。

3. 冗余调试输出干扰逻辑 #

left()和right()函数中的std::cout调试输出会干扰正常执行流，且无保留必要。

修复后的完整代码 #

#include <iostream>
#include <memory>
#include <iterator>
#include <string>
#include <stdexcept>

namespace binary_search_tree {

    template <typename T>
    struct binary_tree {
        std::unique_ptr<T> data_node;
        binary_tree<T>* parent = nullptr;
        std::unique_ptr<binary_tree<T>> left_node;
        std::unique_ptr<binary_tree<T>> right_node;

        std::unique_ptr<binary_tree<T>>& left() {
            return left_node;
        }

        std::unique_ptr<binary_tree<T>>& right() {
            return right_node;
        }

        // 返回引用而非值，避免临时对象
        const T& data() const {
            if (!this || !this->data_node) {
                throw std::logic_error("Data node is null");
            }
            return *this->data_node;
        }

        void insert(const T& data) {
            if (!this->data_node) {
                this->data_node = std::make_unique<T>(data);
            }
            else {
                if (data > *this->data_node) {
                    if (!this->right_node) {
                        this->right_node = std::make_unique<binary_tree<T>>(this);
                    }
                    this->right_node->insert(data);
                }
                else {
                    if (!this->left_node) {
                        this->left_node = std::make_unique<binary_tree<T>>(this);
                    }
                    this->left_node->insert(data);
                }
            }
        }

        binary_tree(T data) {
            this->insert(std::move(data));
        }

        binary_tree() = default;

        explicit binary_tree(binary_tree<T>* parent_ptr) : parent(parent_ptr) {}

        struct iterator {
            using iterator_category = std::forward_iterator_tag;
            using value_type = T;
            using difference_type = std::ptrdiff_t;
            using pointer = const T*;
            using reference = const T&;

            binary_tree<T>* current;
            binary_tree<T>* root;

            bool operator==(const iterator& other) const {
                return current == other.current;
            }
            bool operator!=(const iterator& other) const {
                return !(*this == other);
            }

            iterator& operator++() {
                if (!current) {
                    return *this;
                }

                // 标准中序后继查找逻辑
                if (current->right_node) {
                    // 右子树的最左节点
                    current = findStartLeftLeaf(current->right_node.get());
                }
                else {
                    // 向上找第一个当前节点是左子节点的父节点
                    binary_tree<T>* p = current->parent;
                    while (p && current == p->right_node.get()) {
                        current = p;
                        p = p->parent;
                    }
                    current = p;
                }
                return *this;
            }

            reference operator*() const {
                if (!current) {
                    throw std::out_of_range("Dereferencing end iterator");
                }
                return current->data();
            }

            pointer operator->() const {
                return &(**this);
            }

            iterator() : current(nullptr), root(nullptr) {}
            explicit iterator(binary_tree<T>* tree_pointer) : current(tree_pointer), root(nullptr) {
                if (tree_pointer) {
                    root = findRoot(tree_pointer);
                }
            }
            // 正确拷贝根节点
            iterator(const iterator& other) : current(other.current), root(other.root) {}
            iterator& operator=(const iterator& other) = default;
        };

        iterator begin() {
            return iterator(findStartLeftLeaf(this));
        }
        iterator end() {
            return iterator(nullptr);
        }

        const iterator begin() const {
            return iterator(findStartLeftLeaf(const_cast<binary_tree<T>*>(this)));
        }
        const iterator end() const {
            return iterator(nullptr);
        }

        static binary_tree<T>* findStartLeftLeaf(binary_tree<T>* node) {
            while (node && node->left_node) {
                node = node->left_node.get();
            }
            return node;
        }
        static binary_tree<T>* findRoot(binary_tree<T>* node) {
            while (node && node->parent) {
                node = node->parent;
            }
            return node;
        }
    };

}

using namespace binary_search_tree;

int main()
{
    // 测试int类型
    binary_tree<int> tree_int(2);
    tree_int.insert(3);
    tree_int.insert(1);
    tree_int.insert(7);
    tree_int.insert(0);
    tree_int.insert(1);
    tree_int.insert(1);

    std::cout << "Tree elements (int):\n";
    for (const auto& value : tree_int) {
        std::cout << "value:\t" << value << "\n";
    }

    // 测试std::string类型
    binary_tree<std::string> tree_str("hi");
    tree_str.insert("2");
    tree_str.insert("6");
    tree_str.insert("apple");
    tree_str.insert("zoo");

    std::cout << "\nTree elements (string):\n";
    for (const auto& value : tree_str) {
        std::cout << "value:\t" << value << "\n";
    }

    return 0;
}

关键修复说明 #

1. 修正data()函数：

   • 返回类型改为const T&，避免值拷贝，确保返回有效引用。
   • 添加空指针检查，抛出明确异常替代未定义行为。

2. 修复迭代器逻辑：

   • 拷贝构造函数中正确拷贝root指针，保证遍历始终指向整棵树的根。
   • 简化operator++()逻辑，使用标准中序后继查找逻辑，更可靠清晰。
   • 为迭代器添加STL标准迭代器类型别名，符合规范要求。

3. 优化插入函数：

   • 参数改为const T&，避免不必要的拷贝。
   • 移除冗余调试输出，消除执行干扰。

4. 添加const版本迭代器接口：

   • 实现const begin()和const end()，支持对const二叉树的遍历。

运行修复后的代码，std::string类型的二叉树可正常遍历，不会出现段错误。

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