Comment mettre en miroir un arbre binaire ?

Question

J'ai besoin de créer un arbre binaire en Scala. Je pense que cela doit fonctionner comme suit :

sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A]

def mirrorTree[A](bt: BT[A]): BT[A] = bt match {
  case Empty => Empty
  case Node(root, left, right) => Node(root, right, left)
}

val t = Node(1,Node(2,Empty,Node(3,Empty,Empty)),Empty)
mirrorTree(t)

Je dois appeler la fonction de manière récursive pour les sous-arbres de gauche et de droite, mais je ne sais pas comment faire si je dois retourner l'arbre à partir de la fonction, donc je ne peux pas utiliser des opérateurs comme pour les listes.

Answer 1

Si vous voulez tout refléter, faites-le :

case Node(root, left, right) => Node(root, mirrorTree(right), mirrorTree(left))

Answer 2

Vous étiez très près du but, vous deviez juste appeler la méthode de manière récursive, pour vous assurer que les sous-arbres étaient reflétés avant de construire le reste de l'arbre.

sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A]

def mirrorTree[A](bt: BT[A]): BT[A] = bt match {
  case Empty => Empty
  case Node(root, left, right) => 
    val newLeft = mirrorTree(right) 
    val newRight = mirrorTree(left)
    Node(root, newLeft,newRight)
}

val t = Node(1,Node(2,Empty,Node(3,Empty,Node(4,Empty,Empty))),Empty)

mirrorTree(t)  // Node(1,Empty,Node(2,Node(3,Node(4,Empty,Empty),Empty),Empty))