递归搜索二叉树问题

我写下面的代码递归搜索二叉树。即使我的system.out语句正在执行，return语句不会返回整个递归，因此此方法不会返回true。递归搜索二叉树问题

任何人都可以建议如何退出整个递归。

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{ 
    if (root != null) 
    { 
     int rootVal = root.getData(); 
     BinaryTreeNode left = root.getLeft(); 
     BinaryTreeNode right = root.getRight(); 
     if (left != null) 
     { 
      isElementinTree(num,left); 

     } 
     if (right != null) 
     { 
      isElementinTree(num,right); 
     } 
     if (num == rootVal) 
     { 
      System.out.println("------ MATCH -----");    
      return true; 
     }   
    } 
    return false; 
}

来源

2012-08-07 Manish

我觉得你应该先检查是否在通过节点的匹配且仅当它没有数据，就应该移动到左边或右边子树。 – 2012-08-07 13:52:16

这就是问题所在：

if (left != null) 
{ 
    isElementinTree(num,left); 

} 
if (right != null) 
{ 
    isElementinTree(num,right); 
}

你调用的方法在那些情况下 - 但忽略结果。我怀疑你只是想改变每个那些立即返回，如果它的发现：

if (left != null && isElementinTree(num, left)) 
{ 
    return true; 
} 
if (right != null && isElementinTree(num, right)) 
{ 
    return true; 
}

或者使整个事情更声明，你可以做到这一点更简单：

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{ 
    return root != null && (root.getData() == num || 
          isElementInTree(num, root.getLeft()) || 
          isElementInTree(num, root.getRight())); 
}

它的优良使用空的第二个参数调用isElementInTree，因为您已经通过第一部分保护了这一点。

来源

2012-08-07 13:52:01

那永远不会在树的右半部分返回'true' – Claudiu 2012-08-07 13:52:35

那只会搜索第一个分支，还是我错过了什么？ – pcalcao 2012-08-07 13:52:43

正在修复 - 现在检查:) – 2012-08-07 13:54:11

您需要检查该值是否在其中一个分支中，并保存该结果。

初始化变量boolean found = false;。

当你做递归调用，你需要做的是这样的：在右侧

found = isElementinTree(num,left)

同样的事情。

最后，而不是返回false，检查值树枝上找到，只是return found;

另外，如果你正在寻找的号码是第一次检查不是节点本身，而不是首先搜索每个分支。只需切换if的顺序。

来源

2012-08-07 13:52:02 pcalcao

如果你发现你正在寻找一个在左边或右边子树，你需要返回这个事实回升到主叫方的元素：

if (left != null) 
    { 
     if(isElementinTree(num,left)) return true; 
    } 
    if (right != null) 
    { 
     if(isElementinTree(num,right)) return true; 
    }

只有当你发现它没有左树，右树和当前节点是否最终会落到最后的return false。

来源

2012-08-07 13:58:51

递归解决方案：

boolean isElementinTree (int num, BinaryTreeNode root) 
{ 
    if(root == null) 
    return false; 

    if(root.value == num) 
    return true; 

    boolean n1 = isElementinTree(num,root.getLeft()); 
    boolean n2 = isElementinTree(num,root.getRight()); 

    return n1 ? n1 : n2; 

}

来源

2013-08-01 00:57:52

递归搜索二叉树问题

回答

相关问题