在球拍中将预定的通用树转换为post

Question

我是新手，我读过很多网页上的信息，但我在实现一个通用树作为一个数字列表列表时遇到了困难。如果我从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

其中，第一个数字表示该节点的值，而第二个值表示该节点的子节点数。在将预期结果转换为“后序”之前，我会尝试这样做：

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