有什么方法可以使用递归宽度优先实现来创建二叉树的副本？

Question

本质上讲，我试图做的是采取与数据定义

binary_tree: number | (symbol binary_tree binary_tree) 

二叉树和创造，每个叶片（数字）替换为计数器的号树的新版本。我试图从左到右，然后从上到下这样做，所以使用宽度优先搜索似乎是按顺序访问每个节点的明显选择。但是，我的问题是这样的。我需要积累一个新的二叉树来返回它。因为我们正在访问每个节点，是否有任何可能的方法来做到这一点？

因此，在短期，如果我有一棵树定义是这样的：

(define bt '(foo (bar 26 12) (baz 11 (quux 117 14)))) 

我需要处理和积累新的列表，使得

(define bt '(foo (bar 0 1) (baz 2 (quux 3 4)))) 

这里是我的代码：

(define (number-leaves bst) 
    (define (helper queue counter) 
    (cond[(non-empty-queue? queue) 
       (define x (dequeue! queue)) 
       (cond [(number? x)(cons counter (helper queue (+ 1 counter)))] 
        [(symbol? (car x))(begin (enqueue! queue (car(cdr x))) 
              (enqueue! queue (car(cdr(cdr x)))) 
              (cons (list(car x)) (helper queue counter)))])] 
     ['()])) 
    (begin (define q (make-queue)) 
     (enqueue! q bst) 
     (helper q 0))) 

截至目前此功能返回

(foo bar baz 0 1 2 quux 3 4) 

在我看来，在首先处理树宽度时，不可能积累到递归数据定义中。我能做什么？ （NB：car = first和cdr = EOPL球拍方言中的休息）

Answer 1

我认为你需要做两次传球。

1. 基于持有树叶的叶子及其增量新值进行查找时首先呼吸。使用对因为自己的号码不保证唯一的，因此(eq? 2 2)可以#t，即使他们有不同的地方..相比保持了三三两两保证是唯一的eq?有非常相同的值对是非常重要的。

2. 标准后期订单树遍历，您从查找中获取新值。

该查找应该是效率的散列，但它可以是小树的关联列表。如果你希望散列做O（1）遍历整个元素两次仍然只会使它O（n）。