第3章-哈工大-数据结构-树与二叉树.pdf

第3章 树与二叉树 数据结构与算法数据结构与算法数据结构与算法数据结构与算法 Data Structures and Alggorithms 张岩张岩 海量数据计算研究中心 哈工大计算机科学与技术学院 2016/11/10 哈工大计算机科学与技术学院 张岩 Slide 3-1 第第第第3333章章章章 树与二叉树树与二叉树树与二叉树树与二叉树 2016/11/10 Slide 3-2 第3章 树与二叉树 学习目标 学习目标 树型结构是一种非线性结构，反映了结点之间的层次关系， 在计算机科学与软件工程中有着广泛的应用在计算机科学与软件工程中有着广泛的应用。。 掌握树(森林)和二叉树的定义及其相关的术语 ； 重点掌握重点掌握二叉树的结构二叉树的结构、、性质性质，，存储表示和四种遍历算法存储表示和四种遍历算法；； 二叉树线索化的实质及线索化的过程； 了解了解树的结构性质树的结构性质、、存储表示方法和遍历算法存储表示方法和遍历算法；； 掌握森林(树)与二叉树的对应关系和相互转换方法； 了解树型结构的应用，重点掌握哈夫曼树的概念和构造方法 ，哈夫曼编码和译码的原理及实现方法。 2016/11/10 哈工大计算机科学与技术学院 张岩 Slide 3-3 第3章 树与二叉树 本章主要内容本章主要内容 3.1 树与二叉树的基本术语 3.2 二叉树 3.3 堆 3.4 选择树 33.55 树树 3.6 森林（树）与二叉树的相互转换 3 7 树的应用 3.7 树的应用 本章小结 2016/11/10 哈工大计算机科学与技术学院 张岩 Slide 3-4 第3章 树与二叉树 本章的知识点结构 本章的知识点结构 基本的数据结构（ADT ） 二叉树树、树树 （森林森林） 知识点结构 ADT定义 定义及相关术语 静态的结构 逻辑结构 逻辑结构及其特征 ADT 基本操作基本操作 （（算法算法）） 动态的操作动态的操作 基本 存储结构（描述） 静态的结构 数据 静态的结构 数据 实现 存储结构特点存储结构特点 ADT实现 结构 存储结构 存储结构的定义 动态的操作 操作 （算法）实现