二叉搜索树非递归insert函数问题：插入时重复创建根节点

我来帮你搞定这个非递归二叉搜索树（BST）的实现问题！你遇到的重复创建根节点的问题，核心原因几乎都是没处理好第一次插入时根节点为空的特殊场景。下面是完整的可运行实现，包含你需要的三个成员函数，我会重点解释Insert的逻辑：

#include <vector>
#include <stack>

class BST {
private:
    // 定义二叉树节点结构体
    struct Node {
        double val;
        Node* left;
        Node* right;
        Node(double x) : val(x), left(nullptr), right(nullptr) {}
    };

    Node* root;

public:
    BST() : root(nullptr) {}

    // 非递归Insert函数
    void insert(double x) {
        // 特殊情况：树为空，直接创建根节点
        if (root == nullptr) {
            root = new Node(x);
            return;
        }

        // 树不为空，遍历找插入位置
        Node* current = root;
        Node* parent = nullptr;

        while (current != nullptr) {
            parent = current;
            if (x < current->val) {
                current = current->left;
            } else if (x > current->val) {
                current = current->right;
            } else {
                // 处理重复值：这里假设BST不存储重复元素，直接返回
                return;
            }
        }

        // 找到插入位置，创建新节点挂到父节点对应位置
        if (x < parent->val) {
            parent->left = new Node(x);
        } else {
            parent->right = new Node(x);
        }
    }

    // 非递归Search函数
    bool search(double x) {
        Node* current = root;
        while (current != nullptr) {
            if (x == current->val) {
                return true;
            } else if (x < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }
        return false;
    }

    // 非递归中序遍历（升序输出BST元素）
    void inorder(vector<double>& v) {
        v.clear(); // 先清空传入的vector
        stack<Node*> s;
        Node* current = root;

        while (current != nullptr || !s.empty()) {
            // 遍历到最左子节点
            while (current != nullptr) {
                s.push(current);
                current = current->left;
            }

            current = s.top();
            s.pop();
            v.push_back(current->val);

            // 处理右子树
            current = current->right;
        }
    }
};

关键细节解释 #

1. Insert函数的核心修复：

   • 开头先判断root == nullptr，这时候直接创建根节点并返回，避免进入后续遍历逻辑，从根源解决重复创建根的问题。
   • 遍历过程中用parent指针跟踪当前节点的父节点，这样找到空位置时，能准确把新节点挂到父节点的左/右子树，而不是重新修改根节点。
   • 额外处理了重复值的情况（如果需要存储重复值，可以把else分支改成插入到右子树或者左子树，根据你的需求调整）。

2. Search函数逻辑：

   • 从根节点开始遍历，根据目标值和当前节点值的大小关系，选择左/右子树继续查找，直到找到目标或遍历到空节点。

3. Inorder遍历的非递归实现：

   • 用栈模拟递归调用栈，先遍历到最左节点，然后弹出节点记录值，再处理右子树，这样就能得到BST的升序序列（符合BST的中序遍历特性）。

如果你之前的代码没有判断root == nullptr的情况，每次插入都会尝试创建新节点覆盖根，或者错误地在遍历中重新初始化根，现在这个实现应该能完美解决你的问题。

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