scheme - Racket：将新节点插入二叉搜索树

Question

假设我们有一个二叉树结构：

(define-struct tree-node (left right node))    

我在创建二叉搜索树时遇到了麻烦。我的主要问题是，我不知道如何将节点插入树或覆盖 make-tree-node 结构中的左侧或右侧。
假设我们的树长度为 8，如果 left 或 right 为空，我想插入一个新节点。我的问题是我怎么走那么深？这可能递归吗？如果可以，我该怎么做？

只能使用中级。

Answer 1

How to Design Programs 中的设计秘诀回答了这个问题。19.5 节专门讨论了二叉搜索树。但是，对您最有帮助的材料可能是第 8 节和第 9 节中的内容。为您引出一些线索：首先，您需要一个二叉搜索树的数据定义。然后，您需要为各种案例编写测试案例，包括基本案例（插入到空节点中）。然后，您需要遵循与您的数据定义关联的模板。