• 第五章第三节：数和二叉树的应用(二叉排序树和哈夫曼树及哈夫曼编码)

    文章目录

    1. 二叉排序树（BST）

    教程：二叉排序树（BST）

    1.1 二叉排序树的定义

    二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树
    1）若左子树非空，则左子树上所有结点的值均小于根结点的值。
    2）若右子树非空，则右子树上所有结点的值均大于根结点的值。
    3）左、右子树也分别是一棵二叉排序树。

    根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。
    例如,图5.21所示二叉排序树的中序遍历序列为1 2 3 4 6 8。在这里插入图片描述

    二叉排序树可用于元素的有序组织、搜索

    1.2 二叉排序树的查找操作

    二叉排序树的查找是从根结点开始的，沿某个分支逐层向下进行比较的过程。
     其查找过程描述如下：若二叉排序树非空，则将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定关键字值时，在根结点的左子树中查找；否则在根结点的右子树中查找。
    在这里插入图片描述
    在这里插入图片描述
    实现代码：

    //查找的递归算法
BSTNode *Search(BSTNode *root, int x){
    if(root->data == x){
        return root;
    }else if(x < root->data){
        return Search(root->left, x);
    }else{
        return Search(root->right, x);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    //查找的非递归算法
BSTNode *Search(BSTNode *root, int x){
    BSTNode *p = root;
    while(p!=NULL && p->data!=x){
        if(x < p->data)
            p = p->left;
        else
            p = p->right;
    }
    return p;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    1.3 二叉排序树的插入操作

    在这里插入图片描述

    //插入的递归算法
BSTNode *Insert(BSTNode *root, int x){
    if(root == NULL){
        root = CreateTreeNode(x);
        return root;
    }
    if(x < root->data){
        root->left = Insert(root->left, x);
    }
    if(x > root->data){
        root->right = Insert(root->right, x);
    }
    return root;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    //插入的非递归算法
BSTNode *Insert1(BSTNode *root, int x){
    BSTNode *parent = NULL;
    BSTNode *p = root;
    if(root == NULL){
        root = CreateTreeNode(x);
        return root;
    }
    while(p != NULL){
        parent = p;
        if(x < p->data){
            p = p->left;
        }else{
            p = p->right;
        }
    }
    if(parent->data >x){
        parent->left = CreateTreeNode(x);
    }else{
        parent->right = CreateTreeNode(x);
    }
    return root;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    1.4 二叉排序树的构造

    构造一棵二叉排序树就是依次输入数据元素，并将它们插入二叉排序树中适当位置上的过程。
     构造二叉排序树的过程：每读入一个元素，就建立一个新结点，若二叉排序树为空，则将新结点作为二叉排序树的根结点；若二叉排序树非空，则将新结点的值与根结点的值比较，若小于根结点的值，则插入左子树，否则插入右子树。

    在这里插入图片描述

    void Create(BSTNode *&root, int str[], int n){
    root = NULL;
    for(int i=0; i<n; i++){
        Insert(root, str[i]);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    1.4 二叉排序树的删除操作

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    //删除
bool Delete(BSTNode *p){
    //在二叉排序树中删除结点p, 并重新连接它的左右子树
    BSTNode *q, *s;
    //1.p为叶子结点
    if(p->left==NULL && p->right==NULL){
        p = NULL;
    }
    //2.1 p左子树为空, 重接右子树
    else if(p->left == NULL){
        q = p;
        p = p->right;
        free(q);
    }
    //2.2 p右子树为空, 重接左子树
    else if(p->right == NULL){
        q = p;
        p = p->left;
        free(q);
    }
    //3. p左右子树均不为空
    else{
        q = p;
        s = p->right; //找到p的右子树的最左端（中序直接后继）
        while(s->left != NULL){
            q = s;
            s = s->left;
        }
        p->data = s->data;
        
        if(q != p) //判断是否执行上述while循环
            q->left = s->right; //执行上述while循环，重接*q的左子树
        else
            q->right = s->right; //未执行上述while循环，重接*q的右子树，对于这个情况，可以参考代码后给出的示例图
        free(s);
    }
    return true;
}
bool DeleteBST(BSTNode *root, int x){
    if(root == NULL){
        return false;
    }else{
        if(x == root->data)
            return Delete(root); 
        else if(x < root->data)
            return DeleteBST(root->left, x);
        else
            return DeleteBST(root->right, x);
    }
}


    • 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
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    1.5 二叉排序树查找效率分析

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    代码实现

    二叉排序树的结点定义：

    typedef struct BSTNode{
    int data;
    struct BSTNode *left,*right;
}BSTNode;

    • 1
    • 2
    • 3
    • 4

    二叉树结点的创建：

    // 二叉树结点的创建
BSTNode *CreateTreeNode(int x){
    BSTNode *p=(BSTNode *)malloc(sizeof(BSTNode));
    p->data =x;
    p->left=NULL;
    P->right=NULL;
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    完整代码及实例

    #include
using namespace std;

typedef struct BSTNode{
    int data;
    struct BSTNode *left;
    struct BSTNode *right;
}BSTNode;

#define N 100 

//查找的递归算法
BSTNode *Search(BSTNode *root, int x){
    if(root->data == x){
        return root;
    }else if(x < root->data){
        return Search(root->left, x);
    }else{
        return Search(root->right, x);
    }
}
//查找的非递归算法
BSTNode *Search1(BSTNode *root, int x){
    BSTNode *p = root;
    while(p!=NULL && p->data!=x){
        if(x < p->data)
            p = p->left;
        else
            p = p->right;
    }
    return p;
}

//二叉树结点创建
BSTNode *CreateTreeNode(int x){
    BSTNode *p = (BSTNode *)malloc(sizeof(BSTNode));
    p->data = x;
    p->left = NULL;
    p->right = NULL;
    return p;
}

//插入的递归算法
BSTNode *Insert(BSTNode *root, int x){
    if(root == NULL){
        root = CreateTreeNode(x);
        return root;
    }
    if(x < root->data){
        root->left = Insert(root->left, x);
    }
    if(x > root->data){
        root->right = Insert(root->right, x);
    }
    return root;
}
//插入的非递归算法
BSTNode *Insert1(BSTNode *root, int x){
    BSTNode *parent = NULL; //记录当前结点的父结点
    BSTNode *p = root;
    if(root == NULL){
        root = CreateTreeNode(x);
        return root;
    }
    while(p != NULL){
        parent = p;
        if(x < p->data){
            p = p->left;
        }else{
            p = p->right;
        }
    }
    if(parent->data >x){
        parent->left = CreateTreeNode(x);
    }else if(parent->data < x){
        parent->right = CreateTreeNode(x);
    }
    return root;
}


//构建
void Create(BSTNode *&root, int str[], int n){
    root = NULL;
    for(int i=0; i<n; i++){
        root = Insert(root, str[i]);
    }
}

//删除
bool Delete(BSTNode *p){
    //在二叉排序树中删除结点p, 并重新连接它的左右子树
    BSTNode *q, *s;
    //1.p为叶子结点
    if(p->left==NULL && p->right==NULL){
        p = NULL;
    }
    //2.1 p左子树为空, 重接右子树
    else if(p->left == NULL){
        q = p;
        p = p->right;
        free(q);
    }
    //2.2 p右子树为空, 重接左子树
    else if(p->right == NULL){
        q = p;
        p = p->left;
        free(q);
    }
    //3. p左右子树均不为空
    else{
        q = p;
        s = p->right; //找到p的右子树的最左端（中序直接后继）
        while(s->left != NULL){
            q = s;
            s = s->left;
        }
        p->data = s->data;
        
        if(q != p) //判断是否执行上述while循环
            q->left = s->right; //执行上述while循环，重接*q的左子树
        else
            q->right = s->right; //未执行上述while循环，重接*q的右子树
        free(s);
    }
    return true;
}
bool DeleteBST(BSTNode *root, int x){
    if(root == NULL){
        return false;
    }else{
        if(x == root->data)
            return Delete(root); 
        else if(x < root->data)
            return DeleteBST(root->left, x);
        else
            return DeleteBST(root->right, x);
    }
}


void LevelOrder(BSTNode *root){
    queue<BSTNode *> treenode; //队列存储结点
    if(root != NULL)
        treenode.push(root); //根结点入队
    while(!treenode.empty()){
        BSTNode *p = treenode.front(); 
        treenode.pop(); //根结点出队
        cout<<p->data<<" "; //输出队首元素，即当前访问的结点值
        if(p->left != NULL){
            treenode.push(p->left);//如果有左子树，则将左子树的根结点入队
        }
        if(p->right != NULL){
            treenode.push(p->right);//如果有右子树，则将右子树的根结点入队
        }
    }
}

int main(){
    BSTNode *root;
    int n;
    cin>>n;
    int str[n];
    for(int i=0; i<n; i++){
        cin>>str[i];
    }
    Create(root,str,n); 
    cout<<"当前二叉排序树的层序遍历序列为：";
    LevelOrder(root);
    cout<<endl;
    BSTNode *p = Search(root, 17);
    cout<<"结点17的右孩子结点值为："<<p->right->data<<endl;
    DeleteBST(root, 78);
    cout<<"删除结点78后的二叉排序树的层序遍历序列为：";
    LevelOrder(root);
    return 0;
}


    • 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
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178

    2. 平衡二叉树（AVL树）

    教程：平衡二叉树（AVL树）

    2.1 平衡二叉树的定义

    在这里插入图片描述

    2.2 平衡二叉树的插入操作

    在这里插入图片描述

    在这里插入图片描述

    2.2.1 调整最小不平衡子树

    在这里插入图片描述

    2.2.1.1 在A的左孩子的左子树中插入导致不平衡（LL——右旋）

    在这里插入图片描述

    2.2.1.2 在A的右孩子的右子树中插入导致不平衡（LL——左旋）

    在这里插入图片描述在这里插入图片描述

    2.2.1.3 在A的左孩子的右子树中插入导致不平衡（LR——先左旋后右旋）

    在这里插入图片描述
    在这里插入图片描述

    2.2.1.4 在A的右孩子的左子树中插入导致不平衡（RL——先右旋后左旋）

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    练习：
    在这里插入图片描述
    在这里插入图片描述
    练习：
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2.3 查找效率分析

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3. 哈夫曼树和哈夫曼编码

    教程：哈夫曼树和哈夫曼编码

    3.1 带权路径长度

    在这里插入图片描述

    3.2 哈夫曼树的定义

    在这里插入图片描述

    3.3 哈夫曼树的构造

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3.4 哈夫曼编码

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  • 相关阅读:
    Linux·socket编程
    ZC-CLS381RGB颜色识别+8x8点阵指示（完）
    jsqlparser:基于抽象语法树(AST)遍历SQL语句的语法元素
    linux中的lo介绍及作用(回环接口 回环IP)
    【LeetCode】761. 特殊的二进制序列
    OpenCV 中的轮廓－轮廓的层次结构
    基于椭圆动态限制和免疫机理的路径规划算法
    数据结构之八大排序——简单选择排序
    vscode 版本比较插件 Git History Diff
    能获客的数字化官⽹运营操作指南
  • 原文地址：https://blog.csdn.net/qq_56897195/article/details/127779952