有什麼方法可以使用遞歸寬度優先實現來創建二叉樹的副本？

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）。