数据结构（C语言描述）教学课件斯庆巴拉第6章树.ppt

《数据结构（C语言描述）教学课件斯庆巴拉第6章树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树学习重点：树和二叉树的概念、性质和相互间的转换方法树和二叉树的遍历方法和实现算法哈夫曼树、线索二叉树和二叉排序树的构造方法与应用第6章树6.1实例1：文件目录管理6.2树的逻辑结构6.3树的遍历6.4实例2：通信中电文编码6.5二叉树定义、存储结构6.6二叉树遍历6.7树与二叉树的转换6.8应用举例本章总结6.1实例1：文件目录管理6.1.1问题描述6.1.2问题的分析6.1.3实现算法6.1.1问题描述在操作系统中对文件进行访问时提供按名存取机制，只需给出文件名，就可以访问到相应的文件，而无需知道文件的存储位置。如何实现按名存取机制呢？6.1

2、.2问题的分析文件系统将这些说明部分的全部信息集中起来构成文件控制块（FCB），文件目录由文件控制块组成。再将所有的文件目录组合在一起构成一个目录文件，目录文件以树型目录结构存储。树型目录结构中文件目录的第一级系统目录为树的根结点，定义为根目录，文件目录的第二级和以下各级目录均为树的分支结点（非终结点），均定义为子目录，只有树的叶子结点（终结点）才为文件。所以实现文件的按名存取，就是从目录结构的根目录开始直到所要找的文件为止。6.1.3实现算法实现算法：（略）结论：文件目录结构是一种树型结构，目录树中的根目录是树的根结点，根目录下各级子目录和文件是树的

3、其余结点。对处在同一层的各个子目录和文件进行比较可以发现各个子目录和文件都只有一个共同的上一级目录，而同一层的各个子目录可以有任意多个下级子目录和文件。文件目录结构中的各个目录和文件都满足树型结构的特征。6.2树的逻辑结构6.2.1树的逻辑结构6.2.2树的相关术语6.2.1树的逻辑结构树或者是一棵空树，或者是一棵非空树。一棵非空树由n（n≥0）个结点来组成。它满足以下条件：l有且仅有一个根结点，它没有前驱结点l其余结点构成m(m>=0)棵互不相交的树，称为该树的子树。每棵子树又是一棵树（递归定义）。逻辑结构：一棵树由若干个结点组成，元素以结点的形式存

4、在；关系：树的各个结点间是一对多的关系，即除根结点外，所有结点有且仅有一个前驱结点，所有结点或者没有后继结点，或者有任意多个后继结点。6.2.2树的相关术语根结点：唯一没有前驱的结点。所有非空树，都有唯一的一个根结点。结点的度：结点所拥有的子树的个数，或者结点所拥有的后继结点的个数。树的度是指树中所有结点的度的最大值。终端结点（叶子结点）：度为0的结点，或者树中没有后继的结点。非终端结点（分支结点）：度不为0的结点，或者指有后继的结点。父结点、孩子结点：对一个结点来讲，它的前驱结点是它的父结点（双亲结点）；它的后继结点是它的孩子结点（子结点）。兄弟结点

5、是指父结点相同的结点，即前驱结点是相同的结点。结点的深度是指该结点在树中所处的层数，根结点所在的层为第一层。树的深度是指树中结点的最大层次数。有序树是指构成树的各子树，从左到右有一定顺序，不能互相交换的树。无序树是指构成树的各子树是无顺序的，可以互相交换的树。森林是指若干棵互不相交的树。6.3树的遍历6.3.1先根遍历6.3.2后根遍历6.3.3按层遍历树的遍历指的是按照某一种顺序访问树中的所有结点，并且每个结点只访问一次。树的遍历顺序：先根遍历（先序遍历）、后根遍历（后序遍历）和按层遍历。6.3.1先根遍历先根遍历指如果树非空，则按下列规则进行遍历：

6、l先访问树的根结点。l从左到右访问根结点的所有子树。l对子树也按先根遍历顺序来访问所有的结点。6.3.2后根遍历后根遍历指如果树非空，则按下列规则进行遍历：l先从左到右访问根结点的所有子树。l后访问树的根结点。l对子树也按后根遍历顺序来访问所有的结点。6.3.3按层遍历按层遍历指如果树非空，则按下列规则进行遍历：l从第一层开始，从上到下顺序遍历各层，同一层从左到右访问各个结点。l树的根结点所在层定义为第一层，依次类推。6.4实例2：通信中电文编码6.4.1问题的描述6.4.2问题的分析6.4.3实现算法6.4.1问题的描述在电信科技日新月异的今天，人们

7、早已淡忘了，曾经风靡一时的电报。电报的原文发送时，都按一定的规则翻译成编码，以编码的形式传送。收到的电文中，每个文字的下面都会有一个数字编码。下面介绍的也是一种电报的编码方法：发送的电文翻译成0和1的数字序列。6.4.2问题的分析电报主要依靠将传送的文字转换成由二进制数组成的字符串进行传送。第一种解决方法：将所有传送的文字都转换成等长的二进制字符串来传送，接收者只需按等长进行译码。第二种解决方法：对电文中出现的字符设计长度不等的字符编码，对电文中出现次数比较多的字符采用尽可能短的字符编码，则传送的信息的长度就可以减少了。前缀编码（哈夫曼编码）：每个字符

8、的编码都不是另一个字符的编码的前缀。构造字符哈夫曼编码的方法：将每个字符按在代码中出现的次数为