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はわかりませんが）、左、右、そして最後にルートにアクセスしていることがわかります。

同等の再帰的な順序どおりの印刷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は、外部から渡される必要があるList型の変数です。

于 2011-12-02T05:58:18.980 に答える