使用递归方法查找给定根的子树中的最小元素:我在这里做错了什么？

Question

所以我有一个功课问题,我应该使用递归方法"找到以指定节点为根的子树中的最小元素"

然后我将此作为我的出发点:

   public TreeNode
{
    int data;
    TreeNode left;
    TreeNode right;
}

和

/**
Finds the minimum value for the subtree that is 
rooted at a given node
@param n The root of the subtree
@return The minimum value 
PRECONDITION: n is not null.
*/
int min(TreeNode n)
{
  // COMPLETE THE BODY OF THIS METHOD
}

现在,我已经编写了一个非常基本的驱动程序,用于将节点插入到树中,并且我已经编写了我的递归方法,但它似乎在计算而不是向下,这是我的方法:

int min(TreeNode n){      
if(n.left != null) {
  n = n.left;
  min(n);
  System.out.println("N is now " + n.value);
 }
    return n.value;
   }

输出我的代码:

Building tree with rootvalue 25
  =================================
  Inserted 11 to left of node 25
  Inserted 15 to right of node 11
  Inserted 16 to right of node 15
  Inserted 23 to right of node 16
  Inserted 79 to right of node 25
  Inserted 5 to left of node 11
  Inserted 4 to left of node 5
  Inserted 2 to left of node 4
    Root is 25
    N is now 2
    N is now 4
    N is now 5
    N is now 11
    The minimum integer in the given nodes subtree is: 11

有人可以向我解释为什么这不起作用？

Answer 1

注意:这都是假设你在二进制搜索树中,所以返回最小元素意味着返回最左边的元素.

这意味着您的递归调用非常简单:

min(node):
  if this node has a left node:
    return min(node.left)
  if this node does not have a left node:
    return this node's value

逻辑是,如果我们没有另一个左节点,那么我们是最左边的节点,所以我们是最小值.

现在,在Java中:

int min(TreeNode n){
  if (n.left == null)
    return n.value;
  return min(n.left); // n.left cannot be null here
}

现在解释您的结果,考虑这种方法的工作原理.它min(n.left)在继续之前调用下一个节点()上的方法.在你的情况下,你有一个println在这个递归调用之后.因此,递归调用println 内部是第一个.因此,您的打印件从树的底部开始,然后重新开始工作.这解释了"逆序"打印.
然后你的方法11作为你的结果返回,因为(正如另一个答案所解释的那样)你n = n.left没有影响你的任何递归子调用,只影响当前函数调用中的一个.这意味着您返回了根的左节点,而不是最左边的子节点.

我希望这是有道理的.如果您需要澄清任何事情,请留下评论或其他内容.一开始,你可以非常难以接受递归.