DrRacket删除二叉搜索树的根

Question

请注意，这是家庭作业！ - >我不是在寻找直接代码的例子，而是一些温和的按摩我的推理...

我被要求写一个函数，通过做三件事去除二叉搜索树的根： i）将树右移 ii）删除右子树的根（这是原始bst根） iii）用新根（它是原始树的左边）和适当的重排来重建bst该节点的孩子......这是我有：

(define (rm-root my-bst) 
     (list (key (rot-r my-bst)) 
      (left (rot-r my-bst)) 
      (append (right (right (rot-r my-bst))) 
        (left (right (rot-r my-bst)))))) 

这是所有伟大的，期待它不与childr重建树zh_cn被“提升”到根节点的节点。任何人都可以帮助我思考我应该如何去实现它？我应该提到，我们已经将Bst定义为列表，并且函数rot -r将bst旋转到右侧。谢谢。

Answer 1

嗯，我不确定这个问题在问题提出后12天会有用，但是在这里。要清楚，我猜数据结构的形式是（左键右键列表），其中左边和右边也是树（或空的，但与此无关）。如果情况并非如此，则需要澄清这一点。

你的代码中的一个问题是，你不想直接追加右边的两个列表。你想用其中一个关键字列表，然后左右。如果我正确读取这个，左边的函数应该返回一棵树，因此应该工作正常。

如果我是你，我会检查rot-r的执行情况，因为这似乎是事情出错的主要可能性。