二叉搜索樹插入中迭代和遞歸之間的區別

我正試圖在二叉搜索樹中實現插入。根據我的邏輯，遞歸和迭代都執行非常類似的任務 - 但是，我的遞歸函數工作，但我的迭代解決方案沒有。執行有什麼區別？爲什麼迭代功能不起作用？（忽略不同的返回類型）二叉搜索樹插入中迭代和遞歸之間的區別

發生的錯誤是，在迭代的情況下，只有一個元素被正確插入。連續插入不起作用。

類定義：

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

二叉搜索樹插入中迭代和遞歸之間的區別

回答

相關問題