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).
网友评论