数据结构课件树和二叉树

数据构造课件(第 6 章)树和二叉树 1、第六章树和二叉树,信阳师范学院计算机与信息技术学院,2024/12/19,数据构造 page2,信阳师范学院计算机与信息技术学院,主要内容,2024/12/19,数据构造 page3,信阳师范学院计算机与信息技术学院,把握二叉树的构造特性;生疏二叉树的各种存储构造的特点及适用范围；把握各种遍历策略的递归算法，能灵敏运用遍历算法实现二叉树的其他操作；理解二叉树线索化的实质,把握二叉树的线索化过程。生疏树的各种存储构造及其特点，把握树和与二叉树的转换方法，把握树的遍历方法；解哈夫曼树的特性，把握构造哈夫 2、曼树和哈夫曼编码的方法；,学习要点,2024/12/19,数据构造 page4,信阳师范学院计算机与信息技术学院,6.1.1 树的定义,注 1：过去很多书籍中都定义树为 n≥1，曾经有“空树不是树”的说法，但如今树的定义已修改。注 2：树的定义具有递归性，即“树中还有树”。,由一个或多个(n≥0)结点组成的有限集合 T，有且仅有一个结点称为根〔root〕，当 n1 时，其余的结点分为m(m≥0)个互不相交的有限集合 T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。,6.1 树的有关概念,2024/1 3、2/19,数据构造 page5,信阳师范学院计算机与信息技术学院,6.1.2 假设干术语,根叶子森林有序树无序树,——即根结点(没有前驱)——即终端结点(没有后继)——指 m 棵不相交的树的集合(例如删除 A 后的子树个数),——结点各子树从左至右有序，不能互换〔左为第一〕——结点各子树可互换位置。,2024/12/19,数据构造 page6,信阳师范学院计算机与信息技术学院,——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点〔孩子之间互称兄弟〕——即双亲位于同一层的结 4、点〔但并非同一双亲〕,,双亲孩子兄弟堂兄弟,6.1.2 假设干术语,2024/12/19,数据构造 page7,信阳师范学院计算机与信息技术学院,——即从根到该结点所经分支的全部结点——即该结点下层子树中的任一结点,,祖先子孙结点结点的度,——即树的数据元素——结点挂接的子树数,6.1.2 假设干术语,2024/12/19,数据构造 page8,信阳师范学院计算机与信息技术学院,结点的层次终端结点分支结点,树的度树的深度(或高度),——从根到该结点的层数〔根结点算第一层〕——即度为 0 的结点，即叶子——即度不 5、为 0 的结点〔也称为内部结点〕,——全部结点度中的最大值〔Max{各结点的度}〕——指全部结点中最大的层...