数据结构(21)-二叉排序树

二叉排序树(Binary Sort Tree)，又称二叉查找树，它或者是一棵空树，或者是一棵具有一下性质的树：

1. 若它的左子树不空，则左⼦树上所有结点的值均⼩于它的根结点的值
2. 若它的右子树不空，则右子树上所有结点的值均⼤于它的根结点的值
3. 它的左右子树也分别是二叉排序树

二叉排序树采用了递归的定义方法。左子树结点一定比双亲结点小，右子树结点一定比双亲结点大。因为需要做删除插入操作，所有我们选择链式存储结构。

#define T_ERROR -1
#define T_OK 1
typedef int TStatus;
typedef int ElementType;

typedef struct BinaryNode {
    ElementType data;
    struct BinaryNode *leftChild, *rightChild;
} BinaryNode, *BinaryTree;

下面我们通过一个示例，来看看二叉排序树的操作。首先，我们把集合{62,88,58,47,35,73,51,99,37,93}按照二叉排序的规则生成一棵树。结果如下：

二叉排序树.png

二叉排序树的查找

在二叉排序树中查找数据可以使用递归来实现，首先我们将与根结点比较，如果小于根结点的值就去左子树中查找，如果大于根结点的值就去右子树中查找。以此类推，即可得到结果。

代码如下：

/// 二叉排序树查找
/// @param bTree 需要查找的二叉树
/// @param key 查找的key
/// @param pTree 递归使用 指向bTree的双亲结点 初始值为NULL
/// @param sTree 查找成功即返回查找到的结点TStatus返回T_OK；查找不到则返回访问的最后一个结点TStatus返回T_ERROR
TStatus searchBinarySortTree(BinaryTree bTree, int key, BinaryTree pTree, BinaryTree *sTree) {
    if (!bTree) {
        // 递归到树的最后一个结点 还是没有找到
        *sTree = pTree;
        return T_ERROR;
    } else if (key == bTree->data) {
        // 查找命中
        *sTree = sTree;
        return T_OK;
    } else if (key < bTree->data) {
        // 如果key小于当前结点，则在左子树中找
        return searchBinarySortTree(bTree->leftChild, key, bTree, sTree);
    }
    // 如果key大于当前结点，则在右子树中找
    return searchBinarySortTree(bTree->rightChild, key, bTree, sTree);
}

二叉排序树的插入

在二叉排序树查找的基础上做插入就比较简单了，先判断需要插入的是否存在二叉排序树中，如果存在则不能插入。如果不存在，判断是否是空树，若是空树，则把插入的结点作为根结点；如果不为空树，则只需要比较返回的结点值和的大小，若小于返回的结点值，则插入返回结点的左子树；若大于返回的结点值，则插入返回结点的右子树。

代码如下：

/// 二叉排序树插入
/// @param bTree 二叉排序树
/// @param key 二叉排序树插入的key
TStatus insertBinarySortTree(BinaryTree *bTree, int key) {
    BinaryTree sTree;
    if (searchBinarySortTree(*bTree, key, NULL, &sTree) == T_ERROR) {
        // 没有从二叉排序树中查找到当前key
        BinaryTree iTree = (BinaryTree)malloc(sizeof(BinaryNode));
        iTree->data = key;
        iTree->leftChild = iTree->rightChild = NULL;
        
        if (sTree == NULL) {
            // 二叉树是空树
            *bTree = iTree;
        } else if (key < sTree->data) {
            // 不是空树 key比最后一个结点的值小 往最后一个结点的左子树插入
            sTree->leftChild = iTree;
        } else {
            // 不是空树 key比最后一个结点的值大 往最后一个结点的右子树插入
            sTree->rightChild = iTree;
        }
        
        return T_OK;
    }
    
    return T_ERROR;
}

二叉排序树的删除

相对于查找和插入，二叉排序树的删除就比较麻烦了，因为删除了结点之后，我们还得必须让剩下的树还得是二叉排序树。所以我们需要对删除的结点进行分类：

• 删除的结点为叶子结点。可以直接删除不会对树造成影响。
• 删除的结点只有左子树或者只有右子树。那我们就需要将子树替换原来的结点。
• 删除的结点左右子树都有。我们先找到要删除的结点的前驱结点，然后用前驱结点来替换需要删除的结点，最后再删除前驱结点即可。或者找到被删除结点的后继结点，然后使用后继结点替换被删除的结点，然后删除后继结点。

下面我们实现以下使用前驱结点删除的代码：

/// 删除结点bTree
void delete(BinaryTree *bTree) {
    BinaryTree tmpTree;
    
    if ((*bTree)->rightChild == NULL) {
        // 右子树为空 对接左子树
        tmpTree = *bTree;
        *bTree = (*bTree)->leftChild;
        free(tmpTree);
    } else if ((*bTree)->leftChild == NULL) {
        // 左子树为空 对接右子树
        tmpTree = *bTree;
        *bTree = (*bTree)->rightChild;
        free(tmpTree);
    } else {
        // 左右子树均不为空 都需要处理
        tmpTree = *bTree;
        // 找待删除结点的前驱
        // 找到被删除结点的左子树
        BinaryTree preTree = (*bTree)->leftChild;
        // 循环一直取左子树的右子树 最后一个右子树即为被删除结点的前驱结点
        while (preTree->rightChild) {
            tmpTree = preTree;
            preTree = preTree->rightChild;
        }
        // 循环之后preTree没有右子树了
        // tmpTree此时成了preTree的双亲结点 preTree是其右子树
        
        // 将被删除结点替换成前驱结点
        // 将被删结点的数据换成前驱的数据
        (*bTree)->data = preTree->data;
        if (tmpTree != *bTree) {
            // preTree的值赋给了要删除的结点 所以我们需要把preTree删掉 连接tmpTree右子树
            tmpTree->rightChild = preTree->leftChild;
        } else {
            // 连接tmpTree左子树
            tmpTree->leftChild = preTree->leftChild;
        }
        free(preTree);
    }
}

TStatus deleteBinarySortTree(BinaryTree *bTree, int key) {
    if (bTree == NULL) {
        return T_ERROR;
    }
    
    // 查找到要删除的key就删除对应的结点
    if (key == (*bTree)->data) {
        delete(bTree);
        return T_OK;
    } else if (key < (*bTree)->data) {
        return deleteBinarySortTree(&(*bTree)->leftChild, key);
    } else {
        return deleteBinarySortTree(&(*bTree)->rightChild, key);
    }
}

二叉排序树的操作依赖于树的形状，如果二叉排序树是平衡的，则其操作的时间复杂度为，如果是斜树的话，时间复杂度就是。