用C++实现二叉搜索树

    一棵二叉搜索树是一棵二叉树，可以为空，但它不为空时，满足下述条件：

    1、每个元素都有一个键值且都不相同

    2、左子树的键值都小于树根的键值

    3、右子树的键值都大于树根的键值

    4、左右子树也都是二叉搜索树。

    下图是一棵简单的二叉搜索树：

二叉搜索树

    下面是用C++实现的二叉搜素树的算法：

C++实现二叉搜索树

    上述算法比较难的就是二叉搜索树的节点删除需要分三种情况考虑。第一种，删除节点是树叶，则直接删除；第二种是被删除的节点只有一个子节点，此时只需要将删除节点的上一个节点的指向该节点的指针指向该节点唯一的子节点；第三种是被删除的节点有两个子节点，这种情况是最麻烦的。我们采用的思想是将该节点的该节点右子树中最小的一个节点的值覆盖该节点中的值，然后再删除该节点的右子树中的最小的那个子节点。因为，该节点的右子树中的最小的那个子节点的值刚好大于被删除节点的左子树中所有的值，又小于被删除节点的右子树中所有的值。最小的那个子节点不可能有左子树，不然它就不是最小的节点，删除该节点就转换为删除一个只有一个子节点的节点，即第二种情况。

    可以发现，在代码中，多次用了递归的方法来进行算法的编写，那么递归中的时间复杂度如何分析呢？小编在这里总结一个规律：“递归中进行一次递归调用，递归深度为depth，每个递归中的时间复杂度为T，则总的时间复杂度为O(T*depth)”。当递归中进行多次递归调用时，还要关注递归调用的次数，就像采用递归实现的斐波那契数列一样。

    关于插入，删除，查找等算法的时间复杂度，接下来有时间小编在做分析。小编这里就简单放了一个调试成功无bug的代码，当然也是结合网上其他人总结得到的。