华师本科生数据结构课件-第6章-二叉树和树.ppt-

华师本科生数据构造课件 第 6 章 二叉树和树.ppt 1、第 6 章二叉树和树树型构造是一类重要的非线性构造。树型构造是结点之间有分支,并且具有层次关系的构造,它特别类似于自然界中的树。树构造在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。树构造在计算机领域中也有着广泛的应用,例如在编译程序中,用树构造来表示源程序的语法构造；在数据库系统中,可用树构造来组织信息；在分析算法的行为时,可用树构造来描述其执行过程等等。华中师范高校魏开平王敬华沈显君…系统软件办公室应用操作系统数据库数据构造离散数学……外语中文历史计科教务处科研处总务处………附中 ds.cs.ccnu.edu.cnauee 2、cneduccnucsdsbuaawhu………………课前导学 6.1 二叉树 6.2 遍历二叉树和线索二叉树 6.3 树和森林 6.4 树的应用第六章二叉树和树【学习目标】领悟树和二叉树的类型定义，理解树和二叉树的构造差异。熟记二叉树的主要特性，并把握它们的证明娴熟把握二叉树的各种遍历算法，并能灵敏运用遍历算法实现二叉树的其它操作。理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。娴熟把握二叉树和树的各种存储构造及其建立的算法。学会编写实现树的各种操作的算法。了解最优树的特性，把握建立最优树和赫夫曼编码的方法。【重点和难点】重点：二叉 3、树和树的遍历及其应用难点：编写实现二叉树和树的各种操作的递归算法学问点树的类型定义二叉树的类型定义二叉树的存储表示二叉树的遍历以及其它操作的实现线索二叉树树和森林的存储表示树和森林的遍历以及其它操作的实现最优树和赫夫曼编码【学习指南】 本章是整个课程的第三个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应当学会如何依据二叉树和树的构造及其操作的递归定义编写递归算法。本章必需完成的算法设计题为:6.1,6.3,6.4,6.5,6.6,6.7,6.8,6.9,6.10,6.11,6.12,6.14,6.16,6.17,6.18,6 4、.20,6.21,6.24,6.25,6.266.1 二叉树二、二叉树的根本性质一、二叉树的定义和根本术语三、二叉树的存储构造规律构造物理构造一、二叉树的定义和根本术语 1、二叉树的定义 2、二叉树的根本术语 3、二叉树的应用举例 4、二叉树的根本操作 1、二叉树定义二叉树 T 是 n 个结点的有限集合，其中 n≥0,当n=0 时，为空树，否那么，其中有一个结点为根结点，其余结点划分为两个互不相交的子集 TL、TR，并且 TL、TR 分别构成...