数据结构 2015版(严).pdf

树和二叉树 第6章 树和二叉树 计算机科学与技术学院 主讲:孙玉霞 树和二叉树 目　录 6.1　树的定义和基本术语 6.2　二叉树 6.3　遍历二叉树和线索二叉树 6.4　树和森林 6.6　赫夫曼树及其应用 树和二叉树 ●基本要求： ● 　1）理解并准确叙述树、二叉树、森林及其有关概念并 熟悉它们的基本性质 ； 　2）熟悉树形结构的存储结构和中序线索二叉树； 　3）熟悉树的遍历方法，尤其是二叉树的前序、中序和 后序遍历的递归与应用，知道树形结构的若干应用。 ●学习重点： ● 　1）二叉树的性质与存储结构； 　2）二叉树的遍历算法。 树和二叉树 6.1　树的定义和基本术语 ●　树的定义 　 ●　树的定义 　　树的逻辑结构——它定义一类重要的非线性结构。树结 构在计算机科学的很多领域都得到了广泛的应用。 　　树结构可应用于诸如  编译程序中表示源程序的语法结构  数据库系统中的信息组织  文件目录  电路分析  社会各个组织和管理机构  家谱  书的章节编目  军队编制 　　树型结构是结点之间有分支、层次关系的结构，它非常 类似于自然界中的树。树型结构在客观世界中大量存在。 树和二叉树 6.1　树的定义和基本术语 6.1.1　树的定义 　 6.1.1　树的定义 ● 定义： ● 树 (tree)是n(n0)个结点的有限集T，其中： 1）有且仅有一个特定的结点，称为树的根 (root) 1） 2 ）当n1时，其余结点可分为m(m0)个互不相交的有限集 2 ） T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根 的子树 (subtree)。 ● 特点： ● 1）树中至少有一个结点——根。 1） 2 ）树中各子树是互不相交的集合。 2 ） 注1：树的定义具有递归性，即“树中还有树”。 树和二叉树 6.1　树的定义和基本术语 6.1.1　树的定义 　 6.1.1　树的定义 有子树的树 根 A 只有根结点的树 B C D A E F G H I J K L M (a)　只有根结点的树