Désérialiser une arborescence binaire en premier dans la programmation fonctionnelle

Tout d'abord, vous pouvez utiliser une classe de cas pour simplifier votre classe d'arbre, et vous devez utiliser Option au lieu de null :

private def buildTree(row: Int, col: Int, map: Map[(Int, Int), Int]): Option[Tree] = {
  map.get((row, col)).map{value =>
    Tree(value, buildTree(row + 1, col * 2, map), buildTree(row + 1, col * 2 + 1, map))
  }
}

Ensuite, le principal problème ici est que votre arbre est immuable, il doit être construit avec un parcours post-ordre en profondeur d'abord, et votre format de sérialisation nécessite un parcours d'ordre de niveau en largeur premier. Vous devez donc d'abord désérialiser en une structure de données qui peut ensuite être parcourue dans le premier ordre en profondeur. Ce qui suit utilise une carte de (ligne, colonne) à la valeur du nœud:

@scala.annotation.tailrec
private def bfsTraverse(
    serialized: List[Option[Int]],
    queue: Queue[(Int, Int)],
    map: Map[(Int, Int), Int]): Map[(Int, Int), Int] = {
  val ((row, col), queueTail) = queue.dequeue
  if (serialized.isEmpty) {
    map
  } else if (serialized.head.isEmpty) {
    bfsTraverse(serialized.tail, queueTail, map)
  } else {
    val newQueue = queueTail.enqueueAll(List((row + 1, col * 2), (row + 1, col * 2 + 1)))
    val newMap = map + ((row, col) -> serialized.head.get)
    bfsTraverse(serialized.tail, newQueue, newMap)
  }
}

Vous pouvez maintenant utiliser la sortie de cette fonction pour construire votre Tree code >:

case class Tree(value: Int, left: Option[Tree], right: Option[Tree])

Cette solution est un peu verbeuse mais utilise certains concepts fonctionnels et définit minutieusement les structures de données.

• L'algorithme que vous avez fourni fonctionne mieux avec les nœuds mutables. Il est possible d'avoir une solution plus courte avec une seule classe mutable, mais ici, il existe deux versions (une classe de nœuds avec mutable gauche / droite et l'autre complètement immuable).
Les
• Les classes de cas fournissent automatiquement de nombreuses fonctionnalités utiles telles que comparaison et impression conviviale
• La fonction processValues ​​ exécute de manière récursive les tâches équivalentes à la fonction makeTree que vous avez fournie.
• L'annotation @tailrec indique le compilateur pour vérifier que la fonction est récursive en queue.
• La correspondance de modèle à l'aide des mots clés match et case remplace la vérification de la nullité ou de sous-types différents, et le compilateur peut rechercher une clause de correspondance non exhaustive.
• Le trait App vous permet de créer facilement un objet (classe statique) dans un point d'entrée pour exécuter quelques exemples.

import scala.annotation.tailrec

sealed trait TreeNode[T]
sealed trait MutableTreeNode[T]
object MutableTreeNode {
  final case class Empty[T]() extends MutableTreeNode[T]
  case class Branch[T](val value: T) extends MutableTreeNode[T] {
    protected var left: MutableTreeNode[T] = Empty()
    protected var right: MutableTreeNode[T] = Empty()
    def setLeft(newLeft: T): Branch[T] = {
      left = Branch(newLeft)
      left.asInstanceOf[Branch[T]] // shouldn't be necessary but compiler requires it
    }
    def setRight(newRight: T): Branch[T] = {
      right = Branch(newRight)
      right.asInstanceOf[Branch[T]]
    }
    override def toString: String = this.toImmutable().toString

    /* converts given node to immutable version */
    private def toImmutable(node: MutableTreeNode[T]): TreeNode[T] = {
      node match {
        case Empty() => TreeNode.Empty()
        case b@Branch(value) => TreeNode.Branch(value, toImmutable(b.left), toImmutable(b.right))
      }
    }
    def toImmutable():TreeNode[T] = toImmutable(this)
  }

  /**
    * Modifies nodes inside of queue
    */
  @tailrec def processValues[T](values: Seq[Option[T]], queue: Seq[MutableTreeNode.Branch[T]]): Unit = {
    (queue, values) match {
      case (Nil, _) => ()
      case (_, Nil) => ()
      case (qHead :: qTail, Some(vLeft) :: Some(vRight) :: vTail) =>
        processValues(vTail, qTail :+ qHead.setLeft(vLeft) :+ qHead.setRight(vRight))
      case (qHead :: qTail, Some(vLeft) :: None :: vTail) =>
        processValues(vTail, qTail :+ qHead.setLeft(vLeft))
      case (qHead :: qTail, None :: Some(vRight) :: vTail) =>
        processValues(vTail, qTail :+ qHead.setRight(vRight))
      case (qHead :: qTail, None :: None :: vTail) =>
        processValues(vTail, qTail)
    }
  }
}
object TreeNode {
  final case class Empty[T]() extends TreeNode[T]
  final case class Branch[T](value: T, left: TreeNode[T], right: TreeNode[T]) extends TreeNode[T]

  def deserialize[T](values: Seq[Option[T]]): TreeNode[T] = {
    values match {
      case Some(headVal) :: tail =>
        val root: MutableTreeNode.Branch[T] = MutableTreeNode.Branch(headVal)
        MutableTreeNode.processValues(tail, Seq(root))
        root.toImmutable()
      case Nil => Empty()
      case _ => throw new RuntimeException("Invalid argument values")
    }
  }
}

object TreeNodeTest extends App {
  val input = Seq(Some(5), Some(4), Some(7), None, None, Some(2), None)
  val treeNode:TreeNode[Int] = TreeNode.deserialize(input)
  println(treeNode)
}

Comme cela a été noté, Scala évite null autant que possible, préférant Option pour indiquer l'absence de valeur.

Les variables mutables sont également évitées, ce qui la rend beaucoup plus facile de construire un arbre B en profondeur plutôt qu'en largeur en premier.

Donc, tout ce dont vous avez vraiment besoin est une sérialisation en largeur en premier facile à utiliser --to -> traducteur profondeur-première-sérialisation.

Je l'ai fait en deux étapes.

Tree.fromBFS(Vector(Some('A'),None,Some('B'),Some('C'))).get
//res0: Tree[Char] = Tree(A,None,Some(Tree(B,Some(Tree(C,None,None)),None)))

Maintenant paramétrons l'arborescence pour que nous puissions construire Int arbres, Float arbres, String arbres, etc.

Nous allons également rendre le constructeur privé code> pour que la création de nœuds se fasse uniquement via des méthodes d'usine.

object Tree {
  private def BFS2full[A]( . . . //as above 
  private def toDFS[A]( . . . //as above

  def fromDFS[A](dfs :IterableOnce[Option[A]]) :Option[Tree[A]] = {
    val itr = dfs.iterator
    def loop(): Option[Tree[A]] =
      Option.when(itr.hasNext)(itr.next())
            .flatten
            .map(new Tree(_,loop(),loop()))
    loop()
  }
  def fromBFS[A](bfs:IndexedSeq[Option[A]]) :Option[Tree[A]] =
    fromDFS(toDFS(BFS2full(bfs)))
}

Il ne reste plus qu'à fournir les méthodes d'usine.

case class Tree[A] private (value : A
                           ,left  : Option[Tree[A]]
                           ,right : Option[Tree[A]])

test :

//from Breadth-First-Serialization to full tree representation
def BFS2full[A](bfs:IndexedSeq[Option[A]]) :List[List[Option[A]]] = {
  val bfsLen = bfs.length
  if (bfs.isEmpty) Nil
  else
    List(bfs.head) :: List.unfold((List(bfs.head),1)){case (pr,idx) =>
      Option.when(bfsLen > idx){
        val ns = pr.foldLeft((List.empty[Option[A]],idx)){
          case ((acc,x), None) => (acc ++ List(None,None), x)
          case ((acc,x), _) => (acc ++ List(bfs.lift(x).flatten
                                           ,bfs.lift(x+1).flatten), x+2)
        }
        (ns._1, ns)
      }
    }
}

//from full tree representation to Depth-First-Serialization
def toDFS[A](lloa :List[List[Option[A]]]
            ,lvl :Int = 0) :List[Option[A]] = lloa match {
  case Nil => List(None, None)
  case List(None) :: Nil => List(None)
  case List( oa ) :: tl  => oa :: toDFS(tl, lvl)
  case row :: tl => row.drop(lvl*2) match {
    case List(None,None,_*) => List(None, None)
    case List(None, ob ,_*) => None :: (ob::toDFS(tl,2*lvl + 1))
    case List( oa ,None,_*) => (oa::toDFS(tl,2*lvl)) ++ List(None)
    case List( oa , ob ,_*) => (oa :: toDFS(tl, 2*lvl)) ++
                                (ob :: toDFS(tl,2*lvl + 1))
  }
}

Voici une solution de base. Il n'utilise pas de valeurs paresseuses ou de structures de données autres que Liste , Option et Soit . Vous trouverez peut-être plus facile à comprendre à cause de cela ou plus difficile à cause de la verbosité.

J'ai défini Tree comme ceci, juste pour rendre les choses plus faciles.

def makeTree[T](list: List[Option[T]]): Tree[T] = {
  def helper(f: RecFun[T], l: List[Option[T]]): Tree[T] =
    f(l) match {
      case (_, Right(tree)) => tree
      case (next, Left(f))  => helper(f, next)
    }

  list match {
    case Some(x) :: tail => helper(createRec(x), tail)
    case _               => Empty
  }
}

def createRec[T](data: T): RecFun[T] = {
  case None :: Nil | Nil => (Nil, Right(Node(data, Empty, Empty)))
  case Some(l) :: Nil => (Nil, Right(Node(data, Node(l, Empty, Empty), Empty)))
  case lo :: ro :: rest =>
    (rest, (lo, ro) match {
      case (Some(l), Some(r)) =>
        Left(waitForChildren(data, createRec(l), createRec(r)))
      case (Some(l), None) =>
        Left(waitForChild(Node(data, _, Empty), createRec(l)))
      case (None, Some(r)) =>
        Left(waitForChild(Node(data, Empty, _), createRec(r)))
      case (None, None) => Right(Node(data, Empty, Empty))
    })
  }

def waitForChildren[T](data: T, leftF: RecFun[T], rightF: RecFun[T]): RecFun[T] =
  input => {
    val (next, res) = leftF(input)
    res match {
      case Right(tree) =>
        (next, Left(waitForChild(Node(data, tree, _), rightF)))
      case Left(leftF2) => {
        val (next2, res2) = rightF(next)
        (next2, Left(res2 match {
          case Right(tree)   => waitForChild(Node(data, _, tree), leftF2)
          case Left(rightF2) => waitForChildren(data, leftF2, rightF2)
        }))
      }
    }
  }

def waitForChild[T](ctor: Tree[T] => Node[T], f: RecFun[T]): RecFun[T] =
  input => {
    val (next, res) = f(input)
    (next, res match {
      case Right(tree)  => Right(ctor(tree))
      case Left(recFun) => Left(waitForChild(ctor, recFun))
    })
  }