11-二叉查找树

二叉查找树

1.什么是二叉查找树？

• 二叉查找树是一种支持数据动态的插入，删除，查找的数据结构。

2.二叉查找树的设计要求

• 任意一个节点的左孩子必须小于当前节点
• 任意一个节点的右孩子必须大于当前节点
• 整个二叉树的数据不能重复
• 如下图所示

tree40.jpg

3.二叉排序树数据的查找

既然二叉排序树每个节点的左孩子都小于当前节点，每个节点的右孩子都大于当前节点，所以我们可以根据这个特性，很容易查找数据。下面是查找步骤

• 数据小于当前节点，向左走一步
• 数据大于当前节点，向右走一步
• 找到就退出，反之当走到叶子节点，还没找到，就查找失败。

查找演示

tree5.jpg

我们要查找的数据是19，根据二叉排序树的定义去查找，
首先来到根节点33，目标19小于33，则去左分支找
来到17，目标树19大于17，去右分枝找
来到18，目标树19大于18，去右分枝找
来到25，目标树19小于25，去左分支找
来到19，等于目标数，成功找到。
如果走到某个节点为空，证明查找失败

查找代码

//0---没找到
//1---找到
void Find_Tree(struct Tree * t, int data)
{
    struct Tree * p = t;
    while (p != NULL)
    {
        if(data < p->data)
        {
            p = p->left;
        }
        else if(data>p->data){
            p = p->right;
        }
        else
        {
            printf("1\n");
            return;
        }
    }
    printf("0\n");
}

4.二叉排序树数据的插入

二叉排序树的数据插入用到了查找的步骤，因为它先要查找这个数字合适的位置，如果找到一个空节点，直接插入进去，如果找到一个和它相等的了，则不能插入了。下面是插入步骤

• 先按照查找步骤走，如果待插入数据小于当前节点，左走一步，如果大于当前节点，右走一步，如果等于当前节点，直接退出，插入失败。
• 当走到一个空节点时，就是它的位置了，直接插入进去。

插入演示

tree6.jpg

待插入数据是55
首先来到33，发现目标55比33大，走右分枝
来到50，发现目标55比50大，走右分枝，
来到58，发现目标55比58小，走左分支，
来到51，发现目标55比51大，走右分枝，
此时为空，就将数据插入该位置。

插入代码

void Insert_Tree(struct Tree ** t, int data)
{
    if ((*t) == NULL)
    {
        (*t) = (struct Tree*)malloc(sizeof(struct Tree));
        (*t)->data = data;
        (*t)->count = 1;
        (*t)->left = NULL;
        (*t)->right = NULL;
    }
    else
    {
        if (data < (*t)->data)
        {
            Insert_Tree(&((*t)->left), data);
        }
        else if (data > (*t)->data)
        {
            Insert_Tree(&((*t)->right), data);
        }
        else
        {
            (*t)->count++;
        }
    }
}

5.数据的删除

为了保证删除元素后，二叉排序树仍然有序，我们必须按照一定规律进行删除。二叉排序树数据的删除总体分为两部分，第一部分就是查找，先在树中查找是否存在待删除的节点，如果不存在，直接退出。反之找到了这个节点。然根据规律进行对应的删除操作。下面是删除操作的步骤。

• 首先在树中查找待删除的数据，其实就是查找操作。
• 找到数据后，此时的删除分三类情况
  1. 待删除节点无左右孩子，直接删除当前节点
  2. 待删除节点存在一个孩子，是左孩子或者右孩子，那么将存在的那个左孩子分枝或者右孩子分枝直接挂在当前节点的位置上(就是覆盖当前位置)
  3. 待删除节点存在两个孩子，左右孩子都有，此时有两种操作可以删除，第一种是先向左走一步，再一路向右走下去，直到来到一个没有右孩子的节点，将该节点直接放在待删除节点位置上就行。第二种是先向右走一步，再一路向左走下去，直到来到一个没有左孩子的节点，将该节点直接放在待删除节点的位置上就行。

插入操作演示

1.删除节点20,先查找节点20，发现存在节点20，此时的20没有左右孩子，直接删除。

tree41.jpg

2.删除节点2，先找到节点2，发现存在一个左孩子，直接将左孩子放在自己位置上。

tree42.jpg

3.删除节点10，先找到10，发现10左右孩子都有，按照我总结的，随便采取一个方法，我们采取先向左走一步,来到节点8位置，一路向右走，直到走到一个无右孩子的节点，就是元素9，将9放在待删除节点位置上。

tree43.jpg

删除代码

/*
删除操作分三种情况

第一类：该元素无左右孩子，直接删除
第二类：该元素有左孩子或者右孩子(有一个孩子),直接将该孩子节点与其父节点连接
第三类：该元素左右孩子都在
3.1：先向左走一步，一直向右走，直到走到一个叶子节点，将该叶子节点的赋给待删除节点元素。
3.2：先向右走一步，一直向左走，直到走到一个叶子节点，将该叶子节点的赋给待删除节点元素。
*/
void Del(struct Tree ** t)
{
    //左子树空，右不空
    if ((*t)->left == NULL && (*t)->right!=NULL)
    {
        struct Tree *p;
        p = (*t);
        (*t) = (*t)->right;
        free(p);
    }
    //右子树空，左不空
    if ((*t)->right == NULL && (*t)->left != NULL)
    {
        struct Tree *p;
        p = (*t);
        (*t) = (*t)->left;
        free(p);
    }
    //左右都空
    if ((*t)->right == NULL && (*t)->left != NULL)
    {
        free((*t));
    }
    //左右都不空
    if ((*t)->right != NULL && (*t)->left != NULL)
    {
        //采用左枝法，先向左走一步，一直向右边走
        struct Tree *p,*q;
        p = (*t)->left;
        while (p->right != NULL)
        {
            p = p->right;
        }
        //该节点右子树一定是空，左边不确定
        (*t)->data = p->data;
        if (p->left == NULL)
        {
            free(p);
        }
        else
        {
            q = p;
            p = q->left;
            free(q);
        }
    }
}
void Del_Tree(struct Tree ** t, int data)
{
    if ((*t) == NULL)
    {
        return;
    }
    if ((*t)->data == data)
    {
        Del(t);
    }
    else if ((*t)->data > data)
    {
        Del_Tree(&((*t)->left), data);
    }
    else
    {
        Del_Tree(&((*t)->right), data);
    }
}

6.二叉查找树的弊端

通过上面的学习，我们直到二叉查找树是一个近乎完美的查找算法，还可以动态添加数据，删除数据。当时二叉查找树被发明时。许多人都认为它就是最牛逼的，因为它太好用了，可是又有一位大神出来了，他是谁，你们去查吧，我忘了谁。它发现二叉查找树不总是可以让查找的时间复杂度控制在0(logn),当我么插入一组有序的数列时，它的查找就退化成了线性表,进而事件复杂度又回退到o(n)级别了。如下所示，我依次插入数据1,2,3,4,5

tree30.jpg

此时我们要查找一个数字，是不是得逐个遍历才可以的，好了，今天主角故事讲完了。下节我们继续讲它点升级版---平衡二叉树

总结

二叉查找树，是十分优秀的查找算法，它的查找时间复杂度是0(logn),并且中序遍历二叉查找树，它输出的序列是有序的。

获取完整代码

我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。

点击查看