予約注文の一般的なツリーをラケットに投稿する

Question

私はラケットを初めて使いました。多くのウェブページを読みましたが、数字のリストとして一般的なツリーを実装するのに問題があります。 私は、標準入力から次の予約注文の木の入力に取っていた場合：

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

最初の数はノードとの値を表し、第二の値は、ノードがを持っている子供の数を表します。 私のようにポスト・オーダーに変換する前に、私の予想結果を生成しようとしていることになります。これまでのところ、私は以下のいる

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

：

(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)))])) 

をコードが完全でも正確ではありませんが、それは私の思考プロセスの出発点です。 このトラバーサルにアプローチする方法はありますか？私はここで相互再帰が必要だと感じています。

Answer 1

私は期待した結果をかなり理解できません。子どもはサブリスト内にほとんど含まれているように見えますが、ノード1の子はありません。11はサブツリーであるため、(11 (12))である必要があります。したがって、私の頭の中で、可能な結果は'(1 ((2 (5 6)) (3 (7)) (4 (8 9 10 (11 (12))))))のように見え、各ノードの子はそれぞれのリストにあります。

getTreeInfo関数のバージョンは、現在のノードが何個多くの子孫が予期しているかを追跡する別の引数を取ることができ、各再帰的なステップでそれを減らします。私は多くのスキームを使用していないので、私はこれが慣用的であるかどうかはわかりませんが、ここに例があります。

コマンドラインから

;; 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)) 

、

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