陈越《数据结构》第五讲 树(下)

5.1 堆(heap)(解决优先队列)

5.1.1 定义



优先队列(Priority Queue):特殊的“ 队列”,取出元素的顺序是依照元素的优先权(关键字) 大小,而不是元素进入队列的先后顺序。

即可认为
每个加入队列的值有一定的意义(大小),进入队列没有规定,但是出队列要根据一定的意义(大小)出队列。

5.1.2 存储和特性


我们运用优先队列


特性:
1. :用数组表示的完全二叉树
2. $\color{有序性** : 任一结点 的关键字是其子树所有结点的最大值( 或最小值)
- “最大堆(MaxHeap)”, 也称”大顶堆”:最大值
- “最小堆 ( MinHeap)”, 也称”小顶堆”:最小值

5.1.3 堆抽象数据类型


这里写图片描述

5.1.3.1插入


这里写图片描述

5.1.3.2 删除


这里写图片描述

5.1.4 总结


1.了解堆的定义和结构;
2.会识别最大堆和最小堆,能做出相关习题;
3.编程(插入、删除、建立)。


5.2 哈夫曼树(解决编码)

5.2.1 定义


:将百分制的考试成绩转换成五分制的成绩?

如何根据结点不同的查找频率构造更有效的搜索树?

(WPL) : 设二叉树有 n 叶子结点 ,每个叶子结点带有权值 wk ,从根结点到每个叶子结点的长度为 lk ,则每个叶子结点的带权路径长度之和就是:
WPL=ni=1wklk

(最小二叉树):WPL最小的二叉树。

5.2.2 构造与特点


1.

  1. 把数据从小到大进行排列(构造最小堆);
  2. 每次把 权值最小的两棵 二叉树(节点)合并。

2.

  1. 没有度为1 的结点;
  2. n 个叶子结点的 哈夫曼树共有 2n1 个结点 ;
  3. 哈夫曼树的任意非叶节点左右子树交换 后仍是哈夫曼树 ;
  4. 对同一组 权值 {w1,w2,,wn} ,存在 不同构的两棵哈夫曼树

例如:
对一组 权值 {1,2,3,3} ,可构成:不同构 的两棵哈夫曼树。

5.2.3 哈夫曼树编码


1.
给定一段字符串,如何 对字符进行编码 ,可以使得该字符串的编码存储空间最少!

:假设有一段文本,包含 58 个字符,并由以下 7 个字符构: aeistspnl ;这 7 个字符出现的次数不同。如何对这7 个字符进行编码,使得总编码空间最少?

进行不等长编码需注意:
(prefix code ):任何字符的编码都不是另一字符编码的前缀

进行编码(编码代价最小):
(1 )左右分支: 0 1
(2 )字符只在叶结点上。
这里写图片描述

2.

  1. 为五个使用频率不同的字符设计哈夫曼编码,下列方案中哪个不可能是哈夫曼编码?
    A. 00,100,101,110,111
    B. 000,001,01,10,11
    C. 0000,0001,001,01,1
    D. 000,001,010,011,1

**解析:**A

根据编码规则建立一个编码树,然后对于任何给定的要判断的码,起始结点设为根结点,读到一个0,转到左儿子,读到一个1,转到右儿子,直到读完,这时检查走到的结点是不是叶子结点~因为没有提到是最优编码,所以构成的编码树树不一定是哈夫曼树,该结点不必须由两个儿子。


5.3 集合


  1. : 交、并、补、差,判定 一个元素是否属于某一集合。
  2. :集合 查找 某元素属于什么集合。
    • 可以 用 树结构 表示集合;
    • 采用数组存储形式。
  1. 查找(返回根节点)
    这里写图片描述

  2. 并集合(一个根结点的父结点指针设置成另一个根结点 的数组下标
    这里写图片描述

5.4


这里写图片描述

#include<stdio.h>

#define MAXH 1001
#define MINH -10001

int H[MAXH],size;

void Create()
{
    size = 0;
    H[0] = MINH;
    /*设置"岗哨"*/
}

void Insert(int X)
{
    int i;
    for(i=++size;H[i/2]>X;i/=2)
        H[i] = H[i/2];
    H[i] = X;
}

int main()
{
    int count,outCount,x,i,outNumb;
    scanf("%d %d",&count,&outCount);
    Create();
    for(i = 0; i < count; i++)
    {
        scanf("%d",&x);
        Insert(x);
    }
    for(i = 0; i < outCount ; i++)
    {
        scanf("%d",&outNumb);
        printf("%d",H[outNumb]);
        while(outNumb>1)
        {
            outNumb/=2;
            printf(" %d",H[outNumb]);
        }
        printf("\n");
    }
    return 0;
}
相关文章
相关标签/搜索