Создание очень простого двоичного дерева в Scala

Question

Я пытаюсь создать очень простое двоичное дерево в Scala для хранения и обхода данных.

Прямо сейчас у меня есть:

trait Tree 
case class Node(left: Tree, value: String, right: Tree) extends Tree 

Мои вопросы:

1. Как можно также включать в себя указатель на родителя?

2. Могу ли я иметь левую и правую точку в нуле? Или родительский указатель для корневого узла?

3. Как я могу на самом деле пересечь дерево?

4. Легко ли обновлять значения узла?

Answer 1

1. Не с неизменяемых классов случае. Это циклическая зависимость: вам нужен родительский элемент для создания дочерних элементов, но вам также нужны дети для создания родителя. С другой стороны, большинству алгоритмов обхода дерева действительно не нужен родительский элемент, поскольку родительский элемент обычно находится в стеке или может быть где-то сохранен.

2. Да, мы, как правило, представляют их с одноплодной инстанции (object) признака:

   case object EmptyNode extends Tree 
   

3. Есть много алгоритмов там, поиск в ширину и глубиной первого поиска являются наиболее распространенными , Это хорошее упражнение для их реализации. Но немного помощи со стороны Scala, мы обычно картина матча на left и right увидеть, что нам нужно делать дальше:

   tree: Tree match { 
       case EmptyNode => // do nothing, return, etc. 
       case Node(left, value, right) => 
       // Do inorder, preorder, postorder operation order 
       // You will also probably be processing left and right as well 
   } 
   

4. Нет, ваше предположение верно, что использование неизменяемых классов регистра в дереве довольно сложно обновить, потому что, если вы обновляете листовой узел, вы должны воссоздать все выше него. Есть так называемые библиотеки Lenses и Lens, которые могут помочь вам в этом, хотя они могут быть немного более продвинутыми. Один популярный в Скале - Monocle.

---

Похоже, вы только начинаете с программированием или новой для Scala, поэтому я бы рекомендовал использовать var -s вместо val с:

case class Node(var left: Tree, var value: String, var right: Tree) extends Tree 

Кроме того, если ваши черты уплотняются (sealed trait Tree), тогда компилятор скажет вам, не обработал ли вы один из подтипов в совпадении с шаблоном.

EDIT:

На основе комментариев начать работать с этим:

sealed trait Tree 
case class Node(var left: Tree, var value: String, var right: Tree, var parent: Tree) extends Tree 
case object EmptyNode extends Tree 

Answer 2

В случае полезно для программистов с необходимостью для бинарных объектов дерева, я написал некоторые Scala черты, которые могут быть унаследованным и/или смешанным, чтобы обеспечить базовую функциональность Red-Black tree, а также некоторые другие древовидные алгоритмы:

http://erikerlandson.github.io/blog/2015/09/26/a-library-of-binary-tree-algorithms-as-mixable-scala-traits/