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

第6章信息论、哈夫曼编码与二叉树PART

B1《可视化计算》二叉树

二叉树(Binary

Tree)是指树的度为2的有序树。它是一种最简单、而且最重要的树，在计算机科学领域有着广泛地应用

定义

二叉树或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树2二叉树的例子3二叉树重要性质

二叉树上终端节点数等于双分支节点数加1

二叉树上第i层上至多有2i-1个节点(i≥1)

性质3深度为h的二叉树至多有2h-1个节点4满二叉树(a)和完全二叉树

(b)5理想平衡树(a)和普通二叉树(b)理想平衡树包含满二叉树和完全二叉树，但不一定是完全二叉树（a）6二叉树的存储结构7

顺序存储结构

顺序存储一棵二叉树时，首先对该树中每个节点进行编号，然后以各节点的编号为下标，把各节点的值对应存储到一维数组中。树中各节点的编号与等深度的完全二叉树中对应位置上节点的编号相同顺序存储的二叉树8二叉树的存储结构

链接存储结构

在二叉树的链接存储：在每个节点中设置三个域：值域、左指针域和右指针域，其节点结构如下图：LeftdataRightdata表示值域，用于存储放入节点的数据元素，

left和right分别表示左指针域和右指针域，用以分别存储左子和右子节点的存贮位置9二叉树的存储结构

在节点结构中再增加一个parent指针域，用来指向其父节点

这种存储结构既便于查找子节点，也便于查找父节点10二叉链表的字符串数组表达11带父节点的二叉链表字符串表达12在RAPTOR中建立二叉树13二叉树的遍历

二叉树的遍历是二叉树中所有其它运算的基础

二叉树的遍历是指按照一定次序访问树中所有节点，并且每个节点的值仅被访问一次的过程

根据二叉树的递归定义，遍历一棵非空二叉树的问题可分解为三个子问题：

访问根节点

遍历左子树

遍历右子树。14前序遍历算法15堆排序

堆排序(Heap

Sort)是一树形选择排序。

父节点值大于或等于其子节点值的，叫“大根堆”（a）;父节点值小于或等于子节点值的，叫“小根堆”(b)16堆排序原理

堆排序需要两个过程，一是建立堆，二是堆顶与堆底（堆的最后一个元素）交换位置

所以堆排序有两个过程组成

建堆的过程；

调用建堆调整函数实现排序的过程17堆的基本操作18

1.建堆：数组具有对应的树表示形式

一般情况下，树并不满足堆的条件；通过重新排列元素，可以建立一棵“堆化”的树

2.插入一个元素：新元素被加入到表中

随后树被更新以恢复堆次序

3.删除一个元素：删除总是发生在根（root）节点处

用表中的最后一个元素来填补空缺位置，结果树被更新以恢复堆的性质堆排序过程19

请对对关键字序列14，15，32，68，54，100，876，45，32，10建堆并排序输出堆排序实现说明20为调试方便，将排序数据放在文件

data.txt中，其中，第一个数据表示参与排序的数据个数(n)，后面则跟随排序数据；在main子图中，算法进行了建堆运算；creatheap子程序在建堆和排序输出两个过程中都会用到，①

在第一轮循环中，用于建堆；②

在heap_sort_output中，用于调整堆排序流程

Main子图21堆排序流程

creatheap子程序22堆排序流程

heap_sort_output

子图23堆排序的应用场合

一般的快速排序，归并排序都是在排序结束后才能确定数据元素的全部序列；

堆排序则是每次输出一个堆顶元素，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小

欲在一个大量数据的文件中，如含有5000个元素的记录文件中选取前10个最大的元素，可采用堆排序24二叉搜索树

是一棵空树，或者是具有下列性质的二叉树：

1.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2.若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3.它的左、右子树也分别为二叉搜索树。25二叉搜索树的例子26二叉搜索树的优点

在二叉搜索树中进行查找的最糟时间复杂度为O(n)，等于顺序查找；

但它支持动态查询（当搜索关键词没有在二叉搜索树中时，可以进行插入，这是该算法有别于大部分查找算法的特点）

有很多二叉搜索树改良算法可以使树高为logn，如AVL树等

是一种好的动态排序方法27构造二叉搜索树

使用随机数产生一个无序序列，用该序列构造二叉搜索树，并使用金字塔（下图）的形式输出该树，以及排序结果28二叉搜索树的构建说明29

本例采用顺序形式保存二叉搜索树（BST）并输出排序结果，另外，需要考虑二叉搜索树的“金字塔”形式的输出（展示各种随机产生的二叉搜索树的特点）

为了简化算法，本例没有将动态插入的功能列入，有兴趣者可自行设计二叉搜索树的主要模块（I）30

main子图控制算法的整体流程

init_first子图首次初始化使用随机数产

生待排序数组a[]；数组元素个数可以设定；对两个BST的指针数组l[]、r[]分别进行初

始化

binary_sort子图进行BST的构建；二叉搜索树31

Main子图二叉搜索树32

init_first子图二叉搜索树33

binary_sort子图二叉搜索树主要模块（II）34

init_second子图进行第二次初始化，创建

b[]向量数组，用于数组形式的BST的存贮

binary_take_out子图实现输出金字塔式数组b[]的填充

binary_output子图进行数组形式的BST输出；

sort子程序进行BST排序结果的输出二叉搜索树35

init_second子图二叉搜索树：binary_take_out子图（I）36二叉搜索树：binary_take_out子图（II）37二叉搜索树

binary_output子图38二叉搜索树39