插入零元素树很容易:
return tree_make(elt, tree_make(), tree_make());
插入一棵单元素树也很容易:
tree_t new_node = tree_make(elt, tree_make(), tree_make());
if(elt < tree_elt(tree))
return tree_make(tree_elt(tree), new_node, tree_right(tree));
else
return tree_make(tree_elt(tree), tree_left(tree), new_node);
一般来说,要插入新元素,您需要以这种方式重新创建其所有父元素。
第 2 部分:递归
我们有我们的基本情况(零元素树)。我们知道如何将新的子树附加到现有树的根上。
那么如何获取新的子树呢?那么,我们将元素插入到当前子树中怎么样?
以下代码始终将新元素附加在树的最左侧,但是一旦您理解了它,纠正起来应该很简单:
tree_t tree_insert(int elt, tree_t tree)
{
if(tree_empty(tree)) //base case
return tree_make(elt, tree_make(), tree_make());
else
return tree_make( // make a new node
tree_elt(tree) // with the same value as the current one
tree_insert(elt, tree_left(tree)) //insert into the left subtree
tree_right(tree) // keep the right subtree the same
);
}