使用简单递归从未排序列表构建二叉搜索树

Question

给定一个未排序的列表，假设 (list a b c ...) 其中所有值都是整数。有没有办法使用简单的recusion来构建二叉搜索树

我正在使用 Racket 的初级学生版。

我知道如何解决列表排序的问题，我知道如何解决累加器的问题。我也知道我可以对列表进行排序，然后使用简单的回避。但是，如果没有这些方法，我该怎么做呢？

示例： 给定列表 (list 1 2 3 5 0 9 3 5 2) 该函数应该生成一个二叉树，类似于

根据要求，这是我用累加器执行上述操作的代码。我没有代码来执行我所要求的，因为我不知道如何编写代码来执行我所要求的。

(define-struct node (key left right))
;; A Node is a (make-node Nat BT BT)

;; A binary tree (BT) is one of:
;;  * empty
;;   * Node

;; (build-bst-from-list list) takes in an unstorted list and builds
;;    a binary search tree using an acculator

;; build-bst-from-list: (listof Num) -> BT
(define (build-bst-from-list list) 
  (build-bst-from-list/acc (rest list) (make-node (first list) empty empty)))

;; (build-bst-from-list/acc list tree) takes in an unstored list and a binary 
;;    tree and inserts all the values from the list into the tree such that
;;    the tree continues to be a binary search tree

;; build-bst-from-list/acc (listof Num) BT -> BT
(define (build-bst-from-list/acc list tree)
  (cond [(empty? list) tree]
        [else (build-bst-from-list/acc (rest list)
                                   (bst-add tree (first list)))]))
;; (bst-add tree value) takes in a binary search tree and a value and
;;    add's the value such that the tree remainder a binary search
;;    tree

;; bst-add: BT Num -> BT
(define (bst-add tree value)
  (cond [(empty? tree) (make-node value empty empty)]
        [(> (node-key tree) value) (make-node (node-key tree)
                                              (bst-add (node-left tree) value)
                                              (node-right tree))]
        [(= (node-key tree) value) tree]
        [else (make-node (node-key tree)
                         (node-left tree)
                         (bst-add (node-right tree) value))]))

Answer 1

假设空树表示为null，非空树表示为(letf root right), 你可以定义一个函数来insert一个item到二叉树中，如下所示：

(define (insert item tree)
  (cond
    [(empty? tree) (list null item null)]
    [(< item (second tree)) (list (insert item (first tree)) (second tree) (third tree))]
    [(> item (second tree)) (list (first tree) (second tree) (insert item (third tree)))]
    [else tree]))

然后，您可以使用foldl来创建二叉搜索树，如下所示：

(define (create-bst items)
  (foldl insert null items))

这里有一些例子：

> (create-bst '(4 6 2 7 1 5 3))
'(((() 1 ()) 2 (() 3 ())) 4 ((() 5 ()) 6 (() 7 ())))

> (create-bst '(1 2 3 5 0 9 3 5 2))
'((() 0 ()) 1 (() 2 (() 3 (() 5 (() 9 ())))))

Answer 2

所以，事实证明我需要做的只是简单的递归。只需像我对累加器所做的那样做，但不是插入累加器，而是插入创建列表其余部分的递归调用。

像这样

(define (bst-from-list list)
  (cond [(empty? list) empty]
        [else (bst-add (bst-from-list (rest list))
                       (first list))]))


(define (bst-add tree value)
  (cond [(empty? tree) (make-node value empty empty)]
        [(> (node-key tree) value) (make-node (node-key tree)
                                              (bst-add (node-left tree) value)
                                              (node-right tree))]
        [(= (node-key tree) value) tree]
        [else (make-node (node-key tree)
                         (node-left tree)
                         (bst-add (node-right tree) value))]))

使用简单递归从未排序列表构建二叉搜索树

Building a Binary Search Tree out of an unsorted list using simple recursion

recursion

binary-tree

binary-search-tree

racket