1

二分探索木とそれらをリストに変換するのに問題があります。

(define-struct node (key val left right))
;; A binary search tree (bst) is either
;; empty, or
;; a structure (make-node k v l r), where
;; k is a number (the key),
;; v is a string (the value),
;; l is a bst, where every key in l is less than k, and
;; r is a bst, where every key in r is greater than k.

誰かがこの質問にアプローチする方法についてのヒントを教えてもらえますか？

二分探索木を消費し、二分探索木のノードの値フィールドにあるすべての文字列のリストを返す関数bstを作成します。リストは、二分探索木のキー値に基づいて降順である必要があります。

;;Examples: (bst (make-node 4 "James" (make-node 2 "Kien" empty empty)
;;(make-node 5 "Jack" empty (make-node 11 "Cole" empty empty)))) => (list "Cole" "Jack" "James" "Kien")

ありがとう！

4

2 に答える 2

2

基本的に、逆インオーデントラバーサル（右サブツリー/値/左サブツリー）を使用してツリー内のすべてのノードにアクセスすると同時に、回答を含むリストを作成する必要があります。これらの線に沿った何か：

(define (tree->list tree)
  (if (empty? tree)
      empty
      (append (tree->list (node-right tree))
              (cons (node-val tree)
                    (tree->list (node-left tree))))))

期待どおりに機能します。

(define bst
  (make-node 4 "James"
             (make-node 2 "Kien" empty empty)
             (make-node 5 "Jack" empty
                        (make-node 11 "Cole" empty empty))))

(tree->list bst)
=> (list "Cole" "Jack" "James" "Kien")
于 2013-03-25T22:43:35.197 に答える
0 
(define (tree->list tree)
  (if(leaf? tree)
     (list (node tree))
     (cond((right-branch-only? tree)(append (list(node tree))
                                            (tree->list (right-branch tree))))
          ((left-branch-only? tree)(append (list(node tree))
                                           (tree->list (left-branch tree))))
          (else(append (list (node tree))
                       (append (tree->list (left-branch tree))
                               (tree->list (right-branch tree))))))))
于 2013-10-26T19:23:58.710 に答える