0

abstract BinaryTreeサブクラスNodeを持つ単純ながありLeaf、 を生成する関数を書きたいとしますList[Leaf]。

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
      case Leaf(v) => List(tree.asInstanceOf[Leaf])
      case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }

ケースasInstanceOf[Leaf]で明示的なキャストを回避する方法はありますか? 省略した場合、次のような診断メッセージが表示されます: found: BinaryTree; 葉が必要です。Leaf

4

3 に答える 3

8

この構造が他の場所で使用されているのを見ました。それは仕事をするようです。

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
      case leaf: Leaf => List(leaf)
      case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }
于 2013-11-11T05:21:42.743 に答える
3

この方法を試してください

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
      case x@Leaf(v) => List(x)
      case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }

また、すべてのノードで新しいリストを作成しているため、実装はパフォーマンスが悪いことに注意してください。

この方法で修正できます

def genLeaves(tree:BinaryTree) = {
  def getLeaves0(tree: BinaryTree, acc:List[Leaf]): List[Leaf] =
    tree match {
      case x@Leaf(v) => x::acc
      case Node(left, right) => {
         val leftLeaves = getLeaves(left, acc)
         getLeaves(right, leftLeaves)
         }
    }
  getLeaves0(tree).reverse
}

ここでは、すでに収集されたすべてのアイテムを再利用し、トラバーサル中に割り当てられるリストは 1 つだけになります。トラバースしながら要素を収集しているので、Leaves は逆順になります (List は LIFO として機能します)。そのため、アクセスした順序で要素を取得するには、結果のリストを逆にする必要があります。

于 2013-11-11T01:28:18.510 に答える
1

treeすでに に分解したという事実を利用してLeaf(v)、リーフを再構築できます。

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
        case Leaf(v) => List(Leav(v))
        case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }
于 2013-11-11T01:27:47.347 に答える