为什么不能递归地工作？

Question

下面是斯卡拉的一个程序。

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 
} 

我在我的二叉查找树中实现了范围方法，实现了按顺序遍历算法。所以它必须递归地工作，但它不会打印任何东西，List（）。如何修复我的算法？或编辑我的代码？

Answer 1

我不知道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 
} 

Answer 2

定义你的resultList函数外，因为我看到你将结果追加到这个变量。顺便说一下，为了遍历遵循这个规则。访问左侧，访问根目录并最终访问权限。然而，从代码（尽管我不知道scala），我可以破译你正在访问左，右，最后是根。

一种等价递归中序打印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 
    } 
} 

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

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是一个变量应该从外部传递的类型列表。