数据结构学习四树

发表于 更新于

学习数据结构笔记

二叉搜索树

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

  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
8
// 迭代查找最大元值
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 旋转。