《小白学数据结构》课件-第五章 树

主讲教师：1.树与二叉树什么是树呢？树树的定义树（Tree）是n（n≥0）个结点的有限集，它或为空树（n=0）；或为非空树，对于非空树T：(1)有且仅有一个称之为根结点；(2)除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。树树的基本术语（1）结点的度（2）树的度（4）分支结点（3）叶子结点树中结点拥有子树的数量称为结点的度树中所有结点度的最大值称为树的度树中度为零的结点称为叶子结点树中度不为零的结点称为分支结点ABCDEFGH4B02D01FGHB、D、F、G、H五个结点——叶子结点ACEA、C、E三个结点——分支结点二叉树二叉树的五种基本形态(a)——空二叉树(b)——仅有根结点的二叉树(c)——右子树为空的二叉树(d)——左子树为空的二叉树(e)——左右子树非空的二叉树二叉树的两个基本特点（1）结点的度小于等于2（2）二叉树是有序树，左右子树不能颠倒树与二叉树ABCDEGHF二叉树ABCDEFGH树一般的树可以有多个子结点，而二叉树每一个结点最多有两个子结点。二叉树的结点是有顺序的，分为左子树和右子树，一般的树中结点的顺序是无关的。(1)满二叉树

满二叉树第一层第二层第三层第四层137152456891011121314(2)完全二叉树定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。深度——4结点——12个完全二叉树满二叉树和完全二叉树有什么区别？满二叉树和完全二叉树满二叉树是完全二叉树的一种特例，所以满二叉树也是完全二叉树，但完全二叉树不一定都是满二叉树。123456789101112131415123456789101112满二叉树/完全二叉树完全二叉树2.二叉树的性质和存储结构二叉树的性质性质1:在二叉树的第i层上至多有2i-1个结点第一层第二层第三层第四层24835679101112131415二叉树的性质性质2:深度为k的二叉树至多有2k-1个结点深度42k-1=24-1=16-1=15至多有15个结点二叉树的性质性质3:对于任何一棵二叉树，若度为2的结点数有n2个，

则叶子数n0必定为n2＋1（即n0=n2+1）二叉树的存储结构顺序存储链式存储二叉树的存储结构(1)顺序存储顺序存储是用一组地址连续的存储单元，以层次的顺序存放二叉树的数据元素，结点的相对位置蕴含了结点之间的关系。二叉树的存储结构(2)链式存储顺序存储的存储效率不高有大量的空间浪费很多存储单元并没有存储数据链式存储二叉树的存储结构(2)链式存储二叉树的链式存储至少包含三个域：①数据域②左指针域（左孩子域）③右指针域（右孩子域）数据域左指针域右指针域3.二叉树的遍历二叉树的遍历指从根结点出发，顺着某一条搜索路径访问二叉树中的结点，使得每个结点的均被访问一次，而且仅被访问一次。二叉树的遍历先序遍历后序遍历中序遍历层序遍历二叉树的遍历①先序遍历如果二叉树为空，那么我们就不访问，否则我们访问根结点然后我们先序遍历左子树。左子树遍历完后，我们再去先序遍历右子树，按照根左右的顺序。这颗二叉树的先序遍历的序列是：A-B-C-D-E-F-G-H二叉树的遍历②后序遍历后序遍历按照左右根的顺序。先递归后序遍历的左子树，然后再访问它的右子树，最后访问根结点。这颗二叉树的后序遍历的序列是：D-E-C-B-H-G-F-A二叉树的遍历③中序遍历中序遍历算法按照左根右的顺序这颗二叉树的中序遍历的序列是：B-D-C-E-A-F-H-G二叉树的遍历④层序遍历按层从上到下，每层按一定顺序对树的结点进行遍历，一般情况下，每一层按照自左至右的顺序访问。这颗二叉树的层序遍历的序列是：A-B-F-C-G-D-E-H4.树、森林与二叉树的转换一棵树：无最大子结点数量限制二叉树：最大子结点数量为2树与二叉树结构的不同树与二叉树的转换方法使用链表存储所有树的结点，然后在链表中进行组织层序遍历对树中的每个结点进行递归，逐步转换为二叉树递归树与二叉树的转换方法特定结构转换的目的CAB树与二叉树的转换方法CDEFGHIAB加线操作：连接树中所有相邻兄弟去线操作：删除其他多余连线旋转操作：将整棵树顺时针旋转45°一棵树转换为二叉树树与二叉树的转换方法CDEFGHIAB一棵树转换为二叉树加线操作：连接树中所有相邻兄弟去线操作：删除其他多余连线旋转操作：将整棵树顺时针旋转45°森林与二叉树的转换森林与二叉树的转换将树中的每棵树转换成相应的二叉树01从第二棵二叉树始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子02将重新组织后的二叉树返回作为结果03步骤可能需要修改森林与二叉树的转换练习：将下图所示的森林转换为二叉树先将森林中的每棵树转换为二叉树选中轴心，将树顺时针旋转45°ABCDEFGHIKLNMOJ森林与二叉树的转换ABCDEFGHIKLNMOJ练习：将下图所示的森林转换为二叉树先将森林中的每棵树转换为二叉树选中轴心，将树顺时针旋转45°将二叉树依次连接起来森林与二叉树的转换练习：将下图所示的森林转换为二叉树先将森林中的每棵树转换为二叉树选中轴心，将树顺时针旋转45°将二叉树依次连接起来ABCDEFGHIKLNMOJ5.哈夫曼树用于数据压缩哈夫曼树的定义acbd将频率高的数据项分配的编码长度更短有效的减少了编码后数据的长度哈夫曼树的优点哈夫曼树基本术语acbd5724哈夫曼树的定义哈夫曼树又称最优二叉树，是一类带权路径长度最短的树。路径长度：

在二叉树中结点到根结点路径的边数。带权路径长度权值×路径长度=树的带权路径长度：所有结点的带权路径长度之和，记作WPL。例题计算cdab4257acbd5724adbc5724例：计算下图二叉树的WPL例题计算cdab4257WPL=4×2例：计算下图二叉树的WPL+7×3+5×3+2×1=46例题计算cdabacbd5724WPL=4×2+7×3+5×3+2×1=46WPL=7×2例：计算下图二叉树的WPL5724+5×2+2×2+4×2=36例题计算acbd5724adbc5724WPL=7×2+5×2+2×2+4×2=36WPL=35？例：计算下图二叉树的WPLcdab5724WPL=4×2+7×3+5×3+2×1=46哈夫曼树的概念根据一组具有确定权值的叶子结点，可以构造出不同的带权二叉树，其中带权路径长度最小的二叉树就是哈夫曼树。构建方法哈夫曼树的构建方法一、创建一个空的哈夫曼树，然后将所有的叶子结点的权值存储在一个有序的队列中。二、选择权值最小的两个结点，合并成一个新的二叉树，并将根结点权值设为两个结点权值之和。三、将加入队列中，重复步骤二，直到队列中只剩下一个结点为止。这个结点即为哈夫曼树的根结点。哈夫曼树的构建方法例：W={5，29，7，8，14，23，3，11}53111429782371114298823141529811231519291423………….哈夫曼树的构建方法81553871001119142923295842有效地利用数据的频率信息使得编码后的数据更加紧凑哈夫曼树的优势频繁出现不常出现短编码长编码可以使用更少的比特表示相同的数据对编码数据的频率信息进行分析将这些信息表示为二叉树根据树的构造方法对各个叶子结点分配编码哈夫曼编码哈夫曼编码的生成应用文件压缩图像压缩音频压缩6.堆（heap）树是一种递归的数据结构树通常用于表示层次关系树的定义

堆的定义二叉堆具有最大堆性质和最小堆性质堆中结点的值总是不大于或不小于其父结点的值堆1023172631644835455964594845313517231026最大堆10483145352317645926最小堆45173126643548102359堆具有树的递归性质，还具有额外的最大堆/最小堆的性质堆45173126643548102359堆完全二叉树堆是一颗完全二叉树，可以用二叉树的存储方式来表示堆

二叉树的存储方法顺序存储链式存储节省结点的指针空间便于访问孩子结点和双亲结点顺序存储的优点堆的基本操作向上调整将添加的新结点进行向上调整，直到调整的合适的位置满足堆的性质向下调整基本操作【例】：堆（Heap）的插入——示意图小根堆往小根堆中插入节点8小根堆第一次向上调整小根堆第二次向上调整小根堆第三次向上调整小根堆调整完成基本操