定义
二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。
一个二叉搜索树可以为空,如果它不为空,它将满足以下性质:
- 非空左子树的所有键值小于其根节点的键值
- 非空右子树的所有键值都大于其根结点的键值
- 左、右子树都是二叉树
动态查找
查找操作Find
在二叉搜索树中查找关键字为X的结点,返回其所在结点的地址。查找过程如下:
- 查找从树的根节点开始,若树为空,返回NULL
- 搜索树非空,则根节点关键字和X比较,依据结果,需要进行不同的处理
若根节点键值小于X,在根节点右子树中查找
若根节点的键值大于X,在根节点的左子树中查找
若两者比较结果相等,搜索完成。
递归代码
Position Find_RE(BinTree BT, ElementType X) {
if (!BT) {
return NULL;
}
if (X > BT->Data) {
return Find_RE(BT->Right, X);
}
else if(X < BT->Data)
{
return Find_RE(BT->Left, X);
}
else
{
return BT;
}
}
迭代函数
Position Find_D(BinTree BT, ElementType X) {
BinTree T = BT;
while (T) {
if (T->Data > X) {
T = T->Left;
}
else if (T->Data < X) {
T = T->Right;
}
else
{
return T;
}
}
}
查找最大和最小元素
根据二叉搜索树的性质,最大元素一定在最右分支的尾端,最小元素一定在最左分支的尾端。
递归函数
Position FindMin(BinTree BT) {
if (!BT) {
return NULL;
}
else if(!BT->Left)
{
return BT;
}
else
{
return FindMin(BT->Left);
}
}
迭代函数
Position FindMinD(BinTree BT) {
BinTree T = BT;
while (T->Left) {
T = T->Left;
}
return T;
}
找最大值只需要把left换成right
插入
BinTree Insert(BinTree BT, ElementType X) {
if (!BT) {
BT = (BinTree)malloc(sizeof(struct TNode));
BT->Data = X;
BT->Left = BT->Right = NULL;
}
else {
if (X > BT->Data) {
BT->Right = Insert(BT->Right, X);
}
else if (X < BT->Data) {
BT->Left = Insert(BT->Left, X);
}
}
return BT;
}
删除
二叉搜索树的删除比较复杂,需要考虑节点的位置文章来源:https://www.toymoban.com/news/detail-834985.html
- 叶结点
可以直接删除,将其父节点指针置空即可。 - 只有一个孩子结点
要修改其父节点的指针,指向要删除结点的孩子结点。 - 有左、右两颗树
究竟用哪颗子树的根结点来填充删除节点的位置?有两种选择方式:选择左子树的最大元素,或者选择右子树的最小元素。无论哪种方式,最后被选择的结点必定最多只有一个孩子。
采用右子树的最小元素的删除代替策略。
代码思路: 先找到要删除元素的位置,若其具有左右子树,找到该位置的右子树里面的最小元素,赋值到该位置上,在其右子树中删除最小元素(递归调用),若只有一个子树或者没有,易操作。文章来源地址https://www.toymoban.com/news/detail-834985.html
BinTree DeleteBT(BinTree BT, ElementType X) {
Position p;
if (!BT) {
printf("can't find the node\n");
}
else {
if (X > BT->Data) {
BT->Right = DeleteBT(BT->Right, X);
}
else if (X < BT->Data) {
BT->Left = DeleteBT(BT->Left, X);
}
else {
if (BT->Left && BT->Right) {
//FIND THE Min OF Right TREE
p = FindMin(BT->Right);
BT->Data = p->Data;
BT->Right = DeleteBT(BT->Right, p->Data);
}
else {
p = BT;
if (!BT->Left) {
BT = BT->Right;
}
else { BT = BT->Left; }
free(p);
}
}
}
return BT;
}
到了这里,关于【数据结构】18 二叉搜索树(查找,插入,删除)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!