方案 bst-delete-max

Question

我必须创建一个函数 bst-delete-max，它将二叉搜索树作为参数，returns 一个二叉搜索树，其中包含从树中删除的最大值的节点。我不能使用任何找到最大值的辅助函数 (bst-max) 或辅助函数来删除节点 (bst-delete)。因此，我完全不知道如何解决这个问题以及如何为它做任何事情。我知道，无论在哪里我都会使用 bst-max，我只需要编写用于查找最大最大值的函数。但是我该如何删除它呢？任何帮助将不胜感激。这是我目前拥有的：

 (define (remove-max bs-tree)
  (cond ((null? bs-tree)
     '())
    ((null? (bst-right bs-tree))
     (bst-value bs-tree)
     (car bs-tree)) ;This is the part I know is wrong. How should I fix it?
    (else (remove-max (bst-right bs-tree)))))

Answer 1

BST中消除最大元素有两种可能：结点是叶子（此时必须returnnull）或者结点有左子树（那么我们必须return它，因为我们只需要消除一个单个节点，而不是整个子树。

注意节点不能有右子树，否则不是最大元素。我们可以通过简单地 returning 左子树来涵盖所有情况，无论它是什么 - 如果我们在叶子中，它甚至可能是 null。此外，我们必须在前进时构建一棵新树，具有相同的元素 - 只有正确的子树会有所不同。

假设我们有一个 bst-make 过程接收一个值、一个左子树和一个右子树作为参数，这就是一个可能的解决方案：

(define (remove-max bs-tree)
  (cond ((null? bs-tree)
         '())
        ((null? (bst-right bs-tree))
         (bst-left bs-tree))
        (else
         (bst-make (bst-value bs-tree)
                   (bst-left  bs-tree)                   
                   (remove-max (bst-right bs-tree))))))

方案 bst-delete-max

Scheme bst-delete-max

tree

scheme

binary-tree

list

binary-search-tree