遞歸：傳遞給函數的變量是否需要跟蹤和更新？

我正在經歷從二叉搜索樹刪除節點的代碼，我有點糊塗了遞歸：傳遞給函數的變量是否需要跟蹤和更新？

Node deleteRec(Node root, int key) 
    { 
     /* Base Case: If the tree is empty */ 
     if (root == null) return root; 

     /* Otherwise, recur down the tree */ 
     if (key < root.key) 
      root.left = deleteRec(root.left, key); 
     else if (key > root.key) 
      root.right = deleteRec(root.right, key); 

     // if key is same as root's key, then This is the node 
     // to be deleted 
     else 
     { 
      // node with only one child or no child 
      if (root.left == null) 
       return root.right; 
      else if (root.right == null) 
       return root.left; 

      // node with two children: Get the inorder successor (smallest 
      // in the right subtree) 
      root.key = minValue(root.right); 

      // Delete the inorder successor 
      root.right = deleteRec(root.right, root.key); 
     } 

     return root; 
    }

爲什麼我們需要存儲結果的功能在root.left和root.right變量在幾個地方調用？由於root的值即傳遞給函數，隨後調用中的任何更改都會自動更新樹，是不是？那麼爲什麼要將這些值存儲在變量中呢？爲了讓下面我一點明確的是另一段代碼

// A recursive function used by topologicalSort 
void topologicalSortUtil(int v, boolean visited[], 
         Stack stack) 
{ 
    // Mark the current node as visited. 
    visited[v] = true; 
    Integer i; 

    // Recur for all the vertices adjacent to this 
    // vertex 
    Iterator<Integer> it = adj[v].iterator(); 
    while (it.hasNext()) 
    { 
     i = it.next(); 
     if (!visited[i]) 
      topologicalSortUtil(i, visited, stack); 
    } 

    // Push current vertex to stack which stores result 
    stack.push(new Integer(v)); 
}

這裏堆被傳遞給函數，我們只是一遍又一遍用它在進一步的函數調用，因爲我們知道，堆棧將繼續跨越更新調用。

我錯過了什麼，或者我明白了什麼錯？有人可以幫助我理解。謝謝！！

來源

2017-07-27 varunkr

當您刪除樹的一個節點時，父節點的左指針或右指針可能需要更新。最簡單的情況是，刪除的不是葉子時：在這種情況下，指向它的鏈接必須設置爲空。

如果另外刪除的節點恰好是根節點，則必須更新指向根的指針。

當您調用deleteRec方法時，無法預先知道返回的值是否與第一個參數相同。

來源

2017-07-27 13:07:18

」最簡單的情況是當刪除的節點是葉：在這種情況下，指向它的鏈接必須設置爲空。「感謝你的回答。所有的答案都很有幫助，但是這條線讓我很清楚。乾杯！ – varunkr

root不同級別的遞歸對象不是同一個對象。

當你遞歸樹形結構時，你可以撥打deleteRec，將root.left或root.right作爲第一個參數。因此，遞歸的下一級將把左側或右側子樹的根作爲它的「根」。

這與您傳遞給topologicalSortUtil的第三個參數的變量stack不同：此變量始終向下傳遞，因此所有級別都可以訪問相同的確切對象。

來源

2017-07-27 13:06:10 dasblinkenlight

當你刪除一個節點時，你必須拉起它下面的那部分樹。否則，您將刪除該節點及其所有後代，這是不正確的。

來源

2017-07-27 13:07:16 Steve11235

您的deleteRec方法收到二叉樹的Node並修改樹。但是，每次遞歸調用都會通過樹的不同Node。這與第二個例子不同，在第二個例子中，將相同的Stack傳遞給每個遞歸調用。

現在，當deleteRec發現Node，它應該從樹中刪除（在當前遞歸調用的root是應該刪除的Node這恰好），它不能從樹中刪除該Node。它必須修改已刪除的Node的父代Node，以便從該樹中刪除該Node。這是遞歸調用返回時發生的情況，並且由該調用返回的Node被分配給root.left或root.right。「

來源

2017-07-27 13:07:27 Eran

遞歸：傳遞給函數的變量是否需要跟蹤和更新？

回答

相關問題