recursion之用Java实现的二叉搜索树之递归查找元素
shangdawei
阅读:43
2024-05-29 10:23:45
评论:0
使用Java,是否可以编写递归方法来查找二叉搜索树中的元素?我说不,因为递归重新回溯的性质,除非我实现不正确?我一直在网上搜索,我能找到的只是一个迭代版本。这是我的方法:
public boolean findValueRecursively(BSTNode node, int value){
boolean isFound = false;
BSTNode currentNode = node;
if (value == currentNode.getData()){
isFound = true;
return isFound;
} else if (value < currentNode.getData()){
findValueRecursively(currentNode.getLeftNode(), value);
} else{
findValueRecursively(currentNode.getRightNode(), value);
}
return isFound;
}
// Node data structure
public class BSTNode
{
private BSTNode leftNode;
private BSTNode rightNode;
private int data;
public BSTNode(int value, BSTNode left, BSTNode right){
this.leftNode = left;
this.rightNode = right;
this.data = value;
}
}
public static void main(String[] args){
BST bst = new BST();
// initialize the root node
BSTNode bstNode = new BSTNode(4, null, null);
bst.insert(bstNode, 2);
bst.insert(bstNode, 5);
bst.insert(bstNode, 6);
bst.insert(bstNode, 1);
bst.insert(bstNode, 3);
bst.insert(bstNode, 7);
if (bst.findValueRecursively(bstNode, 7)){
System.out.println("element is found! ");
} else{
System.out.println("element is not found!");
}
}
我得到的打印结果是“找不到元素”。
任何帮助/提示或建议,非常欢迎。
提前致谢!
请您参考如下方法:
递归版本:
public boolean findValueRecursively(Node node, int value){
if(node == null) return false;
return
node.data == value ||
findValueRecursively(leftNode, value) ||
findValueRecursively(rightNode, value);
}
声明
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。