二叉搜索树(C语言实现)

二叉搜索树

二叉搜索树(BST,Binary Search Tree)也称二叉排序树二叉查找树

特点:

  1. 非空左子树的所有键值小于其根节点的键值
  2. 非空右子树的所有键值大于其根节点的键值
  3. 左右子树都是二叉搜索树

二叉查找树特别函数

查找操作

二叉搜索树的查找操作Find

1
2
3
4
5
6
7
8
9
Position Find(ElementType X,BinTree BST){
if(!BST) return NULL;//查找失败
if(X>BST->Data)
return Find(X,BST->Right);//在右子树中继续查找
else if(X<BST->Data)
return Find(X,BST->Left);//在左子树中继续查找
else
return BST;//查找成功,返回节点的地址
}

由于非递归函数的执行效率高,可将”尾递归”函数改为迭代函数

1
2
3
4
5
6
7
8
9
10
11
Position IterFind(ElementType X,BinTree BST){
while(BST){
if(X>BST->Data)
BST = BST->Right;//向右子树继续查找
else if(X<BST->Data)
BST = BST->Left;//向左子树继续查找
else
return BST;//查找成功
}
return NULL;//查找失败
}

查找效率取决于树的高度

1
2
3
4
5
6
7
8
//查找最小元素的递归函数
Position FindMin(BinTree BST){
if(!BST) return NULL;
else if(!BST->Left)
return BST;//找到最左节点并返回
else
return FindMin(BST->Left);//沿左分支继续查找
}
1
2
3
4
5
6
7
8
//查找最大元素的迭代函数
Position FindMax(BinTree BST){
if(BST){
while(BST->Right) BST = BST->Right;
//沿右分支继续查找,直到最右叶节点
}
return BST;
}

二叉搜索树的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BinTree Insert(ElementType X,BinTree BST){
if(!BST){
//若原树为空,生成并返回一个节点的二叉搜索树
BST = malloc(sizeof(struct TreeNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}else {
if(X<BST->Data)
BST->Left = Insert(X,BST->Left);
//递归插入左子树
else if(X>BST->Data){
BST->Right = Insert(X,BST->Right);
//递归插入右子树
}
}
return BST;
}

二叉树的删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
BinTree Delete(ElementType X,BinTree BST){
Position Tmp;
if(!BST) printf("要删除的元素未找到");
else if(X<BST->Data)
BST->Left = Delete(X,BST->Left);//左子树递归删除
else if(X>BST->Data)
BST->Right = Delete(X,BST->Right);//右子树递归删除
else
if(BST->Left&&BST->Right){
Tmp = FindMin(BST->Right);
BST->Data = Tmp->Data;
BST->Right = Delete(BST->Data,BST->Right);
}else{
Tmp = BST;
if(!BST->Left)
BST=BST->Right;
else if(!BST->Right)
BST=BST->Left;
free(Tmp);
}
return BST;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!