C++二叉搜索树遍历异常求助：根节点缺失、遍历结果不全

1. 迭代器核心逻辑错误（中序遍历缺失根节点） #

Java与C的迭代器语义差异很大，Java的Iterator依赖hasNext()判断，而C迭代器要求begin()指向首个元素、end()指向尾元素的下一个位置。如果你的中序迭代器初始化时只压入根节点的左子树，未处理根节点本身，就会直接跳过根节点5。

正确的中序迭代器实现逻辑：

class InOrderIterator {
private:
    stack<TreeNode*> stk;
    TreeNode* current;
public:
    // 构造函数：初始化时压入所有左子节点（包括根）
    InOrderIterator(TreeNode* root) : current(root) {
        while (current != nullptr) {
            stk.push(current);
            current = current->left;
        }
    }

    // 空迭代器构造（用于end()）
    InOrderIterator() : current(nullptr) {}

    TreeNode* operator*() {
        return stk.top();
    }

    // 重载++运算符，处理右子树
    InOrderIterator& operator++() {
        current = stk.top();
        stk.pop();
        TreeNode* temp = current->right;
        while (temp != nullptr) {
            stk.push(temp);
            temp = temp->left;
        }
        current = nullptr; // 重置current，避免重复处理
        return *this;
    }

    // 重载!=，比较迭代器终止状态
    bool operator!=(const InOrderIterator& other) const {
        return !stk.empty() != !other.stk.empty();
    }
};

关键：初始化时必须将根节点的所有左子节点（含根）压栈，++运算符处理完当前节点后，要将右子树的左节点全部压栈，确保根节点会被弹出访问。

2. 根节点全局缺失的修复 #

如果所有遍历都找不到根节点5，先检查插入逻辑：

void insert(int val) {
    if (root == nullptr) {
        root = new TreeNode(val);
        return;
    }
    TreeNode* curr = root;
    while (true) {
        if (val < curr->val) {
            if (!curr->left) {
                curr->left = new TreeNode(val);
                break;
            }
            curr = curr->left;
        } else if (val > curr->val) {
            if (!curr->right) {
                curr->right = new TreeNode(val);
                break;
            }
            curr = curr->right;
        } else {
            // 重复值直接返回，避免覆盖根节点
            return;
        }
    }
}

确认插入5时，root被正确赋值为新节点，没有被后续插入操作意外覆盖。

3. 前序遍历无输出的修复 #

前序迭代器的压栈顺序是核心：前序为根-左-右，栈是后进先出结构，所以要先压右子节点，再压左子节点。错误的压栈顺序会导致遍历无输出：

class PreOrderIterator {
private:
    stack<TreeNode*> stk;
public:
    PreOrderIterator(TreeNode* root) {
        if (root) stk.push(root);
    }

    PreOrderIterator() {}

    TreeNode* operator*() {
        return stk.top();
    }

    PreOrderIterator& operator++() {
        TreeNode* curr = stk.top();
        stk.pop();
        // 先压右，再压左，保证左子节点先被访问
        if (curr->right) stk.push(curr->right);
        if (curr->left) stk.push(curr->left);
        return *this;
    }

    bool operator!=(const PreOrderIterator& other) const {
        return !stk.empty() != !other.stk.empty();
    }
};

如果初始化时没压入根节点，或者压栈顺序搞反，直接会导致前序遍历无输出。

4. Iterator的end()与!=运算符报错修复 #

C++迭代器是对象，不能直接返回nullptr作为end()标记，否则会出现类型不匹配或死循环。正确做法是：

• 为迭代器添加空构造函数，用于生成end()的终止迭代器
• 重载!=时，比较两个迭代器的内部状态（栈是否为空）

在BST类中定义begin()和end()：

InOrderIterator begin() {
    return InOrderIterator(root);
}

InOrderIterator end() {
    return InOrderIterator(); // 返回空迭代器作为终止标记
}

如果直接让迭代器和nullptr比较，会因为类型不匹配报错，必须通过重载operator!=来实现终止条件判断。

5. 遍历停滞问题修复 #

修改end()为nullptr后停滞，是因为迭代器的++逻辑无法到达终止条件，导致死循环。检查operator++或next()逻辑：确保当栈为空时，迭代器的!= end()返回false，终止遍历。

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