在二叉樹方案中查找列表2

Question

在Scheme中編寫一個函數，該函數接收學生作爲輸入參數列表的cedulas（標識符），一個帶有學生結構實例的二叉查找樹並返回學生結構實例列表，學生列表的標識在二叉搜索樹中。

例如：

這是二叉樹

(make-árbol-bin 
(make-estudiante 5 "35889188" "Victor" (make-fecha 10 6 1991) "calle 67 con cra 20" "4444444") (make- 
árbol-bin 
(make-estudiante 2 "6457234" "Manuel" (make-fecha 12 10 1992) "calle 56 con cra 33" "5555555") (make-árbol-bin 
    (make-estudiante 1 "94252688" "Estela" (make-fecha 20 5 1993) "calle 4 con cra 2" "3333333") empty empty) empty) 
(make-árbol-bin 
(make-estudiante 7 "34987678" "Juan" (make-fecha 25 3 1995) "calle 34 con cra 12" "6666666") empty 
empty) 
) 

列表標識

(list "94252688" "94888888") 

它應該返回下面的列表：

(list (make-estudiante 1 "94252688" "Estela" (make-fecha 20 5 1993) "calle 4 con cra 2" "3333333")) 

，我這樣做，但我不能讓我返回列表

(define-struct fecha (dia mes año)) 

這是學生的結構：

(define-struct estudiante (codigo id nombre fechanaci direccion telefono)) 

這是二叉搜索樹的結構：

(define-struct arbol-bin(estudiante nod-izq nod-der)) 

這些都是搜索樹中列表的函數

(define(buscarevd n E) 
(cond 
[(or(empty? E) (empty? n))false] 
[(equal? (first n)(estudiante-id E)) true] 
[else (buscarevd (rest n) E)])) 

(define(buscare n E) 
(cond 
[(empty? E)false] 
[(< (car n)(estudiante-id E)) true] 
[else false])) 


(define (member-bt x bt) 
(cond 
[(empty? bt) false] 
[(or(buscarevd x (arbol-bin-estudiante bt)) 
[else 
(member-bt x (arbol-bin-nod-der bt))])) 

這

(member-bt (list "94252688" "94888888") tree) 

回報

true 

正如我可以做，使我回到了名單。

Answer 1

不知道是否有某種這將允許你在這裏跳過子樹節點之間的關係，所以我會用這種方法：

(define (member-bt lst tree) 
    (let loop ((tree tree) (res '())) 
    (if (null? tree) 
     res 
     (let* ((node (árbol-bin-estudiante tree)) 
       (res1 (loop (árbol-bin-nod-der tree) res)) 
       (res2 (loop (árbol-bin-nod-izq tree) res1))) 
      (if (member (estudiante-id node) lst string=?) 
       (cons node res2) 
       res2))))) 

然後

(let ((lst '("94888888" "34987678" "94252688"))) 
    (let ((res (member-bt lst tree))) 
    (values res (map estudiante-nombre res)))) 
=> 
'(#<estudiante> #<estudiante>) 
'("Estela" "Juan") 

請注意，這隻會遍歷樹一次，但結果列表中學生的順序與初始列表中的順序不同。如果爲了需要保留的，你需要採取不同的方法，例如：

(define (member-bt-ordered lst tree) 
    (define (sub e tree) 
    (if (null? tree) 
     #f 
     (let ((node (árbol-bin-estudiante tree))) 
      (if (string=? e (estudiante-id node)) 
       node 
       (or (sub e (árbol-bin-nod-der tree)) 
        (sub e (árbol-bin-nod-izq tree))))))) 
    (filter values (map (lambda (e) (sub e tree)) lst))) 

然後

(let ((lst '("94252688" "94888888" "35889188" "34987678" "6457234"))) 
    (let ((res (member-bt-ordered lst tree))) 
    (values res (map estudiante-nombre res)))) 
=> 
'(#<estudiante> #<estudiante> #<estudiante> #<estudiante>) 
'("Estela" "Victor" "Juan" "Manuel")