Бинарное дерево складное

Мне дали следующее определение бинарного дерева

abstract class Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

и следующая функция

def fold_tree[A,B](f1: A => B)(f2: (A, B, B) => B)(t: Tree[A]): B = t match {
    case Leaf(value) => f1(value)
    case Node(value, l, r) => f2(value, fold_tree(f1)(f2)(l), fold_tree(f1)(f2)(r)) //post order
  }

Меня попросили вернуть самое правильное значение в дереве, используя метод сгиба. Как это будет работать? Я не уверен, что полностью понимаю сгиб, но я думал, что смысл сгиба состоит в том, чтобы выполнить некоторую операцию с каждым элементом дерева. Как я могу использовать его, чтобы просто вернуть самое правильное значение дерева?

Я также не уверен, как вызвать метод. Я продолжаю получать проблемы с неопределенным типом параметра. Может кто-нибудь показать мне правильный способ вызова этого метода fold_tree?

Источник

2 ответа

Решение

Как это будет работать? Я не уверен, что полностью понимаю сгиб

Что твое foldTree Метод делает это рекурсивно ходить по дереву, применяя себя к каждому Node или же Leaf это встречается на пути. Метод также имеет два типа параметров, которые должны быть применены, A а также Bв зависимости от типа предоставляемого дерева.

Давайте для примера скажем, у нас есть Tree[Int] определяется так:

val n = Node(1, Leaf(2), Node(3, Leaf(5), Node(4, Leaf(42), Leaf(50))))

Дерево имеет структуру, которая выглядит следующим образом:

дерево

Мы хотим получить наиболее правильное значение, которое составляет 50. Для того, чтобы сделать это с текущей реализацией foldTreeНам нужно предоставить два метода:

  1. f1: A => B: Учитывая A, проект B значение
  2. f2: (A, B, B) => B: Данный A и два B ценности, проект B,

Мы это видим f1 применяется над Leaf, а также f2 применяется над Node (отсюда разное количество элементов, предоставляемых каждому методу). Так что это дает нам понять, что функции, которые мы предоставляем foldTree будет применяться к каждому, соответственно.

Упакованный с этим знанием, учитывая наше дерево:

val n = Node(1, Leaf(2), Node(3, Leaf(55), Node(4, Leaf(42), Leaf(50))))

Мы предоставляем следующий метод:

println(foldTree[Int, Int](identity)((x, y, z) => z)(n))

Это означает следующее:

  1. Если мы столкнемся с Leaf узел и карту над ним (применяя f1 на это), мы просто хотим извлечь его ценность.
  2. При встрече с Node элемент (и применение f2 к нему), мы хотим взять самый правый элемент, который проецируется третьим элементом z в нашем методе.

Выполнение этого дает ожидаемый результат: 50,

Если мы хотим расширить это в общем для любого A, мы можем сказать:

def extractRightmostValue[A](tree: Tree[A]) =
  foldTree[A, A](identity)((x, y, z) => z)(tree)
Источник 
fold_tree[A,A](identity)((_,_,z) => z)(t)

Это должно работать, потому что метод принимает тип A и возвращает тип A. Он сообщает методу, если мы находимся на листе, просто возвращаем значение листьев. Если у нас есть узел, левое дерево и правое дерево, вернуть значение правого дерева.

Источник
Другие вопросы по тегам