二叉排序树

1.前言

我们知道，对于顺序存储的无序线性表来说，插入操作就是在表尾增加一个记录，删除操作就是将要删除的元素与表尾元素互换然后表长度减一。可见删除插入操作对于无序线性表来说效率是可以的。但问题是对于查找算法的效率是低下的。对于顺序存储的有序线性表来说，查找可以用折半查找，插值查找，斐波那契查找，但是问题是因为线性表是有序的对于插入删除算法效率也低。有没有一种对于插入删除和查找效率都不错的算法呢？这就是我们说的二叉排序树(Binary Sort Tree )啦。

2.二叉排序树定义及实现

二叉排序树：又称二叉查找树。二叉排序树是一颗空树或者具有以下性质的树。1.若它的左子树不为空，则左子树上的所有结点都小于根节点的值。2.若它的右子树不为空，则右子树上的所有结点都大于根节点的值。3.它的左右子树也都为二叉排序树。如下图：

二叉排序树示例.png
由二叉排序树的结构，中序遍历就可以得到一个有序的序列。

现在我们来构建一颗二叉排序树并且实现查找插入删除功能，简单实现如下：

#pragma once
#ifndef _BINARYSORTTREE_H
#define _BINARYSORTTREE_H 1
typedef int ElemType;

//我们采用二叉链表结构实现二叉树存储
typedef struct BiTreeNode
{
    ElemType data;
    BiTreeNode* lchild, * rchild;
}BiTreeNode,* BiTree;

//插入
bool insertBST(BiTree* root,ElemType key);
//删除
bool deleteBST(BiTree* root, ElemType key);
//查找
bool searchBST(BiTree root, BiTree* p, BiTree f,ElemType key);

bool deleteNode(BiTree* node);

//中序遍历
void traverseBiTree(BiTree tree);

#endif

#include "BinarySortTree.h"
#include <cstdlib>
#include <iostream>
#include <cassert>

//插入
bool insertBST(BiTree* root, ElemType key)
{
    BiTree newNode = nullptr;
    //p为记录查找失败时搜寻路径上的最后一个结点
    BiTree p = nullptr;
    //查找失败的话才插入数据
    if (!searchBST(*root,&p,nullptr,key))
    {
        newNode = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        assert(newNode != nullptr);
        newNode->data = key;
        newNode->lchild = newNode->rchild = nullptr;

        //二叉树为空
        if (!p)
        {
            *root = newNode;
        }
        else if (key > p->data)
        {
            p->rchild = newNode;
        }
        else
        {
            p->lchild = newNode;
        }
    }
    return false;
}

//删除
bool deleteBST(BiTree* root, ElemType key)
{
    //不存在key值
    if (!*root)
    {
        return false;
    }
    else
    {
        if ((*root)->data == key)
        {
            return deleteNode(root);
        }
        else if (key < (*root)->data)
        {
            deleteBST(&(*root)->lchild,key);
        }
        else
        {
            deleteBST(&(*root)->rchild, key);
        }
    }
}

//查找
/*
*   @param root二叉树树的根节点
*   @param p如果查找成功就指向该数据元素结点，查找失败就返回搜寻路径上的最后一个结点
*   @param f始终指向root的双亲，万一查找失败方便记录p的位置,初始调用值为nullptr
*   @param key待查找的值
*   @return 查找成功就返回true，否者返回false
*/
bool searchBST(BiTree root, BiTree* p, BiTree f, ElemType key)
{
    //查找失败
    if (!root)
    {
        *p = f;
        return false;
    }
    //查找成功
    else if (key == root->data)
    {
        *p = root;
        return true;
    }
    else if (key < root->data)
    {
        searchBST(root->lchild,p,root,key);
    }
    else
    {
        searchBST(root->rchild, p, root, key);
    }
    return false;
}

/*
*   删除结点考虑三种情况：
*   1.待删除结点是叶子结点
*   2.待删除结点为含有一个左孩子或者右孩子的结点
*   3.待删除结点为含有左右孩子节点的结点
*/
bool deleteNode(BiTree* node)
{
    BiTree p = nullptr, s = nullptr;

    //待删除结点左孩子为空则连右孩子
    if ((*node)->lchild == nullptr)
    {
        p = *node;
        *node = p->rchild;
        free(p);
    }

    //待删除结点右孩子为空则重新连左孩子
    else if ((*node)->rchild == nullptr)
    {
        p = *node;
        *node = p->lchild;
        free(p);
    }

    //待删除结点左右孩子都不为空
    else
    {
        p = *node;
        s = (*node)->lchild;
        //找到待删除结点的前驱结点
        while (s->rchild)
        {
            p = s;
            s = s->rchild;
        }
        (*node)->data = s->data;
        //我们还要对找到的前驱结点的左或者右孩子负责
        if (p != (*node))
        {
            p->rchild = s->lchild;
        }
        else
        {
            p->lchild = s->lchild;
        }
        free(s);

    }

    return true;
}



//中序遍历
void traverseBiTree(BiTree tree)
{
    if (!tree)
    {
        return;
    }
    traverseBiTree(tree->lchild);

    std::cout << tree->data << " ";

    traverseBiTree(tree->rchild);
}

测试程序如下：

#include "BinarySortTree.h"
#include <iostream>

int main()
{
    BiTree tree = nullptr;

    int a[] = {62,88,58,47,35,73,51,99,37,93};
    for (size_t i = 0 ; i < sizeof(a) / sizeof(int) ; i++)
    {
        insertBST(&tree,a[i]);
    }
    std::cout << "删除前：";
    //中序递归遍历
    traverseBiTree(tree);

    //删除99
    bool ret = deleteBST(&tree,99);

    //删除100
    bool ret1 = deleteBST(&tree, 109);
    std::cout << "\n" << ret1 << std::endl;

    std::cout << "删除后：";
    //中序递归遍历
    traverseBiTree(tree);

    //将二叉树的结点全部删除
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        deleteBST(&tree, a[i]);
    }
    
    std::cout << "\n以防内存泄漏将全部结点删除:" << std::endl;
    //中序递归遍历
    traverseBiTree(tree);

    return 0;
}

//运行结果如下：
//删除前：35 37 47 51 58 62 73 88 93 99
//0
//删除后：35 37 47 51 58 62 73 88 93
//以防内存泄漏将全部结点删除:

在删除算法中，是需要考虑三种情况的：
1.待删除结点的左右孩子都为空
2.待删除结点的左孩子或者右孩子为空
3.待删除结点的左右孩子都不为空

在第三种情况中，是有两种方法的，如下图是假设是一个二叉排序树：

二叉排序树.png
现在我们要删除的结点是带有左右孩子的B结点，方法一：找到B结点的前驱结点并替换为B结点，注意要对B结点的左孩子负责进行重连，然后将前驱结点删除。方法二：找到B结点的后继结点并替换为B结点，注意要对B结点的右孩子负责进行重连，然后将后继结点删除。

3.二叉排序树总结

二叉排序树的缺点：二叉排序树的查找性能取决于二叉排序树的性状。怎么说呢？现在假设有两颗二叉排序树如下图：

二叉排序树1.png
二叉排序树2.png
对于查找结点99，图一需要比较3次，图二需要比较10次。也就是说对于一颗不平衡的二叉排序树如图二这个右斜二叉树，查找的时间复杂度达到了O(n).等同于无序的顺序表中查找。这个效率显然不是我们想要的。因此又引申出另一种二叉排序树：平衡的二叉排序树。将查找算法的时间复杂度优化到O(logn).