カッコ列は二分木に対応させることができます。次に示す二分木 Tree をカッコ列に変換する関数 treeToKakko を定義してください。
リスト : 二分木 Tree の定義
abstract class Tree {
def left: Tree
def right: Tree
}
case class Node(left: Tree, right: Tree) extends Tree
case object Leaf extends Tree {
def left = throw new Exception("Leaf: left is none")
def right = throw new Exception("Leaf: right is none")
}
def treeToKakko(node: Tree): String
scala> treeToKakko(Node(Leaf,Leaf)) val res0: String = () scala> treeToKakko(Node(Node(Leaf,Leaf),Leaf)) val res1: String = (()) scala> treeToKakko(Node(Leaf, Node(Leaf,Leaf))) val res2: String = ()() scala> treeToKakko(Node(Node(Leaf,Leaf), Node(Leaf,Leaf))) val res3: String = (())() scala> treeToKakko(Node(Node(Node(Leaf,Leaf),Leaf),Leaf)) val res4: String = ((())) scala> treeToKakko(Node(Leaf,Node(Leaf,Node(Leaf,Leaf)))) val res5: String = ()()()
treeToKakko の逆変換を行う関数 kakkoToTree を定義してください。
def kakkoToTree(s: String): Tree
scala> kakkoToTree("()")
val res0: yasp04.Tree = Node(Leaf,Leaf)
scala> kakkoToTree("()()")
val res1: yasp04.Tree = Node(Leaf,Node(Leaf,Leaf))
scala> kakkoToTree("(())")
val res2: yasp04.Tree = Node(Node(Leaf,Leaf),Leaf)
scala> kakkoToTree("((()))")
val res3: yasp04.Tree = Node(Node(Node(Leaf,Leaf),Leaf),Leaf)
scala> kakkoToTree("()()()")
val res4: yasp04.Tree = Node(Leaf,Node(Leaf,Node(Leaf,Leaf)))
scala> kakkoToTree("(())()")
val res5: yasp04.Tree = Node(Node(Leaf,Leaf),Node(Leaf,Leaf))
葉を n 個持つ二分木 Tree を列挙する関数 trees を定義してください。
def trees(f: Tree => Unit, n: Int): Unit
scala> trees(println, 3) Node(Node(Leaf,Leaf),Leaf) Node(Leaf,Node(Leaf,Leaf)) scala> trees(println, 4) Node(Node(Node(Leaf,Leaf),Leaf),Leaf) Node(Node(Leaf,Node(Leaf,Leaf)),Leaf) Node(Node(Leaf,Leaf),Node(Leaf,Leaf)) Node(Leaf,Node(Node(Leaf,Leaf),Leaf)) Node(Leaf,Node(Leaf,Node(Leaf,Leaf)))
葉にデータを格納する二分木 Tree1 を次のように定義します。
リスト : 二分木 Tree1
abstract class Tree1[A] {
def left: Tree1[A]
def right: Tree1[A]
}
case class Nd[A](left: Tree1[A], right: Tree1[A]) extends Tree1[A]
case class Lf[A](item: A) extends Tree1[A] {
def left = throw new Exception("Lf: left is none")
def right = throw new Exception("Lf: right is none")
}
二分木 Tree とデータを格納したリスト xs から二分木 Tree1 を生成する関数 makeTree1 を定義してください。
def makeTree1[A](node: Tree, xs: List[A]): (Tree1[A], List[A])
scala> makeTree1(Leaf, List(1)) val res0: (yasp04.Tree1[Int], List[Int]) = (Lf(1),List()) scala> makeTree1(Node(Leaf, Leaf), List(1, 2)) val res1: (yasp04.Tree1[Int], List[Int]) = (Nd(Lf(1),Lf(2)),List()) scala> makeTree1(Node(Node(Leaf, Leaf), Leaf), List(1, 2, 3)) val res2: (yasp04.Tree1[Int], List[Int]) = (Nd(Nd(Lf(1),Lf(2)),Lf(3)),List()) scala> makeTree1(Node(Node(Leaf, Leaf), Node(Leaf, Leaf)), List(1, 2, 3, 4)) val res3: (yasp04.Tree1[Int], List[Int]) = (Nd(Nd(Lf(1),Lf(2)),Nd(Lf(3),Lf(4))),List())
リスト xs を前後で二分割することを考えます。二分割したリストをすべて求める関数 splits を定義してください。
def splits[A](xs: List[A]): List[(List[A], List[A])]
scala> splits(List(1)) val res0: List[(List[Int], List[Int])] = List((List(),List(1)), (List(1),List())) scala> splits(List(1, 2)).foreach(println) (List(),List(1, 2)) (List(1),List(2)) (List(1, 2),List()) scala> splits(List(1, 2, 3)).foreach(println) (List(),List(1, 2, 3)) (List(1),List(2, 3)) (List(1, 2),List(3)) (List(1, 2, 3),List()) scala> splits(List(1, 2, 3, 4)).foreach(println) (List(),List(1, 2, 3, 4)) (List(1),List(2, 3, 4)) (List(1, 2),List(3, 4)) (List(1, 2, 3),List(4)) (List(1, 2, 3, 4),List())
二分木 Tree1 に格納する要素をリスト xs で指定したとき、二分木 Trees1 を列挙する関数 trees2 を作ってください。
def trees2[A](f: Tree1 => Unit, xs: List[A]): Unit
scala> trees2(println, List(1, 2)) Nd(Lf(1),Lf(2)) scala> trees2(println, List(1, 2, 3)) Nd(Nd(Lf(1),Lf(2)),Lf(3)) Nd(Lf(1),Nd(Lf(2),Lf(3))) scala> trees2(println, List(1, 2, 3, 4)) Nd(Nd(Nd(Lf(1),Lf(2)),Lf(3)),Lf(4)) Nd(Nd(Lf(1),Nd(Lf(2),Lf(3))),Lf(4)) Nd(Nd(Lf(1),Lf(2)),Nd(Lf(3),Lf(4))) Nd(Lf(1),Nd(Nd(Lf(2),Lf(3)),Lf(4))) Nd(Lf(1),Nd(Lf(2),Nd(Lf(3),Lf(4))))
二分木 Tree1 の木の高さを求める関数 treeHeight, 葉の個数を求める関数 countLeaf, 二分木の中に要素 x があるかチェックする関数 memberTree を定義してください。
def treeHeight[A](node: Tree1[A]): Int def countLeaf[A](node: Tree1[A]): Int def memberTree[A](x: A, node: Tree1[A]): Boolean
scala> treeHeight(Lf(1)) val res0: Int = 1 scala> treeHeight(Nd(Lf(1), Lf(2))) val res1: Int = 2 scala> treeHeight(Nd(Nd(Lf(1), Lf(2)), Lf(3))) val res2: Int = 3 scala> leafCount(Lf(1)) val res3: Int = 1 scala> leafCount(Nd(Lf(1), Lf(2))) val res4: Int = 2 scala> leafCount(Nd(Nd(Lf(1), Lf(2)), Lf(3))) val res5: Int = 3 scala> memberTree(1, Nd(Nd(Lf(1), Lf(2)), Nd(Lf(3), Lf(4)))) val res6: Boolean = true scala> memberTree(4, Nd(Nd(Lf(1), Lf(2)), Nd(Lf(3), Lf(4)))) val res7: Boolean = true scala> memberTree(5, Nd(Nd(Lf(1), Lf(2)), Nd(Lf(3), Lf(4)))) val res8: Boolean = false
二分木 Tree1 から述語 f が真を返す要素を探す関数 find, Tree1 の葉に関数 f を適用してその結果を Tree1 に格納して返す関数 mapTree, Tree1 を畳み込む関数 foldTree を定義してください。
def find[A](f: A => Boolean, node: Tree1[A]): Option[A] def mapTree[A, B](f: A => B, node: Tree1[A]): Tree1[B] def foldTree[A, B](f: (A, B) => B, a: B, node: Tree1[A]): B
scala> find((x: Int) => x % 2 == 0, Nd(Nd(Lf(1), Lf(3)), Nd(Lf(5), Lf(6)))) val res0: Option[Int] = Some(6) scala> find((x: Int) => x % 2 == 0, Nd(Nd(Lf(1), Lf(3)), Nd(Lf(5), Lf(7)))) val res1: Option[Int] = None scala> mapTree((x: Int) => x * x, Nd(Nd(Lf(1), Lf(2)), Nd(Lf(3), Lf(4)))) val res2: yasp04.Tree1[Int] = Nd(Nd(Lf(1),Lf(4)),Nd(Lf(9),Lf(16))) scala> foldTree((x: Int, a: Int) => x + a, 0, Nd(Nd(Lf(1), Lf(2)), Nd(Lf(3), Lf(4)))) val res3: Int = 10 scala> foldTree((x: Int, a: List[Int]) => x :: a, Nil, Nd(Nd(Lf(1), Lf(2)), Nd(Lf(3), Lf(4)))) val res4: List[Int] = List(1, 2, 3, 4)
次に示す二分木 Tree2 を深さ優先で巡回する関数 preOreder, inOrder, postOrder を定義してください。preOrder は行きがけ順、inOrder は通りがけ順、postOrder は帰りがけ順で二分木を巡回します。
リスト : 二分木 Tree2 の定義
abstract class Tree2[+A] {
def left: Tree2[A]
def right: Tree2[A]
def item: A
def isEmpty: Boolean
}
case class Nd2[A](item: A, left: Tree2[A], right: Tree2[A]) extends Tree2[A] {
def isEmpty: Boolean = false
}
case object Nils extends Tree2[Nothing] {
def isEmpty: Boolean = true
def left = throw new Exception("left: Empty Tree2")
def right = throw new Exception("right: Empty Tree2")
def item = throw new Exception("item: Empty Tree2")
}
def inOrder[A](node: Tree2[A]): List[A] def preOrder[A](node: Tree2[A]): List[A] def postOrder[A](node: Tree2[A]): List[A]
scala> val a: Tree2[Int] = Nd2(4, Nd2(2, Nd2(1, Nils, Nils), Nd2(3, Nils, Nils)), Nd2(6, Nd2(5, Nils, Nils), Nd2(7, Nils, Nils))) val a: yasp04.Tree2[Int] = Nd2(4,Nd2(2,Nd2(1,Nils,Nils),Nd2(3,Nils,Nils)), Nd2(6,Nd2(5,Nils,Nils),Nd2(7,Nils,Nils))) scala> inOrder(a) val res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7) scala> preOrder(a) val res1: List[Int] = List(4, 2, 1, 3, 6, 5, 7) scala> postOrder(a) val res2: List[Int] = List(1, 3, 2, 5, 7, 6, 4)
二分木 Tree2 を幅優先で巡回する関数 bfs を定義してください。
def bfs[A](node: Tree2[A]): List[A]
scala> val a: Tree2[Int] = Nd2(4, Nd2(2, Nd2(1, Nils, Nils), Nd2(3, Nils, Nils)), Nd2(6, Nd2(5, Nils, Nils), Nd2(7, Nils, Nils))) val a: yasp04.Tree2[Int] = Nd2(4,Nd2(2,Nd2(1,Nils,Nils),Nd2(3,Nils,Nils)), Nd2(6,Nd2(5,Nils,Nils),Nd2(7,Nils,Nils))) scala> bfs(a) val res0: List[Int] = List(4, 2, 6, 1, 3, 5, 7)
バランスの取れたカッコ列と二分木は 1 対 1 に対応します。二分木を行きがけ順で巡回するとき、途中の節では左カッコ ( を出力して左右の枝をたどり、葉に到達したら右カッコ ) を出力すると、カッコ列を生成することができます。
リスト : 二分木をカッコ列に変換
def treeToKakko(node: Tree): String = {
def iter(node: Tree): String =
node match {
case Leaf => ")"
case Node(l, r) => "(" + iter(l) + iter(r)
}
iter(node).init
}
実際の処理は局所関数 iter で行います。引数が Leaf の場合は右カッコを返します。引数が Node(l, r) の場合は、iter を再帰呼び出しして左部分木 l をたどり、それから右部分木 r をたどります。その結果と左カッコを演算子 + で連結すればいいわけです。ただし、最後に余分な右カッコが付いてくるので、メソッド init で最後の文字を削除します。二分木の場合、葉 (Leaf) の個数を n とすると、節 (Node) の個数は n - 1 になります。カッコ列と違って Leaf の個数が一つ多くなることに注意してください。
リスト : カッコ列を二分木に変換
def kakkoToTree(s: String): Tree = {
def iter(xs: List[Char]): (Tree, List[Char]) =
xs match {
case Nil => (Leaf, Nil)
case ')'::xs1 => (Leaf, xs1)
case '('::xs1 => {
val (l, xs2) = iter(xs1)
val (r, xs3) = iter(xs2)
(Node(l, r), xs3)
}
case _ => throw new Exception("kakkoToTree: input error")
}
iter(s.toList)._1
}
実際の処理は局所関数 iter で行います。リストの先頭要素が右カッコの場合は (Leaf, xs1) を返します。左カッコの場合は、iter を再帰呼び出しして左部分木 l を生成し、それから右部分木 r を生成します。あとは (Node(l, r), xs3) を返すだけです。ただし、葉に対応する右カッコがひとつ少ないので、引数 ls が空リストの場合は葉 Leaf を返すようにします。
リスト : 二分木の列挙
def trees(f: Tree => Unit, n: Int): Unit = {
kakko((s: String) => f(kakkoToTree(s)), n - 1)
}
// 別解
def trees1(n: Int): List[Tree] = {
def splits(n: Int): List[(Int, Int)] =
for (x <- (1 until n).toList) yield (x, n - x)
def joins(ls: List[Tree], rs: List[Tree]): List[Tree] =
for (l <- ls; r <- rs) yield Node(l, r)
if (n == 1) List(Leaf)
else splits(n).flatMap((x: (Int, Int)) => joins(trees1(x._1), trees1(x._2)))
}
trees は kakko (問題 29) と kakkoTotree を使えば簡単に定義することができます。
別解は n 個の要素を左右の部分木に振り分ける局所関数 splits を使って二分木を生成します。たとえば n が 4 の場合、二分割する方法は (1, 3), (2, 2) (3, 1) の 3 通りがあります。あとは、同じことを左右の部分木に行って、それを統合していけばいいわけです。
n が 1 の場合は List(Leaf) を返します。そうでなければ、splits で n を分割します。匿名関数の中で分割した数に trees を適用して左右の部分木を生成し、それを局所関数 joins で統合します。
たとえば、4 を 1 と 3 に分割する場合、List(Leaf) と List(Node(Node,Leaf,Leaf),Leaf), Node(Leaf,Node(Leaf,Leaf))) を統合して、2 つの二分木を生成することになります。この処理はリスト内包表記を使うと簡単ですね。あとは flatMap で匿名関数を適用して結果のリストを平坦化するだけです。
それでは実行してみましょう。
scala> trees1(3).foreach(println) Node(Leaf,Node(Leaf,Leaf)) Node(Node(Leaf,Leaf),Leaf) scala> trees1(4).foreach(println) Node(Leaf,Node(Leaf,Node(Leaf,Leaf))) Node(Leaf,Node(Node(Leaf,Leaf),Leaf)) Node(Node(Leaf,Leaf),Node(Leaf,Leaf)) Node(Node(Leaf,Node(Leaf,Leaf)),Leaf) Node(Node(Node(Leaf,Leaf),Leaf),Leaf)
なお、別解は山下伸夫さんの『Haskell プログラミング 木(tree)で遊ぶ』 (http://www.ipsj.or.jp/07editj/promenade/4605.pdf) を参考にさせていただきました。山下伸夫さんに感謝いたします。
リスト : 二分木 (Tree1) の生成
def makeTree1[A](node: Tree, xs: List[A]): (Tree1[A], List[A]) = {
def iter(node: Tree, xs: List[A]): (Tree1[A], List[A]) =
(node, xs) match {
case (_, Nil) => throw new Exception("makeTree1 error")
case (Leaf, (x::xs)) => (Lf(x), xs)
case (Node(l, r), xs) => {
val (l1, ys) = iter(l, xs)
val (r1, zs) = iter(r, ys)
(Nd(l1, r1), zs)
}
case _ => throw new Exception("makeTree1 error")
}
//
iter(node, xs)
}
実際の処理は局所関数 iter で行います。最初の節で、Tree1 に格納する要素がなくなったならばエラーを送出します。Tree が葉 (Leaf) の場合はリストの先頭要素 x を Lf に格納して、残りのリスト xs と一緒にタプルに格納して返します。節 Node の場合は iter を再帰呼び出しして、左部分木 l1 と右部分木 r1 を生成して、Nd(l1, r1) と残りのリスト zs をタプルに格納して返します。
リスト : リストの二分割
def splits[A](xs: List[A]): List[(List[A], List[A])] =
xs match {
case Nil => Nil
case x::Nil => List((Nil, List(x)), (List(x), Nil))
case y::ys => (Nil, xs) :: (for ((z, zs) <- splits(ys)) yield (y::z, zs))
}
最初の節で、引数が空リストの場合はリストを分割できないので空リストを返します。次の節で、要素が x しかない場合は空リストと List(x) に分割します。最後の節で、空リストと xs に分割する場合は (Nil, xs) をリストに格納するだけです。それ以外の場合は、xs を y :: ys に分割し、ys に対して splits を再帰呼び出しします。そして、その返り値のタプルの第 1 要素 z (前半のリスト) に y を追加します。
リスト : 二分木 (Tree1) の列挙
def trees2[A](f: Tree1[A] => Unit, xs: List[A]): Unit = {
trees((node: Tree) => f(makeTree1(node, xs)._1), xs.length)
}
// 別解
def splits2[A](xs: List[A]): List[(List[A], List[A])] =
xs match {
case Nil | (_::Nil) => Nil
case x::xs => (List(x), xs) :: (for ((ys, zs) <- splits2(xs)) yield (x::ys, zs))
}
def trees3[A](xs: List[A]): List[Tree1[A]] = {
def joins(ls: List[Tree1[A]], rs: List[Tree1[A]]): List[Tree1[A]] =
for (l <- ls; r <- rs) yield Nd(l, r)
//
xs match {
case Nil => throw new Exception("trees3: Empty List")
case x::Nil => List(Lf(x))
case _ => splits2(xs).flatMap((x: (List[A], List[A])) => joins(trees3(x._1), trees3(x._2)))
}
}
trees2 は trees と makeTree1 を使うと簡単です。trees で Tree を生成して、それを匿名関数に渡します。その中で引数 node に makeTree1 を適用して Tree を Tree1 に変換します。
別解はリストを二分割する関数 splits2 を使ったものです。splits2 はリストを長さが 1 以上のリストに二分割します。たとえば、リストが [1,2,3,4] の場合、([1], [2,3,4]), ([1,2], [3,4]), [1,2,3],[4]) の 3 通りがあります。あとは、同じことを左右の部分木に行って、それを統合していけばいいわけです。
それでは実行してみましょう。
scala> trees3(List(1, 2, 3, 4)).foreach(println) Nd(Lf(1),Nd(Lf(2),Nd(Lf(3),Lf(4)))) Nd(Lf(1),Nd(Nd(Lf(2),Lf(3)),Lf(4))) Nd(Nd(Lf(1),Lf(2)),Nd(Lf(3),Lf(4))) Nd(Nd(Lf(1),Nd(Lf(2),Lf(3))),Lf(4)) Nd(Nd(Nd(Lf(1),Lf(2)),Lf(3)),Lf(4)) scala> trees3(List(1, 2, 3)).foreach(println) Nd(Lf(1),Nd(Lf(2),Lf(3))) Nd(Nd(Lf(1),Lf(2)),Lf(3))
なお、trees3 は山下伸夫さんの『Haskell プログラミング 木(tree)で遊ぶ』 (http://www.ipsj.or.jp/07editj/promenade/4605.pdf) を参考にさせていただきました。山下伸夫さんに感謝いたします。
リスト : 木の高さ、葉の個数、要素が含まれているか
def treeHeight[A](node: Tree1[A]): Int =
node match {
case Lf(_) => 1
case Nd(l, r) => 1 + (treeHeight(l) max treeHeight(r))
}
def leafCount[A](node: Tree1[A]): Int =
node match {
case Lf(_) => 1
case Nd(l, r) => leafCount(l) + leafCount(r)
}
def memberTree[A](x: A, node: Tree1[A]): Boolean =
node match {
case Lf(y) => x == y
case Nd(l, r) => if (memberTree(x, l)) true else memberTree(x, r)
}
treeHeight は引数 node が Lf ならば 1 を返します。Nd の場合、左部分木と右部分木の高さを treeHeight で求め、max で大きいほうの値を選び、その値を +1 して返します。leafCount は引数 node が Lf ならば 1 を返します。Nd の場合、左部分木と右部分木の葉の個数を leafCount で求め、それを足し算して返します。memberTree は引数 node が Lf(y) ならば引数 x と要素 y を演算子 == で比較します。Nd の場合、左部分木をたどり、その結果が true ならば true を返します。false ならば右部分木を memberTree で探索します。
リスト : 二分木の高階関数
def find[A](f: A => Boolean, node: Tree1[A]): Option[A] =
node match {
case Lf(x) => if (f(x)) Some(x) else None
case Nd(l, r) => find(f, l) match {
case None => find(f, r)
case x => x
}
}
def mapTree[A, B](f: A => B, node: Tree1[A]): Tree1[B] =
node match {
case Lf(x) => Lf(f(x))
case Nd(l, r) => Nd(mapTree(f, l), mapTree(f, r))
}
def foldTree[A, B](f: (A, B) => B, a: B, node: Tree1[A]): B =
node match {
case Lf(x) => f(x, a)
case Nd(l, r) => foldTree(f, foldTree(f, a, r), l)
}
find は memberTree とほとんど同じです。返り値が Option 型になるので、match 式でマッチングして、None ならば右部分木を探索します。mapTree も簡単で、引数 node が Lf(x) ならば要素 x に関数 f を適用し、その結果を Lf に格納して返します。Nd の場合、左右の部分木を mapTree で変換し、それを Nd に格納して返します。foldTree は引数 node が Lf(x) ならば要素 x と累積変数 a を関数 f に適用して、その結果を返します。Nd の場合、右部分木を foldTree で畳み込み、その結果を foldTree に渡して左部分木を畳み込みます。
リスト : 二分木の巡回
def preOrder[A](node: Tree2[A]): List[A] =
node match {
case Nils => Nil
case Nd2(x, l, r) => List(x) ::: preOrder(l) ::: preOrder(r)
}
def inOrder[A](node: Tree2[A]): List[A] =
node match {
case Nils => Nil
case Nd2(x, l, r) => inOrder(l) ::: List(x) ::: inOrder(r)
}
def postOrder[A](node: Tree2[A]): List[A] =
node match {
case Nils => Nil
case Nd2(x, l, r) => postOrder(l) ::: postOrder(r) ::: List(x)
}
// 別解
def preOrder1[A](node: Tree2[A]): List[A] = {
def iter(node: Tree2[A], xs: List[A]): List[A] =
node match {
case Nils => xs
case Nd2(x, l, r) => x :: iter(l, iter(r, xs))
}
iter(node, Nil)
}
def inOrder1[A](node: Tree2[A]): List[A] = {
def iter(node: Tree2[A], xs: List[A]): List[A] =
node match {
case Nils => xs
case Nd2(x, l, r) => iter(l, x :: iter(r, xs))
}
iter(node, Nil)
}
def postOrder1[A](node: Tree2[A]): List[A] = {
def iter(node: Tree2[A], xs: List[A]): List[A] =
node match {
case Nils => xs
case Nd2(x, l, r) => iter(l, iter(r, x::xs))
}
iter(node, Nil)
}
二分木の巡回は定義をそのままプログラムしただけです。巡回の定義は拙作のページ「二分探索木」をお読みください。別解は演算子 ::: を使わないバージョンです。左部分木から巡回すると要素が逆順に並ぶので、右部分木から巡回していくことに注意してください。
リスト : 二分木の巡回 (幅優先探索)
def bfs[A](node: Tree2[A]): List[A] = {
def iter(xs: List[Tree2[A]]): List[A] =
xs match {
case Nil => Nil
case Nils::xs => iter(xs)
case Nd2(x, l, r)::xs => x :: iter(xs ::: List(l, r))
case _ => throw new Exception("bfs error")
}
iter(List(node))
}
bfs の実際の処理は局所関数 iter で行います。iter の引数 (リスト) をキューとして使い、二分木の節を追加していくところがポイントです。最初は tree をキューに格納します。最初の節で、引数が空リストになったならば空リストを返します。これが再帰呼び出しの停止条件になります。次の節で、キューの先頭要素が Nils ならば、iter xs を再帰呼び出しします。Nd2 の場合は、キューに左右の節 l, r を追加して iter を再帰呼び出しし、その返り値に要素 x を追加します。
//
// yasp04.scala : Yet Another Scala Problems (4)
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
object yasp04 {
// Q31
// 二分木 Tree の定義
abstract class Tree {
def left: Tree
def right: Tree
}
case class Node(left: Tree, right: Tree) extends Tree
case object Leaf extends Tree {
def left = throw new Exception("Leaf: left is none")
def right = throw new Exception("Leaf: right is none")
}
def treeToKakko(node: Tree): String = {
def iter(node: Tree): String =
node match {
case Leaf => ")"
case Node(l, r) => "(" + iter(l) + iter(r)
}
iter(node).init
}
// Q32
def kakkoToTree(s: String): Tree = {
def iter(xs: List[Char]): (Tree, List[Char]) =
xs match {
case Nil => (Leaf, Nil)
case ')'::xs1 => (Leaf, xs1)
case '('::xs1 => {
val (l, xs2) = iter(xs1)
val (r, xs3) = iter(xs2)
(Node(l, r), xs3)
}
case _ => throw new Exception("kakkoToTree: input error")
}
iter(s.toList)._1
}
// Q33
def kakko(f: String => Unit, n: Int): Unit = {
def iter(x: Int, y: Int, a: String): Unit = {
if (x == n && y == n) f(a)
else {
if (x < n) iter(x + 1, y, a + "(")
if (y < x) iter(x, y + 1, a + ")")
}
}
//
iter(0, 0, "")
}
def trees(f: Tree => Unit, n: Int): Unit = {
kakko((s: String) => f(kakkoToTree(s)), n - 1)
}
// 別解
def trees1(n: Int): List[Tree] = {
def splits(n: Int): List[(Int, Int)] =
for (x <- (1 until n).toList) yield (x, n - x)
def joins(ls: List[Tree], rs: List[Tree]): List[Tree] =
for (l <- ls; r <- rs) yield Node(l, r)
if (n == 1) List(Leaf)
else splits(n).flatMap((x: (Int, Int)) => joins(trees1(x._1), trees1(x._2)))
}
// Q34
// 二分木 Tree1 の定義
abstract class Tree1[A] {
def left: Tree1[A]
def right: Tree1[A]
}
case class Nd[A](left: Tree1[A], right: Tree1[A]) extends Tree1[A]
case class Lf[A](item: A) extends Tree1[A] {
def left = throw new Exception("Lf: left is none")
def right = throw new Exception("Lf: right is none")
}
def makeTree1[A](node: Tree, xs: List[A]): (Tree1[A], List[A]) = {
def iter(node: Tree, xs: List[A]): (Tree1[A], List[A]) =
(node, xs) match {
case (_, Nil) => throw new Exception("makeTree1 error")
case (Leaf, (x::xs)) => (Lf(x), xs)
case (Node(l, r), xs) => {
val (l1, ys) = iter(l, xs)
val (r1, zs) = iter(r, ys)
(Nd(l1, r1), zs)
}
case _ => throw new Exception("makeTree1 error")
}
//
iter(node, xs)
}
// Q35
def splits[A](xs: List[A]): List[(List[A], List[A])] =
xs match {
case Nil => Nil
case x::Nil => List((Nil, List(x)), (List(x), Nil))
case y::ys => (Nil, xs) :: (for ((z, zs) <- splits(ys)) yield (y::z, zs))
}
// Q36
def trees2[A](f: Tree1[A] => Unit, xs: List[A]): Unit = {
trees((node: Tree) => f(makeTree1(node, xs)._1), xs.length)
}
def splits2[A](xs: List[A]): List[(List[A], List[A])] =
xs match {
case Nil | (_::Nil) => Nil
case x::xs => (List(x), xs) :: (for ((ys, zs) <- splits2(xs)) yield (x::ys, zs))
}
def trees3[A](xs: List[A]): List[Tree1[A]] = {
def joins(ls: List[Tree1[A]], rs: List[Tree1[A]]): List[Tree1[A]] =
for (l <- ls; r <- rs) yield Nd(l, r)
//
xs match {
case Nil => throw new Exception("trees3: Empty List")
case x::Nil => List(Lf(x))
case _ => splits2(xs).flatMap((x: (List[A], List[A])) => joins(trees3(x._1), trees3(x._2)))
}
}
// Q37
def treeHeight[A](node: Tree1[A]): Int =
node match {
case Lf(_) => 1
case Nd(l, r) => 1 + (treeHeight(l) max treeHeight(r))
}
def leafCount[A](node: Tree1[A]): Int =
node match {
case Lf(_) => 1
case Nd(l, r) => leafCount(l) + leafCount(r)
}
def memberTree[A](x: A, node: Tree1[A]): Boolean =
node match {
case Lf(y) => x == y
case Nd(l, r) => if (memberTree(x, l)) true else memberTree(x, r)
}
// Q38
def find[A](f: A => Boolean, node: Tree1[A]): Option[A] =
node match {
case Lf(x) => if (f(x)) Some(x) else None
case Nd(l, r) => find(f, l) match {
case None => find(f, r)
case x => x
}
}
def mapTree[A, B](f: A => B, node: Tree1[A]): Tree1[B] =
node match {
case Lf(x) => Lf(f(x))
case Nd(l, r) => Nd(mapTree(f, l), mapTree(f, r))
}
def foldTree[A, B](f: (A, B) => B, a: B, node: Tree1[A]): B =
node match {
case Lf(x) => f(x, a)
case Nd(l, r) => foldTree(f, foldTree(f, a, r), l)
}
// Q39
// 二分木 Tree2 の定義
abstract class Tree2[+A] {
def left: Tree2[A]
def right: Tree2[A]
def item: A
def isEmpty: Boolean
}
case class Nd2[A](item: A, left: Tree2[A], right: Tree2[A]) extends Tree2[A] {
def isEmpty: Boolean = false
}
case object Nils extends Tree2[Nothing] {
def isEmpty: Boolean = true
def left = throw new Exception("left: Empty Tree2")
def right = throw new Exception("right: Empty Tree2")
def item = throw new Exception("item: Empty Tree2")
}
def preOrder[A](node: Tree2[A]): List[A] =
node match {
case Nils => Nil
case Nd2(x, l, r) => List(x) ::: preOrder(l) ::: preOrder(r)
}
def inOrder[A](node: Tree2[A]): List[A] =
node match {
case Nils => Nil
case Nd2(x, l, r) => inOrder(l) ::: List(x) ::: inOrder(r)
}
def postOrder[A](node: Tree2[A]): List[A] =
node match {
case Nils => Nil
case Nd2(x, l, r) => postOrder(l) ::: postOrder(r) ::: List(x)
}
// 別解
def preOrder1[A](node: Tree2[A]): List[A] = {
def iter(node: Tree2[A], xs: List[A]): List[A] =
node match {
case Nils => xs
case Nd2(x, l, r) => x :: iter(l, iter(r, xs))
}
iter(node, Nil)
}
def inOrder1[A](node: Tree2[A]): List[A] = {
def iter(node: Tree2[A], xs: List[A]): List[A] =
node match {
case Nils => xs
case Nd2(x, l, r) => iter(l, x :: iter(r, xs))
}
iter(node, Nil)
}
def postOrder1[A](node: Tree2[A]): List[A] = {
def iter(node: Tree2[A], xs: List[A]): List[A] =
node match {
case Nils => xs
case Nd2(x, l, r) => iter(l, iter(r, x::xs))
}
iter(node, Nil)
}
// Q40
def bfs[A](node: Tree2[A]): List[A] = {
def iter(xs: List[Tree2[A]]): List[A] =
xs match {
case Nil => Nil
case Nils::xs => iter(xs)
case Nd2(x, l, r)::xs => x :: iter(xs ::: List(l, r))
case _ => throw new Exception("bfs error")
}
iter(List(node))
}
}