简易BST实现
BST，即二叉搜索树，该数据结构规定任意若一个结点存在左子树，那么该结点键必须要大于左子树上所有键；若有右子树，那么该结点键必须要小于右子树上所有键简单的BST是树形查找里的入门级数据结构，不涉及平衡性调节，只需要简单插入删除，即可，其中删除稍复杂，但是也不难，只需要把三种情况分清即可。简单的BST因为不存在平衡调节，所以针对某些特定序列(如已排序序列依次插入)在构造好BST后，事实上退化为链表，这样搜索效率大幅下降到O(n)
今天先贴个简单BST实现，改天再贴个AVL树的实现
typedef struct BSTnode {
struct BSTnode *left, *right;
int data;
}BSTnode, *BST;
//simple BST
BST batch_create_BST(int a[], int n);
void destroy_BST(BST &T);
bool insert_BST(BST &T, int e);
bool delete_BST(BST &T, int e);
bool find_BST(BST &T, int e);
BST batch_create_BST(int a[], int n)
{
BST T = nullptr;
for (int i = 0; i < n; ++i)
insert_BST(T, a);
return T;
}
void destroy_BST(BST &T)
{
if (!T)
return;
destroy_BST(T->left);
destroy_BST(T->right);
free(T);
T = nullptr;
}
bool insert_BST(BST &T, int e)
{
if (!T)
{
T = (BSTnode *)malloc(sizeof(BSTnode));
T->data = e;
T->left = T->right = nullptr;
return true;
}
if (e > T->data)
return insert_BST(T->right, e);
else if (e < T->data)
return insert_BST(T->left, e);
return false;
}
bool delete_BST(BST &T, int e)
{
if (!T) // 空树删除失败
return false;
if (T->data == e) // 特殊处理根节点删除
{
if (T->left && T->right) // 根有左右子树
{
BSTnode *p = T, *q = T->left;
while (q->right) // 找到根节点的前驱以及前驱的父结点
{
p = q;
q = q->right;
}
T->data = q->data; // 覆盖根的元素
// 以下删除q
if (p->left == q)
p->left = q->left != nullptr ? q->left : q->right; // 这里可以处理叶节点情况
else
p->right = q->left != nullptr ? q->left : q->right; // 同上
free(q);
q = nullptr;
}
else // 仅有左或右子树以及叶结点情况
{
BSTnode *del = T;
T = T->left != nullptr ? T->left : T->right; // 事实上这里也能处理单节点情况
free(del);
del = nullptr;
}
}
else // 删除内部结点
{
BSTnode *p = nullptr, *q = T;
while (q && q->data != e) // 查找待删除结点及其父结点
{
p = q;
q = q->data > e ? q->left : q->right;
}
if (!q) // 没有这个结点删除失败
return false;
if (q->left && q->right) // 具有左右子树的结点删除
{
BSTnode *pre = q, *del = q->left;
while (del->right) // 寻找待删除结点的中序直接前驱以及这个前驱的父结点
{
pre = del;
del = del->right;
}
q->data = del->data; // 前驱直接覆盖原本待删除结点
// 以下删除del
if (pre->left == del)
pre->left = del->left != nullptr ? del->left : del->right; // 可以处理叶结点情况
else
pre->right = del->left != nullptr ? del->left : del->right;
; // 同上
free(del);
del = nullptr;
}
else // 仅有单子树的结点或叶结点删除
{
if (p->left == q)
p->left = q->left != nullptr ? q->left : q->right; // 根据这里可以将前面的叶结点删除作优化掉
else
p->right = q->left != nullptr ? q->left : q->right; // 同上
free(q);
q = nullptr;
}
}
return true;
}
bool find_BST(BST &T, int e)
{
BSTnode *p = T;
while (p)
{
if (e > p->data)
p = p->right;
else if (e < p->data)
p = p->left;
else
break;
;
}
if (p)
return true;
else
return false;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]