Почему это не работает рекурсивно?

Question

Ниже приведена программа на 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 (). Как исправить мой алгоритм? или отредактировать мой код?

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) я могу расшифровать, что вы посещаете левый, правый и, наконец, 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, которую следует передавать извне.