計劃樹之謎：在最終對中表示空節點

Question

我試圖解決一個謎題，即抓取二叉樹以查找特定值是否作爲節點存在。我在評估一個看起來像'(1 '())的對時遇到問題。我想當我評估(= 4 '())它返回真這顯然不正確。

我試圖刪除cons添加空對，但我現在得到以下內容： (#f . #f)我認爲這不是一對。我在阻止如何通過cons建立配對列表。

我的代碼如下：

我自制any?功能

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

版本與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) 
             '())))))))) 

版本，我已經刪除了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) 
           (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))) 

Answer 1

您的代碼不遵循解決方案模板遞歸遍歷列表的列表（無論是樣本輸入還是程序似乎都無法處理實際的二叉樹），試圖修復當前的解決方案毫無意義。相反，我會告訴你正確的配方申請：

(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 

Answer 2

解決規劃問題，方法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))))) 

Answer 3

1. (#f . #f)是完全有效的和良好的對。其car是第一個#f，其cdr是第二個#f。

2. 「如何通過利弊建立一個對列表。「一對是其car及其cdr的cons：

   (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. 在嵌套列表（a.k.a.二叉樹）中查找元素的最一般方法是使用car-cdr遞歸。應注意正確處理列表中的()元素。我們也可以允許列表/對作爲值（不僅僅是原子）：

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

Answer 4

我很喜歡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