1

我正在尝试解决一个难题，即爬取二叉树以查找特定值是否作为节点存在。我在评估一对看起来像'(1 '()). 我认为当我评估(= 4 '())它时返回true，这显然是不正确的。

我尝试删除cons添加空对的，但是我现在得到以下内容： (#f . #f)我相信它不是一对。我对如何通过cons.

我的代码如下：

我的自制any?功能

(define (any? f lst) (not (null? (filter f lst))))

带有 with 的cons版本'()：

(define value-exist? 
  (lambda (n xs)
    (if (null? xs) 
        '()
        (letrec ((node-left (car xs))
                 (node-right (cdr xs))
                 (true? (lambda (x) x)))
          (if (list? node-left) 
              (any? true? (cons (value-exist? n node-left) 
                                (cons (value-exist? n node-right) 
                                      '())))
              (any? true? (cons (= n node-left) 
                                (cons (value-exist? n node-right) 
                                      '()))))))))

我删除conswith的版本'()：

(define value-exist? 
  (lambda (n xs)
    (if (null? xs) 
        '()
        (letrec ((node-left (car xs))
                 (node-right (cdr xs))
                 (true? (lambda (x) x)))
          (if (list? node-left) 
            (any? true? (cons (value-exist? n node-left) 
                              (value-exist? n node-right)))
            (any? true? (cons (= n node-left) 
                              (value-exist? n node-right)))
                              )))))

示例调用：

(value-exist? 4 '(1 2 3 (3 2 3)))
4

4 回答 4

2

  1. (#f . #f)是一对完全有效的好对。它car是第一#f，它cdr是第二#f。

  2. “如何通过 cons 建立一个配对列表。” A pair is a consof itscar和 its cdr：

    (cons 1 2) ==> (1 . 2)。

    列表中的最后一对()具有cdr：

    (cons (cons 1 2) ()) ==> ((1 . 2))

    (cons (cons 1 2) (cons (cons 3 4) ())) ==> ((1 . 2) (3 . 4))

  3. 缺少那个any?功能。好的实施必须尽快停止：

    (define (any? f lst)
    (and (not (null? lst))
         (pair? lst)
         (or (f (car lst))
             (any? f (cdr lst)))))

    但我们这里不需要它。

  4. 在嵌套列表（又称二叉树）中查找元素的最常用方法是使用car-cdr recursion。应注意正确处理()列表中的元素。我们也可以允许列表/对作为值（不仅仅是原子）：

    (define (present? x ls)
   (and (pair? ls)
        (or (equal? x (car ls))
            (and (not (null? (cdr ls)))   ; not an artificial () sentinel
                 (equal? x (cdr ls)))
            (present? x (car ls))
            (present? x (cdr ls)))))

    这个函数是高度递归的。(present? () '(1 () 2))返回#t。

于 2013-07-11T20:50:02.397 回答
1

解决编程问题，方法＃1：a）从一些低级抽象开始，b）考虑高级问题，c）根据低级抽象实现高级问题，d）如果不是' c'，然后 i) 从顶部向下构建一层或 ii) 从底部向上构建另一层，并且 iii) 重复

因此对于低级

(define (make-node value left right)
  `(NODE ,value ,left ,right))
(define node-value cadr)
(define node-left  caddr)
(define node-right cadddr)
(define (node? thing)
  (and (list? thing) (= 4 (length thing)) (eq? 'NODE (car thing)))

(define (make-leaf-node value)
  (make-node value #f #f))

然后是高层：

(define (node-has-value? value node)
  (and node (or (= value (node-value node))
                (node-has-value? value (node-left  node))      ; assume node not sorted...
                (node-has-value? value (node-right node)))))
于 2013-07-11T19:58:45.393 回答
0

我更喜欢 Go 的答案，因为它是一个支持对作为叶子值的实际二叉树。这是我的看法：

#lang racket

(define tree? pair?)
(define left-node car)
(define right-node cdr)
(define make-tree cons)
(define make-leaf identity) ; a little redundant?
(define leaf-eqv? eqv?)

(define (value-exists? value node)
  (if (tree? node)
      (or (value-exists? value (left-node node))
          (value-exists? value (right-node node)))
      (leaf-eqv? value node)))

;; A tree defined like this cannot contain pairs as leaf. Only atomic values.
(define tree 
  (make-tree (make-tree 4 
                        (make-tree #f null)) ;; null is the value of the node. 
             (make-tree "test"
                        'wer)))

(value-exists? "test" tree)   ; ==> #t
(value-exists? 4 tree)        ; ==> #t
(value-exists? null tree)     ; ==> #t
(value-exists? 'hello tree)   ; ==> #f
于 2013-07-11T21:19:05.880 回答
0

您的代码不遵循递归遍历列表列表的解决方案模板（示例输入和过程似乎都没有处理实际的二叉树），尝试修复当前解决方案毫无意义。相反，我将向您展示正确的配方：

(define (value-exist? n xs)
  (cond ((null? xs) ; check if the list is empty
         #f)        ; if it's empty, then we didn't find what we were looking for
        ((not (pair? xs)) ; check if the current element is not a list
         (equal? n xs))   ; if it's not a list, check if it's the element
        (else                              ; otherwise
         (or (value-exist? n (car xs))     ; advance recursion over the car part
             (value-exist? n (cdr xs)))))) ; advance recursion over the cdr part

它按预期工作：

(value-exist? 4 '(1 2 3 (3 2 3)))
=> #f

(value-exist? 4 '(1 2 3 (3 4 3)))
=> #t
于 2013-07-11T19:17:20.700 回答