Impression d'une arborescence binaire par couche dans une liste

Question

La fonction doit imprimer les marquages ​​de l'arborescence d'arguments dans des couches sous la forme d'une liste de couches. Les marques de nœud et de feuille dans chaque couche sont répertoriées de gauche à droite, c'est-à-dire, qui est le nœud le plus à gauche de la couche, le premier élément de la liste, le nœud le plus à droite est le dernier élément de la liste. L'argument de type Ord indique si les couches dans l'ordre croissant de la plus petite à la plus grande couche (TopDown) ou par ordre décroissant de la plus grande à la plus petite couche (bottomup) doivent être émis

data Tree = Leaf Integer | Node Integer Tree Tree 

type Layer = [Integer] 

data Ord = BottomUp | TopDown 

wLayer :: Tree -> Ord -> [Layer] 

Exemple 1: Nous appelons la fonction wLayer avec des arguments
wLayer (Noeud 1 (Noeud 2 (Feuille 21) (Feuille 22)) (Noeud 3 (Feuille 31) (Feuille 32))) TopDown le résultat: [[1], [2,3 ], [21,22,31,32]]

Exemple 2: wLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) BottomUp le résultat: [[21,22,31,32], [2,3] , [1]]

comment puis-je implémenter celui-ci?

Modifier

data Tree = Leaf Integer 
      | Node Integer Tree Tree 
type Layer = [Integer] 
data Ord = BottomUp | TopDown 

writeLayer :: Tree -> Ord -> [Layer] 
writeLayer Leaf x = [x] 
writeLayer (Node x lt rt) BottomUp = (writeLayer rt BottomUp) ++ [x] ++ (writeLayer lt BottomUp) 
writeLayer (Node x lt rt) TopDown = [x] ++ (writeLayer lt TopDown) ++ (writeLayer rt TopDown) 

c'est mon programme, mais il est fonctionne pas comment puis-je résoudre ce problème?

Answer 1

Voici un moyen simple d'y parvenir. Il prend tous les nœuds à un niveau et en extrait la valeur entière, puis récursive sur tous les enfants de ces mêmes nœuds. Après cela, vous faites correspondre Ord pour déterminer si vous devez inverser la liste.

writeLayer t o = 
    case o of 
     BottomUp -> reverse $ makeLayer [t] 
     TopDown -> makeLayer [t] 
    where 
     extract (Node i _ _) = i 
     extract (Leaf i) = i 
     children (Node _ a b) = [a, b] 
     children _ = [] 
     makeLayer [] = [] 
     makeLayer ts = map extract ts : (makeLayer $ concat $ map children ts) 

Answer 2

Quelques conseils:

• le cas où le Tree est un Leaf est trivial
• la différence entre BottomUp et TopDown semble être si vous inversez la liste des Layer s
• lorsque le Tree est un Node vous devrez récurer sur les sous-arbres et combiner les résultats en quelque sorte

Editer: OK, concentrons-nous sur le premier.

L'équation que vous avez pour ce cas est

writeLayer Leaf x = [x] 

D'abord, les besoins Leaf x être entre parenthèses, car il est une seule valeur Tree.

writeLayer (Leaf x) = [x] 

En second lieu, l'équation doit refléter le fait que writeLayer prend deux paramètres (comme écrit ci-dessus, il faut une seule). Avec une valeur Leaf, peu importe l'ordre dans lequel les résultats doivent être retournés --- nous donnons la même réponse dans les deux cas --- mais nous devons encore prendre le paramètre. Nous utilisons _ pour signaler que nous ne nous soucions pas du paramètre et que nous ne l'utiliserons pas.

writeLayer (Leaf x) _ = [x] 

Troisièmement, [x] est un (seul élément) liste des Integer s --- mais nous sommes censés être retourner une liste de Layer s. Je suis sûr que vous pouvez comprendre comment résoudre ce problème.

Enfin, faites attention aux messages d'erreur que l'ordinateur vous donne. Les comprendre.

Answer 3

c'est mon programme encore

data Tree = Leaf Integer 
    | Node Integer Tree Tree 
type Layer = [Integer] 
data DOrd = BottomUp | TopDown 
writeLayer :: Tree -> DOrd -> [Integer] 
writeLayer (Leaf x) _ = [x] 
writeLayer (Node x lt rt) BottomUp = (writeLayer rt BottomUp) ++ [x] ++ (writeLayer lt BottomUp) 
writeLayer (Node x lt rt) TopDown = [x] ++ (writeLayer lt TopDown) ++ (writeLayer rt TopDown) 

Appels:

*Main> writeLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) TopDown 
[1,2,21,22,3,31,32] 
*Main> writeLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) BottomUp 
[32,3,31,1,22,2,21] 

mais je veux prendre d'abord: [[1], [2,3], [21,22,31, 32]]

seconde: [[21,22,31,32], [2,3], [1]]

Answer 4

La réponse de Paul donne une définition corécursive de la traversée de niveau-ordre - un déploiement aux listes. (Exercice: écrivez makeLayer en utilisant Data.List.unfoldr.) C'est ma façon préférée aussi; voir The Underappreciated Unfold.

Mais cela peut aussi être fait récursivement - comme un pli sur les arbres. Ceux-ci sont définis par analogie avec foldr sur les listes comme suit:

foldt :: (Integer->a) -> (Integer->a->a->a) -> Tree -> a 
foldt f g (Leaf n)  = f n 
foldt f g (Node n t u) = g n (foldt f g t) (foldt f g u) 

Ensuite, le niveau d'ordre traversal est donnée par un pli d'arbre simple, avec un possible reverse:

wLayer :: Tree -> Order -> [Layer] 
wLayer t o = (if o==BottomUp then reverse else id) (foldt single glue t) 

Je pris la liberté de rebaptiser votre type de drapeau Order à un vide, un clash nom, et ce qui en fait une instance de Eq:

data Order = BottomUp | TopDown deriving Eq 

Le foncti sur single rend le traversal niveau d'ordre d'une feuille:

single :: Integer -> [Layer] 
single n = [[n]] 

alors glue combine une étiquette et les traversals de deux enfants dans la traversée d'un noeud:

glue :: Integer -> [Layer] -> [Layer] -> [Layer] 
glue n x y = [n] : longzipwith (++) x y 

L'ingrédient essentiel est une fonction longzipwith, qui est comme zipWith sauf que (i) la longueur du résultat est la longueur de l'argument le plus long, pas le plus court, et donc (ii) l'opérateur binaire doit être :

longzipwith :: (a->a->a) -> [a] -> [a] -> [a] 
longzipwith f (a:x) (b:y) = f a b : longzipwith f x y 
longzipwith f x  [] = x 
longzipwith f [] y  = y