二叉查找数

二叉查找树，或者是一颗空树，具备以下性质得二叉树：

1，若它的左子树不空，则其左子树上的所有结点的值均小于它根结点的值；

2，若它的右子树不空，则其右子树上的所有结点的值均大于它根结点的值；

3，它的左、右子树也分别为二叉查找树

具体如下图：

                                                                   

查找操作：

 在二叉查找树中查找x的过程如下：

              1、若二叉树是空树，则查找失败。

              2、若x等于根结点的数据，则查找成功，否则。

              3，若x小于根结点的数据，则递归查找其左子树，否则。

              4，递归查找其右子树。

 

插入操作：

二叉树查找树b插入操作x的过程如下：

              1、若b是空树，则直接将插入的结点作为根结点插入。

              2、x等于b的根结点的数据的值，则直接返回，否则。

              3、若x小于b的根结点的数据的值，则将x要插入的结点的位置改变为b的左子树，否则。

              4，将x要出入的结点的位置改变为b的右子树。

 

删除操作：

于二叉查找树的删除操作（这里根据值删除，而非结点）分三种情况：

              1、如果结点为叶子结点（没有左、右子树），此时删除该结点不会玻化树的结构，直接删除即可，并修改其父结点指向它的引用为null.如下图:

 

                                         

 

                 2、如果其结点只包含左子树，或者右子树的话，此时直接删除该结点，并将其左子树或者右子树设置为其父结点的左子树或者右子树即可，此操作不会破坏树结构。如下图:

 

                                        

 

                  3、 当结点的左右子树都不空的时候，一般的删除策略是用其右子树的最小数据，代替要删除的结点数据并递归删除该结点（此时为null），因为右子树的最小结点不可能有左孩子，所以第二次删除较为容易。z的左子树和右子树均不空。找到z的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替z的值.如图：