給定一個未排序的串列，說明(list a b c ...)其中所有值都是整數。有沒有辦法使用簡單的回避來構建二叉搜索樹。
我正在使用 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))]))
uj5u.com熱心網友回復：
假設空樹表示為null，非空樹表示為 ( letf root right )，您可以定義一個函式將項插入二叉樹，如下所示：
(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 ())))))
uj5u.com熱心網友回復：
所以，事實證明我需要做的只是簡單的遞回。只需像我對累加器所做的一樣，但不是插入到累加器中，我將插入到創建串列其余部分的遞回呼叫中。
像這樣的東西
(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))]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/344893.html
下一篇：PHP中的遞回檔案夾樹