数据结构学习四树

学习数据结构笔记

二叉搜索树

二叉搜索树:一颗二叉树,可以为空。如果不为空,那么满足以下性质:

  1. 非空左子树的所有键值小于其根节点的的值

  2. 非空右子树的所有键值大于其根节点的值

  3. 左、右子树都是二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
Position Find(ElementType X, BinTree BST) {
if (!BST) return NULL; // 不存在的话就直接返回NULL
if ( X > BST->Data) {
return Find(X, BST->Data); // 递归在右树中查找
} else if(X < BST->Data) {
return Find(x, BST->Data); // 递归在左树中查找
} else {
return BST; // 查找成功,返回查找到的节点
}
}

// 代码中的递归都是尾递归,没有性能上的问题

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

1
2
3
4
5
6
7
8
9
10
11
12
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; // 查找失败返回NULL
}

查找最大值和最小值

根据二叉树的特性,如果查找最大和最小元素那么:

最大元素一定在树的最右分支的端节点上

最小元素一定在树的最左节点的端节点上

1
2
3
4
5
Position FindMid(BinTree BST) {
if (!BST) return NULL; // 树为空返回
if(!BST->Left) return BST; // 当前树没有左节点说明当前节点为最小值
return FindMid(BST->Lift); // 如果右左节点递归继续查找
}
1
2
3
4
5
6
7
// 迭代查找最大元值
Position FindMax(BinTree BST) {
if(BST){
while(BST->Rlght) BST = BST->Rlght;
}
return BST;
}

二叉搜索树的插入

插入的关键是找到元素应该插入的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
23
24
25
26
27
BinTree Delete(ElementType X, BinTree BST) {
Position Tmp;
if (!BST) return NULL; // 如果树为空则返回失败
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 = FinMid(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->Lift;
}
free(Tmp); // 释放被删除元素的内存
}
}
return BST;
}

平衡二叉树

平衡因子,简称 BF(T) = hl - hr
其中 hl 和 hr 分别为左、右子树的高度。

平衡二叉树空树,或者任一节点左、右子树高度差绝对值不能超过 1

平衡二叉树的调整。

不平衡的的发现者的麻烦节点在发现者的右子树的右边,因而叫做 RR 插入,需要 RR 旋转。

对应的还有 LL 旋转。

不平衡额发现者的麻烦节点在左子树的右边,因而叫做 LR 插入,需要 LR 旋转。