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 并返回二叉搜索树节点的 value 字段中所有字符串的列表，该列表必须根据二叉搜索树中的键值降序排列。

;;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 回答