二叉树搜索值小于

我为大学工作创建了一个二叉树算法，我需要开发一种算法，可以高效地找到所有小于指定值的值（它们需要按顺序排列）。二叉树搜索值小于

这是我想出的解决方案（上图是万一您忘记了二叉树的样子）。

private BinaryTreeNode root; 
public int[] getBeforeJoinedNum(int num){ 
     usersInOrder = new ArrayList<User>(); 
     beforeNum(num, root); 
     return usersInOrder; 
} 

private void beforeNum(int num, BinaryTreeNode n){ 
     if (n != null){ 
      beforeNum(num, n.getLeft()); 
      int nodeValue = n.getValue(); 
      if (num<nodeValue){ 
       usersInOrder.add(n.getValue()); 
       beforeNum(num, n.getRight()); 
      } 
     } 
    }

这个算法的问题是它做了不必要的比较。例如，如果我希望所有数字小于10，那么代码将检查9（即1,5,8）的所有数字，如果它小于10，则应该很明显小于9的任何东西当然应该是在列表中，不需要任何比较。

如何使该算法更高效？不幸的是，我不能使用Java集合框架，因为数据结构是课程的重点。

来源

2014-03-06 Yahya Uddin

'BinaryTreeNode'与'UserNode'有什么关系？ –

只需创建一个方法，让任何给定的父母的每个孩子。然后做一个比较。 if（num leigero

似乎'root'没有被初始化为任何东西，这意味着'if（n！= null）'永远不会成立。 – aliteralmind

你们哪知道他们履行财产子树，只是做一个标准的中序遍历：

private void addAll(UserNode n) { 
    if (n == null) return; 
    addAll(n.getLeft()); 
    usersInOrder.add(n.getValue()); 
    addAll(n.getRight()); 
} 

private void beforeNum(int num, UserNode n){ 
    if (n == null) return; 
    if (n.getValue() < num) { 
     addAll(n.getLeft()); 
     usersInOrder.add(n.getValue()); 
     beforeNum(num, n.getRight()); 
    } else { 
     beforeNum(num, n.getLeft()); 
    } 
}

请注意，我也beforeNum固定逻辑错误：你有>和混合起来<你没有在正确的情况下遍历右边的子树。

来源

2014-03-06 02:43:07

感谢您的修复。我真的很困惑了一秒 –

有没有听说过inorder search？下面是一个示例代码。修改它，以便它接受一个参数其中的“用户节点”，并停止遍历时，它仍然比“usernode”

public void inOrderTraverse(Node root){ 
     if(root != null){ 
      inOrderTraverse(root.getLeft()); 
      System.out.print(" "+root.getData()); 
      inOrderTraverse(root.getRight()); 
     } 

    }

这里有一个快速修改后的版本较低：

public void inOrderTraverse(Node root,UserNode n){ 
     if(root != null&&root.compareTo(n)<0){ 
      inOrderTraverse(root.getLeft()); 
      System.out.print(" "+root.getData()); 
      inOrderTraverse(root.getRight()); 
     } 

    }

你需要无论如何遍历左侧的所有节点。

来源

2014-03-06 02:49:41

二叉树搜索值小于

回答

相关问题