二叉搜索树 findNode 方法总是 returns root
binary search tree findNode method always returns root
我有一个整数的二叉搜索树,包括 1,2,...,9。我的遍历方法有效,我知道节点在那里并且顺序正确。
我创建了两种搜索方法,一种是查找并 returns 节点,另一种是调用该方法并打印节点是否存在,具体取决于它 returns (null 表示它不存在)。
findNode(int, BSTNode) 但是一直返回根节点。当我将它与在线示例代码进行比较时,它似乎是正确的。
这是两个方法,我在 7,5,6,1,12,15 的主要方法中调用了 searchPrint(int)(注意树中不存在 12 和 15):
//this method calls findNode(int,BSTNode) and prints a message if the value is found
// in the tree
public void searchPrint(int value)
{
System.out.print(value);
if (findNode(value, root) == null)
{
System.out.println(" does not exist in the tree.");
} else
{
System.out.println(" exists in the tree.");
}
}//end searchPrint(int) ----------------------------------------------------
//this method recursively looks for the node that contains 'value' and
//returns that node if it is found. Returns null if no nodes contain
//the value.
private BSTNode findNode(int value, BSTNode current)
{
if(current != null)
{
if (value == current.getValue())
{
System.out.print(" **Test* entering "
+ "if(value = current.value loop...** ");
return current;
} else
{
if (value < current.getValue())
{
findNode(value,current.getLeft());
} else
{
findNode(value,current.getRight());
}
}
} else
{
return null;
}
return current;
}//end findNode(int,BSTNode) -----------------------------------------------
这是输出:
Traversals:
in-order
1
2
3
4
5
6
7
8
9
pre-order
6
2
1
4
3
5
7
9
8
post-order
1
3
5
4
2
8
9
7
6
7 **Test* entering if(value = current.value loop...** exists in the tree.
5 **Test* entering if(value = current.value loop...** exists in the tree.
6 **Test* entering if(value = current.value loop...** exists in the tree.
1 **Test* entering if(value = current.value loop...** exists in the tree.
12 exists in the tree.
15 exists in the tree.
我在纸上写下了当我搜索一个值时会发生什么,它 returns 根是没有意义的。我做错了什么?
你在对 findNode() 的递归调用中缺少 return,因此它总是到达方法末尾的 return
更改为:
private BSTNode findNode(int value, BSTNode current)
{
if(current != null)
{
if (value == current.getValue())
{
System.out.print(" **Test* entering "
+ "if(value = current.value loop...** ");
return current;
} else
{
if (value < current.getValue())
{
return findNode(value,current.getLeft());
} else
{
return findNode(value,current.getRight());
}
}
} else
{
return null;
}
return current;
}
您的递归调用 findNode(value,current.getLeft());
或 findNode(value,current.getRight());
将 return 实际结果。您只是保留该结果而没有任何用处。
取而代之的是,
使用
return findNode(value,current.getLeft());
和
return findNode(value,current.getRight());
我有一个整数的二叉搜索树,包括 1,2,...,9。我的遍历方法有效,我知道节点在那里并且顺序正确。
我创建了两种搜索方法,一种是查找并 returns 节点,另一种是调用该方法并打印节点是否存在,具体取决于它 returns (null 表示它不存在)。
findNode(int, BSTNode) 但是一直返回根节点。当我将它与在线示例代码进行比较时,它似乎是正确的。
这是两个方法,我在 7,5,6,1,12,15 的主要方法中调用了 searchPrint(int)(注意树中不存在 12 和 15):
//this method calls findNode(int,BSTNode) and prints a message if the value is found
// in the tree
public void searchPrint(int value)
{
System.out.print(value);
if (findNode(value, root) == null)
{
System.out.println(" does not exist in the tree.");
} else
{
System.out.println(" exists in the tree.");
}
}//end searchPrint(int) ----------------------------------------------------
//this method recursively looks for the node that contains 'value' and
//returns that node if it is found. Returns null if no nodes contain
//the value.
private BSTNode findNode(int value, BSTNode current)
{
if(current != null)
{
if (value == current.getValue())
{
System.out.print(" **Test* entering "
+ "if(value = current.value loop...** ");
return current;
} else
{
if (value < current.getValue())
{
findNode(value,current.getLeft());
} else
{
findNode(value,current.getRight());
}
}
} else
{
return null;
}
return current;
}//end findNode(int,BSTNode) -----------------------------------------------
这是输出:
Traversals:
in-order
1
2
3
4
5
6
7
8
9
pre-order
6
2
1
4
3
5
7
9
8
post-order
1
3
5
4
2
8
9
7
6
7 **Test* entering if(value = current.value loop...** exists in the tree.
5 **Test* entering if(value = current.value loop...** exists in the tree.
6 **Test* entering if(value = current.value loop...** exists in the tree.
1 **Test* entering if(value = current.value loop...** exists in the tree.
12 exists in the tree.
15 exists in the tree.
我在纸上写下了当我搜索一个值时会发生什么,它 returns 根是没有意义的。我做错了什么?
你在对 findNode() 的递归调用中缺少 return,因此它总是到达方法末尾的 return
更改为:
private BSTNode findNode(int value, BSTNode current)
{
if(current != null)
{
if (value == current.getValue())
{
System.out.print(" **Test* entering "
+ "if(value = current.value loop...** ");
return current;
} else
{
if (value < current.getValue())
{
return findNode(value,current.getLeft());
} else
{
return findNode(value,current.getRight());
}
}
} else
{
return null;
}
return current;
}
您的递归调用 findNode(value,current.getLeft());
或 findNode(value,current.getRight());
将 return 实际结果。您只是保留该结果而没有任何用处。
取而代之的是,
使用
return findNode(value,current.getLeft());
和
return findNode(value,current.getRight());