改进我们的代码
上一小节实现了向二分搜索树中插入元素这一操作,这一小节改进一下我们的代码,让我们对递归有更深的理解。
// 向以 node 为根的二分搜索树中插入元素 e,递归算法 private void add(Node node, E e){ if(e.equals(node.e)) return; else if(e.compareTo(node.e) < 0 && node.left == null){ node.left = new Node(e); size ++; return; } else if(e.compareTo(node.e) > 0 && node.right == null){ node.right = new Node(e); size ++; return; } if(e.compareTo(node.e) < 0) add(node.left, e); else //e.compareTo(node.e) > 0 add(node.right, e); }
首看一下这个插入操作有没有什么问题,先理解一下插入操作的算法过程。
整体上以 node 为根的这个二分搜素树插入新的元素 e,具体插入的过程相当于把新的元素 e 插入给 node 的左孩子或者 node 的右孩子。
如果对于当前的 node 来说,你想插入到左边但左孩子不为空的话,就递归调用将新的元素插入到左子树中,相应的右侧也一样。
// 向二分搜索树中添加新的元素 e public void add(E e){ if(root == null){ root = new Node(e); size ++; } else add(root, e); }
再来看一下对于我们递归 add 方法的初始调用部分,也就是用户看到的 add 接口。
我们对根节点进行了特殊的处理:如果根为空的话,根就直接是一个新的节点,否则的话再调用递归函数。
在递归调用中,我们都是把新的元素作为 node 的子节点插入进去的。
这里形成了一个逻辑上的不统一,再仔细观察一下前面的递归函数,就会发现对于 e 这个元素和 node.e 这个元素进行了两轮比较。
第一轮在比较完两个元素大小的同时还要看一下 node 的左右两个孩子是不是为空,如果是空的话直接插进去就好了。
第二轮比较我们不能直接作为 node 的孩子插入这个元素 e,我们只好递归的再去调用 add 函数。
还有一点现在我们的递归函数中止条件是非常臃肿的,这是因为我们要考虑 node 的左孩子是不是为空又要考虑右孩子是不是为空。
不过之前曾说过,“空”本身就是一个二叉树。
换句话说,想象一下如果我们递归函数走到了一个 node 为空的地方,此时就一定要形成一个节点。
在我们现在写的代码中,这种情况其实还没有递归到底,既然我们看到了 e 小于 node.e,那么我们不管 node.left 是不是为空,就再递归一层。
如果递归的这一层为空的话,也就是现在新插入一个元素到空这个二叉树上,那么很显然这个位置本身就应该是这个节点,所以用这种想法的话,代码就可以修改为如下所示:
// 向以 node 为根的二分搜索树中插入元素 e,递归算法 // 返回插入新节点后二分搜索树的根 private Node add(Node node, E e){ if(node == null){ size ++; return new Node(e); } if(e.compareTo(node.e) < 0) node.left = add(node.left, e); else if(e.compareTo(node.e) > 0) node.right = add(node.right, e); return node; }
那么我们初始调用的时候就不需要对 root 为空这种情况进行判断了,因为在我们递归的 add 函数中对 node 为空已经进行了考虑,所以初始调用的代码可以更改如下:
// 向二分搜索树中添加新的元素 e public void add(E e){ root = add(root, e); }