recursion之用Java实现的二叉搜索树之递归查找元素

shangdawei 阅读:13 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); 
    } 


标签:java
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号