二叉搜索树插入中迭代和递归之间的区别

我正试图在二叉搜索树中实现插入。根据我的逻辑，递归和迭代都执行非常类似的任务 - 但是，我的递归函数工作，但我的迭代解决方案没有。执行有什么区别？为什么迭代功能不起作用？（忽略不同的返回类型）二叉搜索树插入中迭代和递归之间的区别

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

类定义：

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); 
    } 
}

谢谢！

来源

2014-11-02 yaitzme

您不修改迭代版本中的树。你正在修改一个局部变量'travNode'，最后被扔掉。 – 2014-11-02 10:16:33

在你的递归中，当你调用insert（）时，你的整个函数是正确的。

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

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

来源

2014-11-02 09:58:23 Eric

我明白我必须做什么才能使迭代方法奏效，但是能否告诉我为什么现有的代码不起作用？在这种情况下和递归的情况下，我到达了我需要插入的地方，然后插入一个新的节点。 – yaitzme 2014-11-02 15:55:14

二叉搜索树插入中迭代和递归之间的区别

回答

相关问题