c++ - 二叉搜索树插入中迭代和递归的区别

Question

我正在尝试在二叉搜索树中实现插入。根据我的逻辑，递归和迭代都在执行非常相似的任务——但是，我的递归函数有效，但我的迭代解决方案无效。执行力有何不同？为什么迭代功能不起作用？ (忽略不同的返回类型)

发生的错误是在迭代的情况下，只有一个元素被正确插入。连续插入不起作用。

类定义:

class Node
{
    public:
        Node(int x, Node *l = NULL, Node *r = NULL)
        {
            val = x;
            left = l;
            right = r;
        }
        int val;
        Node *left;
        Node *right;
};

迭代:

Node* insert(Node* &root, int x)
{
    Node* newNode = new Node(x);
    if (root == NULL)
    {
        root = newNode;
        return root;
    }
    else
    {
        Node* travNode = root;
        while (travNode != NULL)
        {
            if (x < travNode->val)
                travNode = travNode->left;
            else
                travNode = travNode->right;
        }
        travNode = newNode;
    }
    return root;
}

递归:

void insert(Node* &root, int x)
{
    if (root == NULL)
    {
        Node* newNode = new Node(x);
        root = newNode;
    }
    else
    {
        if (x < root->val)
            insert(root->left, x);
        else
            insert(root->right, x);
    }
}

谢谢!

Answer 1

在你的递归中，你的整个函数在你调用 insert() 时执行，这是正确的。

在迭代解决方案中，您找到一个节点，该节点将成为新节点的父节点，但您用新节点覆盖该节点而不是将其设置为子节点。

您需要在某处设置travNode->left = newNode 或travNode->right = newNode。