二叉排序树(左子树的结点 < 根、结点 < 右子树的结点)
二叉排序树的平均查找长度 等概率下
Hash 的平均查找概率(以拉链法为例)
#include<stdio.h>
#include<malloc.h>
//二叉排序树的插入
bool Insert(BETNode*& t, Keytype k)
{
if (t == NULL)// 判断树是否为空
{
t = (BETNode*)malloc(sizeof(BETNode));
t->key = k;
t->lchild = t->rchild = NULL;
}
else if (k == t->key)//如果插入结点在树中已经存在,则返回false
{
return false;
}
else if (k < t->key)//如果待插入结点小于根结点,则递归插入左子树中
{
return Insert(t->lchild, k);
}
else
{
return Insert(t->rchild, k);//如果待插入结点大于根结点,则递归插入右子树中
}
}
//查找二叉排序树的元素,非递归查找
BSTNode* SearchBST(BSTNode* t, Keytype k)
{
while (t != NULL && k != t->key)
{
if (key < t->key) t = t->lchild; // 当前结点比根节点小,遍历左子树
else t = t->rchild;//当前结点比根节点大,遍历右子树
}
return t;
}
//查找二叉排序树的元素,递归查找
BSTNode* Search(BSTNode* t, Keytype k)
{
if (t == NULL || k != t->key)// 根节点为空 和 找不到 k 结点同时成立,退出递归调用
{
return t;
}
if (k < t->key)
{
return Search(t->lchild, k);//递归调用左子树
}
else
{
return Search(t->rchild, k);//递归调用右子树
}
}
//不仅查找结点,还要找到结点的双亲
BSTNode* Search1(BSTNode* t, Keytype k, BSTNode* f1, BSTNode*& f)//f 返回的是该结点的双亲
{
//Search1(t, x, NULL, f);f1仅作为中间参数,用于求f,初始设为NULL
if (t == NULL)
{
f = NULL;
return NULL;
}
else if (k == t->key)
{
f = f1;
return t;
}
else if(k < t -> key)
{
return Search1(t->lchild, k, t, f);
}
else
{
return Search1(t->rchild, k, t, f);
}
}
//删除某个元素
void Delete(BSTNode *& t, Keytype k)
{
if (t == NULL)
{
return;
}
else if (k < t->key)
{
return Delete(t->lchild, k);
}
else if (k > t->key)
{
return Delete(t->rchild, k);
}
else
{
BSTNode s = t->rchild;
//一般的删除策略是 左子树的最大数据(左子树中最右边的是最大值) 或 右子树的最小数据 递归遍历左子树中的右子树
if (s->lchild != NULL)
s = s->lchild;
}
t->key = s->key;
Delete(t->rchild, s->key);
}