Racket：在二叉树中搜索和替换

Question

代码的目标是搜索键 (k)，如果找到，则将值替换为 v。

(define-struct node (key value left right))

(define (insert k v tree)
  (cond
    [(empty? tree) (list k v) ]
    [(equal? (node-key tree) k) 
     (make-node  k v (insert k v (node-left tree))
                 (insert k v (node-right tree)))]
    [else (make-node (node-key tree) (node-value tree) 
                     (insert k v (node-left tree)) (insert k v (node-right tree)))])) 

(define sample (make-node 2 "two"
                          (make-node 1 "one" empty empty)
                          (make-node 3 "three" empty empty)))

样本和 1 "hello" 的输出应该是

(make-node 2 "two"
           (make-node 1 "hello" empty empty)
           (make-node 3 "three" empty empty))

而是

(make-node 2 "two"
           (make-node 1 "hello"
                      (list 1 "hello")
                      (list 1 "hello"))
           (make-node 3 "three"
                      (list 1 "hello")
                      (list 1 "hello")))

有什么建议可以使输出符合要求吗？

Answer 1

这里

[(empty? tree) (list k v)]

您正在用一个非空列表替换每个不存在的子树，如这个小测试所示：

> (insert 1 "how" empty)
'(1 "how")

应该是

[(empty? tree) empty]

Racket：在二叉树中搜索和替换

Racket: search and replace in a binary tree

search

tree

scheme

binary-tree

racket