1

任何人都可以帮助我左右旋转二叉搜索树的基本案例吗?我尝试将正确的旋转函数编写为:

 (define (right-rotate T)

      (make-tree (car (left T)) 
                 (left (left T)) 
                 (make-tree(value T) (right (left T)) (right T))))

但这让我打电话给某个地方的空列表。此代码对于正确的旋转是否正确?另外,我的基本情况可能是什么?

4

1 回答 1

1

您确实需要提供更多信息,例如您对“树”的表示是什么,以及如何定义和处理缺少其“左”或“右”子节点的树。

(define (make-tree value left right)
  `(TREE ,value ,left ,right))
(define value cadr)
(define right caddr)
(define left  cadddr)

;; How is an 'empty' tree denoted?
(define empty 'EMPTY)
(define (is-empty? tree)
  (eq? tree empty))

(define (make-leaf value)
  (make-tree value empty empty))

;; Now you have the basis for a solution; here is a start.

(define (right-rotate tree)
  (if (is-empty? tree)
      empty
      (let ((l (left tree)))
        (if (is-empty? l)
            <something>
            (make-tree (value l)
                       (left  l)
                       (make-tree (value tree) (right l) (right tree)))))))
于 2013-10-25T14:34:57.317 回答