《可视化计算》第6章信息论、哈夫曼编码与二叉树

1、可视化计算第6章信息论、哈夫曼编码与二叉树 第6章信息论、哈夫曼编码与二叉树 PART B 可视化计算 1 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树 二叉树(Binary Tree)是指树的度为2的有 序树。它是一种最简单、而且最重要的树 ，在计算机科学领域有着广泛地应用 定义 二叉树或者是一棵空树空树，或者是一棵由一个根根 节点节点和两棵互不相交的分别称作根的左子树左子树和 右子树右子树所组成的非空树，左子树和右子树又同 样都是一棵二叉树 2 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树的例子 3 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树重要性质二叉树重要性质 二叉

2、树上终端节点 数等于双分支节点 数加1 二叉树上第i层上至 多有2i-1个节点 (i1) 性质性质3 3深度为h的二 叉树至多有2h-1个节 点 4 可视化计算第6章信息论、哈夫曼编码与二叉树 满二叉树(a)和完全二叉树 (b) 5 可视化计算第6章信息论、哈夫曼编码与二叉树 理想平衡树(a)和普通二叉树(b) 理想平衡树包含满二叉树和完全二叉树，理想平衡树包含满二叉树和完全二叉树， 但不一定是完全二叉树（但不一定是完全二叉树（a） 6 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树的存储结构二叉树的存储结构 顺序存储结构 顺序存储一棵二叉树时，首先对该树中每个节 点进行编号，然后以各节点

3、的编号为下标，把 各节点的值对应存储到一维数组中。树中各节 点的编号与等深度的完全二叉树中对应位置上 节点的编号相同 7 可视化计算第6章信息论、哈夫曼编码与二叉树 顺序存储的二叉树 8 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树的存储结构二叉树的存储结构 链接存储结构 在二叉树的链接存储：在每个节点中设置三个 域：值域、左指针域和右指针域，其节点结构 如下图： LeftdataRight data表示值域，用于存储放入节点的数据元素，表示值域，用于存储放入节点的数据元素， left和和right分别表示左指针域和右指针域，分别表示左指针域和右指针域， 用以分别存储左子和右子节点的存贮

4、位置用以分别存储左子和右子节点的存贮位置 9 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树的存储结构二叉树的存储结构 在节点结构中再增加一个parent指针域， 用来指向其父节点 这种存储结构既便于查找子节点，也便于 查找父节点 10 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉链表的字符串数组表达二叉链表的字符串数组表达 11 可视化计算第6章信息论、哈夫曼编码与二叉树 带父节点的二叉链表字符串表达带父节点的二叉链表字符串表达 12 可视化计算第6章信息论、哈夫曼编码与二叉树 在在RAPTOR中建立二叉树中建立二叉树 13 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉树的遍历

5、二叉树的遍历是二叉树中所有其它运算的基础 二叉树的遍历是指按照一定次序访问树中所有节 点，并且每个节点的值仅被访问一次的过程 根据二叉树的递归定义，遍历一棵非空二叉树的 问题可分解为三个子问题： 访问根节点 遍历左子树 遍历右子树。 14 可视化计算第6章信息论、哈夫曼编码与二叉树 前序遍历算法 15 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序 堆排序(Heap Sort)是一树形选择排序。 父节点值大于或等于其子节点值的，叫“ 大根堆”（a）;父节点值小于或等于子节 点值的，叫“小根堆” (b) 16 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序原理 堆排序需要两个过程，一是建

6、立堆，二是 堆顶与堆底（堆的最后一个元素）交换位 置 所以堆排序有两个过程组成 建堆的过程； 调用建堆调整函数实现排序的过程 17 可视化计算第6章信息论、哈夫曼编码与二叉树 堆的基本操作 1.建堆：数组具有对应的树表示形式 一般情况下，树并不满足堆的条件；通过重新 排列元素，可以建立一棵“堆化”的树 2.插入一个元素：新元素被加入到表中 随后树被更新以恢复堆次序 3.删除一个元素：删除总是发生在根（ root）节点处 用表中的最后一个元素来填补空缺位置，结果 树被更新以恢复堆的性质 18 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序过程 请对对关键字序列14，15，32，68，54，

7、100，876，45，32，10建堆并排序输出 19 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序实现说明 为调试方便，将排序数据放在文件 data.txt中，其中，第一个数据表示参与 排序的数据个数(n)，后面则跟随排序数 据； 在main子图中，算法进行了建堆运算； creatheap子程序在建堆和排序输出两个 过程中都会用到， 在第一轮循环中，用于建堆； 在heap_sort_output中，用于调整 20 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序流程 Main子图 21 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序流程 creatheap子程序 22 可视化计算第

8、6章信息论、哈夫曼编码与二叉树 堆排序流程 heap_sort_output 子图 23 可视化计算第6章信息论、哈夫曼编码与二叉树 堆排序的应用场合 一般的快速排序，归并排序都是在排序结 束后才能确定数据元素的全部序列； 堆排序则是每次输出一个堆顶元素，然后 对堆进行再调整，保证堆顶元素总是当前 剩下元素的最大或最小 欲在一个大量数据的文件中，如含有5000个元 素的记录文件中选取前10个最大的元素，可采 用堆排序 24 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树 是一棵空树，或者是具有下列性质的二叉 树： 1. 若它的左子树不空，则左子树上所有节点的 值均小于它的根节点的值；

9、2. 若它的右子树不空，则右子树上所有节点的 值均大于它的根节点的值； 3. 它的左、右子树也分别为二叉搜索树。 25 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树的例子 26 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树的优点 在二叉搜索树中进行查找的最糟时间复杂 度为O(n)，等于顺序查找； 但它支持动态查询（当搜索关键词没有在 二叉搜索树中时，可以进行插入，这是该 算法有别于大部分查找算法的特点） 有很多二叉搜索树改良算法可以使树高为 logn，如AVL树等 是一种好的动态排序方法 27 可视化计算第6章信息论、哈夫曼编码与二叉树 构造二叉搜索树 使用随机数产生一个无

10、序序列，用该序列 构造二叉搜索树，并使用金字塔（下图） 的形式输出该树，以及排序结果 28 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树的构建说明 本例采用顺序形式保存二叉搜索树（BST） 并输出排序结果，另外，需要考虑二叉搜 索树的“金字塔”形式的输出（展示各种 随机产生的二叉搜索树的特点） 为了简化算法，本例没有将动态插入的功 能列入，有兴趣者可自行设计 29 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树的主要模块（I） main子图控制算法的整体流程 init_first子图首次初始化使用随机数产 生待排序数组a；数组元素个数可以设定 ；对两个BST的指针数组l、r分

11、别进行 初始化 binary_sort子图进行BST的构建； 30 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树 Main子图 31 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树 init_first子图 32 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树 binary_sort子图 33 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树主要模块（II） init_second子图进行第二次初始化，创建 b向量数组，用于数组形式的BST的存贮 binary_take_out子图实现输出金字塔式数 组b的填充 binary_output子图进行数组形式的BST输 出； sort子程序进行BST排序结果的输出 34 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树 init_second子图 35 可视化计算第6章信息论、哈夫曼编码与二叉树 二叉搜索树：binary_take_out子图（I）