0

下面是 Scala 中的一个程序。

def range(low : Int, high : Int) : List[Int] = {
    var result : List[Int] = Nil
    result = rangerec(root, result, low, high)
    result
}

private def rangerec(r : Node, l : List[Int], low : Int, high :Int) : List[Int] = {
      var resultList : List[Int] = List()
      if(r.left != null) {
        rangerec(r.left, resultList, low, high)
      } else if(r.right != null) {
        rangerec(r.right, resultList, low, high)
      } else {
        if(r.key >= low && r.key <= high) {
            resultList = resultList ::: List(r.key)
            resultList
        } 
      }
      resultList
}

我在我的二叉搜索树中创建了 range 方法，实现了中序遍历算法。所以它必须递归地工作，但它不打印任何东西，List()。如何修复我的算法？或编辑我的代码？

4

2 回答 2

3

我不知道 scala，但是您需要使用l作为参数传递给递归函数的列表并使用rangerec函数的输出。

private def rangerec(r : Node, l : List[Int], low : Int, high :Int) : List[Int] = {
      var resultList : List[Int] = l
      if(r.left != null) {
        resultList = rangerec(r.left, l, low, high)
      } else if(r.right != null) {
        resultList = rangerec(r.right, l, low, high)
      } else {
        if(r.key >= low && r.key <= high) {
            resultList = l ::: List(r.key)
        } 
      }
      resultList
}
于 2011-12-02T05:31:40.290 回答
0

当我看到您将结果附加到此变量时，在函数外部定义您的 resultList 。顺便说一句，为了遍历遵循这个规则。访问左，访问根，最后访问右。但是从代码中（虽然我不知道 scala），我可以破译你正在访问左，右，最后是 root。

等效的递归按顺序打印 javacode 看起来像这样

 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left); //VISIT LEFT
  }
  System.out.println(node.data); //VISIT ROOT AND PRINT
  if(node.right!=null){
   printOrdered(node.right); //VISIT RIGHT
  }
 }

所以，scala 可能看起来像这样（语法可能是错误的）

private def rangerec(r : Node) : Void = {
      if(r.left != null) {
        rangerec(r.left)
      } 
      resultList = resultList :: List(r.key)
      if(r.right != null) {
        rangerec(r.right)
      }
}

这里 resultList 是一个 List 类型的变量，应该从外部传递。

于 2011-12-02T05:58:18.980 回答