Conversion de l'arborescence générale en pré-commande pour publication dans Racket

Question

Je suis nouveau sur Racket et j'ai lu de nombreuses pages d'informations, mais j'ai du mal à implémenter un arbre général sous la forme d'une liste de nombres. Si je prends dans l'entrée de l'arbre pré-ordre de stdin:

1 3 
2 2 
5 0 
6 0 
3 1 
7 0 
4 4 
8 0 
9 0 
10 0 
11 1 
12 0 

où le premier numéro représente la valeur du nœud et la deuxième valeur représente le nombre d'enfants du nœud a. J'essaierait de produire mon résultat attendu avant de le convertir en post-ordre:

'(1 (2 (5 6)) (3 (7)) (4 (8 9 10 11 (12)))) 

Jusqu'à présent, je donne les résultats suivants:

(define recurse 0) 

(define (getTreeInfo) 
    (local ((define line (read-line))) 
    (if (eof-object? line) 
     empty 
     (if (= recurse 1) 
      (makeTree (string->number(first (string-split line))) (- (string->number(second (string-split line))) 1)) 
      (makeTree (string->number(first (string-split line))) (string->number(second (string-split line)))))))) 

(define (makeTree value numChildren) 
    (cond 
    [(= numChildren 0) (begin (set! recurse 0) 
           (printf "Recurse: ~a\n" recurse) 
           (cons)] 
    [else (begin (set! recurse 1) 
       (printf "Recurse: ~a\n" recurse) 
       (cons value (getTreeInfo)))])) 

Le code est pas complet ni correct, mais c'est un point de départ de mon processus de réflexion. Des idées pour aborder cette traversée? Je me sens comme la récurrence mutuelle est nécessaire ici.

Answer 1

Je n'arrive pas à comprendre le résultat attendu. Les enfants semblent être la plupart du temps contenus dans des sous-listes, sauf les enfants du noeud 1 qui ne le sont pas, et puisque 11 est un sous-arbre, je pense que cela devrait être (11 (12)). Donc, dans ma tête, un résultat possible pourrait ressembler à '(1 ((2 (5 6)) (3 (7)) (4 (8 9 10 (11 (12)))))), où les enfants de chaque nœud sont dans leur propre liste.

Une version de la fonction getTreeInfo peut prendre un autre argument qui conserve la trace du nombre d'enfants attendus par le nœud actuel, en le décrémentant à chaque étape récursive. Je n'ai pas beaucoup utilisé le schéma, donc je ne suis pas sûr que ce soit idiomatique, mais voici un exemple.

;; IN is input stream, N is number of children remaining for current node 
(define (getTreeInfo in n) 
    (if (zero? n) null      ; no more children, return nil 
     (let ([line (map string->number (string-split (read-line)))]) 
     (cond 
     [(zero? (cadr line)) (list (car line))] ; node has no children 
     [else 
      (let ([children '()]) 
      (for ([_ (in-range (cadr line))]) 
       (set! children (append children (getTreeInfo in 1)))) 
      (cons (list (car line) children) (getTreeInfo in (sub1 n))))])))) 

;; take input from stdin and start N at 1 
(car (getTreeInfo (current-input-port) 1)) 

ligne de commande,

$ racket reorder.rkt < tree.txt 
'(1 ((2 (5 6)) (3 (7)) (4 (8 9 10 (11 (12))))))