使用Scheme实现B+树元素查找的问题求助

需求 #

遍历B+树结构，遇到子列表则递归处理直至获取数值元素；将元素与给定数字比较，可忽略超出范围的分支，实现通用的元素查找功能。

初始代码与问题 #

用户编写的初始Scheme代码：

(define ones (list '() 2 '() 4 '() 6 '() 7 '() 8 '()))
(define sixties (list '() 52 '() 54 '() 66 '() 67 '() 68 '()))
(define tens (list ones 10 '() 30 '() 50 sixties 70 '() 90 '()))
(define ninehundreds (list '() 930 '() 940 '() 960 '() 970 '() 988 '()))
(define tree (list tens 100 '() 300 '() 500 '() 700 '() 900 ninehundreds ))

(define (walk tree num)
   (if list? (car tree)
       (walk-list (car tree)))

  (if (not list? (car tree)))
       walk-list( cdr tree)
)

(define (walk-list lst)
  (if (list? (car lst)) (walk-list (car lst)))
  (if (not (list? (car lst))) (car lst))
)
(walk tree 0)

初始问题：两个函数中的if语句存在语法错误（缺少括号、分支逻辑混乱），执行后曾返回布尔值#t，未实现预期查找功能。

修复语法后的代码与当前错误 #

修复语法后的代码：

(define (walk tree num)
   (if (list? (car tree))
       (walk-list (car tree))
       (car tree))
)

(define (walk-list lst)
  (if  (list? (car lst))
    (walk-list (car lst))
    (car lst))
)

当前执行报错：

mcar: contract violation
  expected: mpair?
  given: ()

报错原因是代码未处理**空列表()**的情况，当递归到空列表时调用(car lst)，违反了car只能作用于非空配对的合约。

完整解决方案 #

要实现需求，需要：

• 增加空列表的判断，避免调用car时出错；
• 加入数值比较逻辑，忽略超出目标数字范围的分支；
• 递归遍历所有有效分支，收集符合条件的元素。

最终实现代码：

(define ones (list '() 2 '() 4 '() 6 '() 7 '() 8 '()))
(define sixties (list '() 52 '() 54 '() 66 '() 67 '() 68 '()))
(define tens (list ones 10 '() 30 '() 50 sixties 70 '() 90 '()))
(define ninehundreds (list '() 930 '() 940 '() 960 '() 970 '() 988 '()))
(define tree (list tens 100 '() 300 '() 500 '() 700 '() 900 ninehundreds ))

(define (walk-btree tree target)
  ; 处理空树的情况
  (if (null? tree)
      '()
      (let ((node (car tree)))
        (cond
          ; 如果当前节点是子树，递归遍历
          ((list? node)
           (append (walk-btree node target)
                   (walk-btree (cdr tree) target)))
          ; 如果当前节点是数值，判断是否符合范围（示例为 >= target，可按需调整）
          ((number? node)
           (if (>= node target)
               (cons node (walk-btree (cdr tree) target))
               (walk-btree (cdr tree) target)))
          ; 空列表直接跳过，继续遍历后续节点
          ((null? node)
           (walk-btree (cdr tree) target))
          ; 其他类型节点直接跳过
          (else
           (walk-btree (cdr tree) target))))))

; 示例调用：查找所有 >= 50 的元素
(walk-btree tree 50)
; 预期输出：(52 54 66 67 68 50 100 300 500 700 900 930 940 960 970 988)

代码说明 #

• 新增null?判断，处理空列表和空树的情况，避免car调用错误；
• 使用cond分支清晰区分不同节点类型（子树、数值、空列表）；
• 内置数值比较逻辑（示例为筛选大于等于目标值的元素），可根据需求修改比较条件；
• 通过append和cons收集符合条件的元素，返回结果列表；
• 递归遍历所有有效分支，自动跳过空列表等无效节点。

内容的提问来源于stack exchange，提问作者EliOne