数据结构与算法分析新视角（第2版） 课件 周幸妮 第5--9章 树---经典算法 .pptx

数据结构与算法分析

新视角

结点逻辑关系分层次的非线性结构树Chapter5DataStructuresandAlgorithmAnalysis

主要内容广义表的概念、存储结构、基本运算广义表树的定义和基本术语二叉树的概念、存储结构遍历二叉树哈夫曼树及其应用树

学习目标了解数据的逻辑结构从线性结构到非线性结构的过渡了解包含子结构的线性结构理解链式存储结构在表达非线性数据结构中的作用掌握树的概念、存储方法、基本运算了解广义表的概念、结构特点及其存储表示方法

实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.75.8

实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.75.8

5.1实际问题中的树及抽象

树引例1——日常生活中的树形结构8

树引例2——计算机的目录结构9

树引例3——树形结构的网站10

表达式树11

实际问题本质的抽象12一切具有层次关系的问题都可用树来描述

实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.75.8

树的逻辑结构14abdcefhgijlmnk层次结构一多对应非线性线性结构便不足以方便地描述这样的复杂情形树

5.2树的逻辑结构.2树的定义和基本术语树的操作定义

5.2树的逻辑结构.2树的定义和基本术语树的操作定义

树17定义AGDCBFE树形结构是一种重要的非线性结构，讨论的是层次和分支关系树是递归结构——在树的定义中又用到了树的概念树（tree）是包含n个结点的有限集合，其中：（1）有一个根结点，它只有直接后继，但没有直接前趋。（2）除根结点之外的其余数据元素被分为m个根的子树。当树的集合为空时，n=0，此时称为空树，空树中没有结点。

树的示意图18

树的图形表示方法19

树的相关术语20AGDCBFE包含一个数据元素及若干指向子树的分支结点的子树的根称为该结点的孩子一个结点的直接上层结点称为该结点的双亲同一双亲的孩子结点B、C、D是A的孩子，E、F是B的孩子A是B、C、D的双亲，B是E、F的双亲B、C、D是兄弟关系树的结点孩子结点双亲结点兄弟结点

树的相关术语21AGDCBFE结点层树的深度结点的度树的度叶子结点分枝结点有序树无序树森林Level1Level2Level3根结点的层定义为1；根的孩子为第二层结点，依此类推；树中最大的结点层度不为0的结点也叫终端结点，是度为0的结点树中最大的结点度结点子树的个数不考虑子树的顺序子树有序的树互不相交的树集合

树的基本术语——示例22E,K,L,GH,I,M

树的概念23我们熟悉的树形结构中，无序树、有序树有哪些？思考讨论讨论：有序树无序树的区别在于子树是否有顺序要求，有顺序要求的如家谱、书的目录等；无序的可以是计算机中的文件夹目录等。

5.2树的逻辑结构.2树的定义和基本术语树的操作定义

构造建立一棵树，初始化。树的基本操作查找可以是查找根结点、双亲结点、孩子结点、叶子结点、指定值的结点等。插入删除在指定位置插入/删除结点遍历沿着某条有哪些信誉好的足球投注网站路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题求深度计算树的高度。

实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.75.8

树的存储结构27存得进取得出A存数值存联系B树形结构的存储原则。非线性结构比线性关系复杂，存储树形结构问题的关键与重点。

树的存储结构2828树形结构存储结点间联系的原则是什么？一个双亲n个孩子对于设计好的存储结构，检验的标准则是只要在存储结构中能找到一个结点的这两种关系，那么这样的存储结构设计就是可行的。我们可以称之为“双亲孩子检验原则”。双亲孩子检验法思考讨论

5.3树的存储结构.2树的连续存储方式树的链式存储方式

5.3树的存储结构.2树的连续存储方式树的链式存储方式

树连续存储1——双亲孩子表示法31

树连续存储2——双亲表示法32

树连续存储3——孩子表示法33

5.3树的存储结构.2树的连续存储方式树的链式存储方式

树的链式存储方式35

树的链式存储方式36

1.同构型结构的特点有哪些？关于树的结构讨论37思考讨论2．什么样的树在用同构型结构时，空的指针域最少？讨论：同构型结构消除了异构型的缺陷，结构的统一化使管理变得容易，但若多数结点的度小于树的度，则部分指针域为空，造成存储空间的浪费。

38什么样的树在用同构型结构时，空链域最少