求助：实现二叉搜索树的非递归insert()函数及相关成员函数

Got it, let's tackle this non-recursive BST insert problem! I've put together a complete C++ implementation of a binary search tree that meets all your requirements, with clear breakdowns of each function:

#include <vector>
#include <stack>

// Node structure for the BST
struct TreeNode {
    double val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(double x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
private:
    TreeNode* root;

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

    // Non-recursive insert function
    void insert(double x) {
        TreeNode* newNode = new TreeNode(x);
        
        // If tree is empty, new node becomes root
        if (root == nullptr) {
            root = newNode;
            return;
        }

        TreeNode* current = root;
        TreeNode* parent = nullptr;

        // Traverse to find the correct insertion spot
        while (current != nullptr) {
            parent = current;
            if (x < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        // Attach the new node to the parent
        if (x < parent->val) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }
    }

    // Non-recursive search function
    bool search(double x) {
        TreeNode* current = root;
        while (current != nullptr) {
            if (current->val == x) {
                return true;
            } else if (x < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }
        return false;
    }

    // Non-recursive inorder traversal to fill the vector
    void inorder(std::vector<double>& v) {
        v.clear(); // Clear the vector before filling
        std::stack<TreeNode*> nodeStack;
        TreeNode* current = root;

        while (current != nullptr || !nodeStack.empty()) {
            // Traverse to the leftmost node
            while (current != nullptr) {
                nodeStack.push(current);
                current = current->left;
            }

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

            // Move to the right subtree
            current = current->right;
        }
    }

    // Optional: Destructor to avoid memory leaks
    ~BST() {
        std::stack<TreeNode*> nodeStack;
        TreeNode* current = root;
        TreeNode* lastVisited = nullptr;

        while (current != nullptr || !nodeStack.empty()) {
            if (current != nullptr) {
                nodeStack.push(current);
                current = current->left;
            } else {
                TreeNode* topNode = nodeStack.top();
                if (topNode->right != nullptr && lastVisited != topNode->right) {
                    current = topNode->right;
                } else {
                    nodeStack.pop();
                    delete topNode;
                    lastVisited = topNode;
                }
            }
        }
    }
};

Key Breakdowns: #

• Non-recursive insert:

  • First check if the tree is empty — if so, the new node becomes the root.
  • For non-empty trees, use two pointers: current to traverse the tree, and parent to track the last non-null node (since we need to attach the new node to it).
  • Loop until current hits a nullptr (the exact spot where we'll insert), then attach the new node to the parent's left or right based on value comparison.

• Search function:

  • Traverse the tree iteratively: compare the target value with the current node's value, move left if smaller, right if larger. Return true if a match is found, false if we reach the end of the tree without success.

• Inorder traversal:

  • Uses a stack to simulate the recursive call stack. We first traverse all left children, then process the current node, then move to the right subtree. This guarantees values are added to the vector in ascending order (the standard for BST inorder traversal).

• Destructor (optional):

  • Added to clean up dynamically allocated nodes and prevent memory leaks — uses a stack to perform an iterative post-order traversal, deleting nodes as we go.

You can test this class with a simple driver program:

#include <iostream>

int main() {
    BST tree;
    tree.insert(5.0);
    tree.insert(3.0);
    tree.insert(7.0);
    tree.insert(2.0);
    tree.insert(4.0);

    std::cout << "Search for 4.0: " << (tree.search(4.0) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search for 6.0: " << (tree.search(6.0) ? "Found" : "Not Found") << std::endl;

    std::vector<double> inorderVec;
    tree.inorder(inorderVec);
    std::cout << "Inorder traversal: ";
    for (double val : inorderVec) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

This will output:

Search for 4.0: Found
Search for 6.0: Not Found
Inorder traversal: 2 3 4 5 7 

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