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

第6章信息论、哈夫曼编码与二叉树PARTB《可视化计算》1二叉树二叉树(BinaryTree)是指树的度为2的有序树。它是一种最简单、而且最重要的树，在计算机科学领域有着广泛地应用定义二叉树或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树2二叉树重要性质二叉树上终端节点数等于双分支节点数加1二叉树上第i层上至多有2i-1个节点(i≥1)性质3深度为h的二叉树至多有2h-1个节点4满二叉树(a)和完全二叉树(b)5理想平衡树(a)和普通二叉树(b)理想平衡树包含满二叉树和完全二叉树，但不一定是完全二叉树（a）6二叉树的存储结构顺序存储结构顺序存储一棵二叉树时，首先对该树中每个节点进行编号，然后以各节点的编号为下标，把各节点的值对应存储到一维数组中。树中各节点的编号与等深度的完全二叉树中对应位置上节点的编号相同7二叉树的存储结构链接存储结构在二叉树的链接存储：在每个节点中设置三个域：值域、左指针域和右指针域，其节点结构如下图：LeftdataRightdata表示值域，用于存储放入节点的数据元素，left和right分别表示左指针域和右指针域，用以分别存储左子和右子节点的存贮位置9二叉树的存储结构在节点结构中再增加一个parent指针域，用来指向其父节点这种存储结构既便于查找子节点，也便于查找父节点10带父节点的二叉链表字符串表达12二叉树的遍历二叉树的遍历是二叉树中所有其它运算的基础二叉树的遍历是指按照一定次序访问树中所有节点，并且每个节点的值仅被访问一次的过程根据二叉树的递归定义，遍历一棵非空二叉树的问题可分解为三个子问题：访问根节点遍历左子树遍历右子树。14堆排序堆排序(HeapSort)是一树形选择排序。父节点值大于或等于其子节点值的，叫“大根堆”（a）;父节点值小于或等于子节点值的，叫“小根堆”(b)16堆排序原理堆排序需要两个过程，一是建立堆，二是堆顶与堆底（堆的最后一个元素）交换位置所以堆排序有两个过程组成建堆的过程；调用建堆调整函数实现排序的过程17堆的基本操作1.建堆：数组具有对应的树表示形式一般情况下，树并不满足堆的条件；通过重新排列元素，可以建立一棵“堆化”的树2.插入一个元素：新元素被加入到表中随后树被更新以恢复堆次序3.删除一个元素：删除总是发生在根（root）节点处用表中的最后一个元素来填补空缺位置，结果树被更新以恢复堆的性质18堆排序过程请对对关键字序列14，15，32，68，54，100，876，45，32，10建堆并排序输出19为调试方便，将排序数据放在文件data.txt中，其中，第一个数据表示参与排序的数据个数(n)，后面则跟随排序数据；2.在main子图中，算法进行了建堆运算；3.creatheap子程序在建堆和排序输出两个过程中都会用到，①在第一轮循环中，用于建堆；②在heap_sort_output中，用于调整20堆排序流程Main子图21堆排序流程creatheap子程序22堆排序流程heap_sort_output子图23堆排序的应用场合一般的快速排序，归并排序都是在排序结束后才能确定数据元素的全部序列；堆排序则是每次输出一个堆顶元素，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小欲在一个大量数据的文件中，如含有5000个元素的记录文件中选取前10个最大的元素，可采用堆排序24二叉搜索树是一棵空树，或者是具有下列性质的二叉树：1.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2.若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；3.它的左、右子树也分别为二叉搜索树。25二叉搜索树的优点在二叉搜索树中进行查找的最糟时间复杂度为O(n)，等于顺序查找；但它支持动态查询（当搜索关键词没有在二叉搜索树中时，可以进行插入，这是该算法有别于大部分查找算法的特点）有很多二叉搜索树改良算法可以使树高为logn，如AVL树等是一种好的动态排序方法27构造二叉搜索树使用随机数产生一个无序序列，用该序列构造二叉搜索树，并使用金字塔（下图）的形式输出该树，以及排序结果28二叉搜索树的构建说明本例采用顺序形式保存二叉搜索树（BST）并输出排序结果，另外，需要考虑二叉搜索树的“金字塔”形式的输出（展示各种随机产生的二叉搜索树的特点）为了简化算法，本例没有将动态插入的功能列入，有兴趣者可自行设计29二叉搜索树的主要模块（I）main子图控制算法的整体流程init_first子图首次初始化使用随机数产生待排序数组a[]；数组元素个数可以设定；对两个BST的指针数组l[]、r[]分别进行初始化binary_sort子图进行BST的构建；30二叉搜索树Main子图31二叉搜索树init_first子图32二叉搜索树binary_sort子图33二叉搜索树主要模块（II）init_second子图进行第二次初始化，创建b[]向量数组，用于数组形式的BST的存贮binary_take_out子图实现输出金字塔式数组b[]的填充binary_output子图进行数组形式的BST输出；sort子程序进行BST排序结果的输出34二叉搜索树init_second子图35二叉搜索树：binary_take_out子图（I）36二叉搜索树：binary_take_out子图（II）37二叉搜索树binary_output子图38二叉搜索树sort子程序39小结与回顾树结构的理论和应用在实践上，是训练计算思维中的逻辑思维的良好机遇因为计算思维中的重要内容之一的逻辑思维是从一个从已知信息推导出未知信息的过程，而用数据方式对树结构进行抽象、描述、计算和应用，正是这样的一个典型过程41