递归：传递给函数的变量是否需要跟踪和更新？

我正在经历从二叉搜索树删除节点的代码，我有点糊涂了递归：传递给函数的变量是否需要跟踪和更新？

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

递归：传递给函数的变量是否需要跟踪和更新？

回答

相关问题