3.1 二叉排序树
3.1.1 定义
-
二叉排序树的定义
又称二叉查找树（BST，Binary Search Tree）
二叉排序树是具有以下性质的二叉树：
左子树结点值<根结点值<右子树结点值
- 进行中序遍历，可以得到一个递增的有序序列。
3.1.2 查找操作
-
步骤
1.若树非空，目标值与根结点的值比较；
2.若相等，则查找成功；
若小于根结点，则在左子树上查找；
否则在右子树上查找；
3.查找成功返回结点指针；查找失败返回NULL。
-
代码
//二叉排序树结点 typedef struct BSTree{ int key; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree; //在二叉排序树中查找值为key的结点 BSTNode *BST_search(BSTree T,int key){ //若树为空或等于根结点值，则结束循环 while(T!=NULL&&key!=T->key){ if(key<T->key) T=T->lchild; //key小，则在左子树上找 else T=T->rchild; //key大，则在右子树上找 } return T; } -
用递归方式实现
BSTNode *BSTSearch(BSTree T,int key){ if(T==NULL) return NULL; if(key==T->key) return T; else if(key<T->key) return BSTSearch(T->lchild,key); //递归在左树中找 else return BSTSearch(T->rchild,key); //递归在右子树中找 }- 递归的最坏空间复杂度 O ( h ) O(h) O(h)，非递归是 O ( 1 ) O(1) O(1)，所以非递归效率更加好。
3.1.3 插入操作
-
思路
若原二叉树为空，则直接插入结点；
否则，若关键字k小于根结点值，则插入到左子树；
若关键字k大于根结点值，则插入到右子树。
-
代码
//在二叉排序树插入关键字为k的新结点（递归实现） int BST_Insert(BSTree &T,int k){ //原树为空，新插入的结点为根结点 if(T==NULL){ T=(BSTree)malloc(sizeof(BSTNode)); T->key=k; T->lchild=T->rchild=NULL; return 1; } else if(k==T->key) //树中存在相同关键字的结点，插入失败 return 0; else if(k<T->key) //插入到T的左子树 return BST_Insert(T->lchild,k); else //插入到T的右子树 return BST_Insert(T->rchild,k); } -
最坏空间复杂度： O ( h ) O(h) O(h)
-
二叉排序树的构造
//按str[]中的关键字序列建立二叉树 void Creat_BST(BSTree &T,int str[],int n){ T=NULL; int i=0; //依次将每个关键字插入到二叉排序树中 while(i<n){ BST_Insert(T,str[i]); i++; } }- 注：不同的关键字序列可能得到同款二叉排序树，也可能不同。
3.1.4 删除操作
-
步骤
先搜索找到目标结点：
1.若被删结点z是叶子结点，
则直接删除，不会破坏二叉排序树的性质。
2.若结点z只有一棵左子树或右子树，
则让z的子树成为z的子树成为z父节点的子树，代替z的位置。
3.若z既有左子树又有右子树，
方法一：则令z的直接后继（中序遍历z子树后的第一个结点）代替z，然后从二叉排序树中删去这个直接后继。
z的后继：z的右子树中最左下结点（该结点一定没有左子树）。
方法二：用直接前驱替换直接后继，其他方法不变。
z的前驱：z的左子树中最右下结点（该结点一定没有右子树）。
3.1.5 效率分析
-
查找长度
在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。
-
时间复杂度
最差情况下 O ( h ) O(h) O(h)，即为树高
*完整代码 二叉排序树
#include <iostream>
using namespace std;
//二叉排序树结点
typedef struct BSTNode{
int key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
// 在二叉排序树中搜索关键字为key的结点
BSTNode* BSTSearch(BSTree T, int key) {
if (T == NULL || T->key == key)
return T;
if (key < T->key)
return BSTSearch(T->lchild, key);
else
return BSTSearch(T->rchild, key);
}
// 在二叉排序树中查找最小值结点
BSTNode* findMin(BSTree T) {
if (T == NULL)
return NULL;
else if (T->lchild == NULL)
return T;
else
return findMin(T->lchild);
}
// 删除结点z
void BST_Delete(BSTree &T, int key) {
if (T == NULL)
return;
else if (key < T->key)
BST_Delete(T->lchild, key);
else if (key > T->key)
BST_Delete(T->rchild, key);
else {
// 找到了要删除的结点
if (T->lchild && T->rchild) {
// 如果有两个子节点
BSTNode* minRight = findMin(T->rchild); // 找到右子树的最小值结点
T->key = minRight->key; // 用右子树的最小值替换当前结点
BST_Delete(T->rchild, minRight->key); // 删除右子树的最小值结点
} else {
// 如果只有一个子节点或者是叶子结点
BSTNode* temp = T;
if (T->lchild == NULL) // 如果只有右子树或者是叶子结点
T = T->rchild;
else if (T->rchild == NULL) // 如果只有左子树
T = T->lchild;
free(temp); // 释放删除结点的内存
}
}
}
//在二叉排序树插入关键字为k的新结点（递归实现）
int BST_Insert(BSTree &T,int k){
//原树为空，新插入的结点为根结点
if(T==NULL){
T=(BSTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->key) //树中存在相同关键字的结点，插入失败
return 0;
else if(k<T->key) //插入到T的左子树
return BST_Insert(T->lchild,k);
else //插入到T的右子树
return BST_Insert(T->rchild,k);
}
//按str[]中的关键字序列建立二叉树
void Creat_BST(BSTree &T,int str[],int n){
T=NULL;
int i=0;
//依次将每个关键字插入到二叉排序树中
while(i<n){
BST_Insert(T,str[i]);
i++;
}
}
// 中序遍历打印二叉排序树
void InOrder(BSTree T) {
if (T != NULL) {
InOrder(T->lchild);
cout << T->key << " ";
InOrder(T->rchild);
}
}
int main() {
BSTree T = NULL;
// 插入操作测试
int arr[] = {50, 30, 70, 20, 40, 60, 80};
int n = sizeof(arr) / sizeof(arr[0]);
Creat_BST(T, arr, n);
cout << "Binary Search Tree (Inorder): ";
InOrder(T);
cout << endl;
// 搜索操作测试
int searchKey = 40;
BSTNode* searchResult = BSTSearch(T, searchKey);
if (searchResult != NULL)
cout << "Key " << searchKey << " found in the tree." << endl;
else
cout << "Key " << searchKey << " not found in the tree." << endl;
// 删除操作测试
int deleteKey = 30;
cout << "Deleting key " << deleteKey << endl;
BST_Delete(T, deleteKey);
cout << "Binary Search Tree after deletion: ";
InOrder(T);
cout << endl;
return 0;
}
