【CPP】各种各样的树（3）——二叉查找树

说完普通的二叉树，接下来是这个二叉树的一种变形，二叉查找树。

二叉查找树，其实就是加了一点限制条件的二叉树，我们限制二叉查找的每一个结点的左子树都小于右子树，按照这个规则进行插入和删除，这样就形成了一棵二叉查找树。起这个名字很显然表示了它的用途，由于数据依据大小规则插入的原因，我们可以较快地查找到所需要的数据。

先来看看声明：

结点的声明与上次没什么区别，只是这次采用了类而不是结构体来写结点，可以使用构造函数来新建结点了。

二叉树这次要来实现几个重要功能：查找，插入，删除。

首先是查找操作，我们先假定我们有一个已经构造好的二叉查照树，很容易就能想到查找的方法，从根节点开始向下搜索，一个一个与搜索到的父节点比较然后向相应方向继续递归下去，知道找到为止，代码也很好写。

然后是也比较常用的FindPre寻找父节点的操作。

接着是插入操作，如前所述，我们需要遍历整个二叉树，寻找到对应的叶子结点然后进行比较，按照规则将结点新建进去，其实这就是查找Find的拓展版本，也很好实现。

然后是比较复杂的删除Delete操作，删除操作的主要思想是，取待删除结点的右子树的最小结点（最左结点）来替代删除的结点，然后取递归删除那个最小结点，这个思想也并不复杂，只是比查找与插入难一点点，代码如下。

这种删除有个很明显的缺点，每次当目标有左右结点时，我们都是取目标结点右子树的最小结点替换然后删去那个最小结点。而如果不断插入删除，久而久之，右子树会越来短，左子树由于积累会变得很深，致使查找的效率越来越低。所以我们需要一个平衡的二叉树来保证查找的效率，能自己进行平衡的二叉树我们以后再说。

最后是将其打印出来，简单的前序遍历加适当的空格就能打印得比较好看了。

最后我们在主函数里测试一下它。

说完了查找二叉树，想必也使用了几次二叉树的遍历了，也能看出二叉树遍历时的一些缺陷吧。什么缺陷呢，下篇文章来说说线索二叉树。