|
对于insert，需要修改查找失败时的指针内容，显然这是个内部指针（在双亲节点的内部，而不是象root和current那样在节点外面指向节点），这就要求find返回一个内部指针的引用。但是C++的引用绑定到一个对象之后，就不能再改变了，因此在find内部的实现是一个二重指针。insert操作还需要修改插入的新节点的parent指针域，因此在find中要产生一个能被insert访问的指向find返回值所在节点的指针，这里用的是current。实际上find返回的指针引用不是current->left就是current->right。这样一来，insert的实现就非常简单了。
对于remove，需要修改查找成功时的指针内容，同样是个内部指针。在find的基础上，很容易就能得到这个内部指针的引用(BTNode*&p=find(data)。
在p->left和p->right中至少有一个为NULL的情况下，如果p->left==NULL，那么就重连右子树p=p->right，反之，重连左子树p=p->left。注意，左右子树全空的情况也包含在这两个操作中了——在p->left==NULL的时候重连右子树，而这时p->right也是NULL——因此不必列出来。如果重连后p不为空，需要修改p->parent=current。
若p->left和p->right都不为空，可以转化为有一个为空。例如一个中序有序序列[1,2,3,4,5]，假设3既有左子树又有右子树，那么它的前驱2一定缺右子树，后继4一定缺少左子树。【注1】这样一来删除节点3就等效成从[1,2,3(4),4,5]删除节点4。这样就可以利用上面的在p->left和p->right中至少有一个为NULL的情况下的方法了。还是由于C++的引用不能改变绑定对象，这里是用利用递归来解决的，还好最多只递归一次。如果用二重指针又是满天星星了，这就是明明是尾递归却没有消去的原因。
【注1】这是因为，如果3既有左子树又有右子树，那么2一定在3的左子树上，4一定在3的右子树上；如果2有右子树，那么在2和3之间还应该有一个节点；如果4有左子树，那么3和4之间也应该还有一个节点。
【闲话】上面关于remove操作p->left和p->right都不为空的处理方法的讲解，源于严蔚敏老师的课件，看完后我豁然开朗，真不知道为什么她自己那本《数据结构（C语言版）》这里写的那么难懂，我是死活没看明白。
|
