所以我有一个家庭作业问题，我应该使用递归方法来"在植根于指定节点的子树中找到最小元素"
然后我的出发点是：
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
有人能向我解释一下为什么这不起作用吗？
注意：这都是假设你在二进制搜索树中，所以返回最小元素意味着返回最左边的元素。
这意味着您的递归调用非常简单：
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没有影响任何递归子调用，只影响当前函数调用中的一个。这意味着您返回了根的左侧节点，而不是最左侧的子节点。
我希望这是有道理的。如果你需要澄清任何事情，请留下评论或其他什么。递归一开始很难理解。
问题是Java是通过值调用的，而不是通过引用调用——尽管引用是通过值传递的。但在这种情况下，这真正意味着对min(n)的调用不会改变变量n所指的内容——它根本不会做任何事情。你可能应该做的是return min(n)。
public static void main(String[] args) throws IOException, NoSuchMethodException, InitializationError {
Logger.getRootLogger().addAppender(new ConsoleAppender(new SimpleLayout(), "System.out"));
Logger.getRootLogger().setLevel(Level.ALL);
TreeNode n1 = new TreeNode();
TreeNode n2 = new TreeNode();
TreeNode n3 = new TreeNode();
TreeNode n4 = new TreeNode();
TreeNode n5 = new TreeNode();
TreeNode n6 = new TreeNode();
n1.data = 110;
n1.left = n2;
n1.right = n3;
n2.data = 15;
n2.left = n4;
n2.right = null;
n3.data = 3;
n3.left = null;
n3.right = null;
n4.data = 4;
n4.left = null;
n4.right = n5;
n5.data = 12;
n5.left = n6;
n5.right = null;
n6.data = 19;
n6.left = null;
n6.right = null;
System.out.print("min=" + min(n1));
}
static public class TreeNode {
int data;
TreeNode left;
TreeNode right;
}
static int min(TreeNode n) {
return min(n, n.data);
}
static int min(TreeNode n, int min) {
System.out.println("N is now " + n.data);
int currentMin = min;
if (n.left != null && n.right != null) {
final int left = min(n.left);
final int right = min(n.right);
if (left < right) {
currentMin = left;
} else {
currentMin = right;
}
} else if (n.left != null) {
currentMin = min(n.left);
} else if (n.right != null) {
currentMin = min(n.right);
}
if (currentMin < min) {
return currentMin;
} else {
return min;
}
}
输出为：
N is now 110
N is now 15
N is now 4
N is now 12
N is now 19
N is now 3
min=3
您需要使用一些树遍历算法来检查树的每个节点。此外，您还需要存储当前查找到的最小值。将这个最小值传递给递归函数。它称之为"累加器"。
方法实现中的最后一条语句返回节点n的值。当n从根开始并被其左子项（如果存在）替换时，您总是得到根的左子项的值。
以下代码应该可以做到这一点：
int min(final Tree n){
int result;
if(n == null){
result = Integer.MAX_VALUE;
} else {
result = n.value;
final int leftResult = min(n.left);
if(leftResult < result){
result = leftResult;
}
final int rightResult = min(n.right);
if(rightResult < result){
result = rightResult;
}
}
return result;
}
或者你可以使用访问者模式（你需要让你的树可迭代，然后把值一个接一个地传递给访问者）：
interface TreeVisitor {
void accept(int value);
}
class MinTreeVisistor implements TreeVisitor {
int min = Integer.MAX_VALUE;
@Override
public void accept(int value) {
if(value < this.min) {
this.min = value;
}
}
}