4-1-4-2树与二叉树 二叉树的基本操作 课件-2021-2022学年浙教版（2019）高中信息技术选修1

第四章 树 选修1《数据与数据结构》 4.1 树与二叉树 学习目标 树 树 二叉树 树 树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。 树是由n（n≧0）个节点构成的一个有限集合以及在该集合上定义的一种节点关系。 ·树的概念 树 节点：集合中的元素。 空树：n = 0 的树。 子树：树中某个节点下面的所有节点 所构成的树。 边：一颗具有 n 个节点的树有 n-1 条边。 树 ·树的基本概念 树 第1层 第2层 第3层 第4层 ·节点的度：树的一个节点所拥有的子树个数。 ·树的度：最大的节点的度。 ·树的高度或深度：树中节点的最大层数。根的层数为1。 ·根节点：没有前驱的节点。 ·叶子节点：度为 0 的节点。 ·父节点或双亲节点：上端节点称为下端节点的父节点。 ·孩子节点：下端节点称为上端节点的孩子节点 叶子节点 度为0 树的深度 根节点 度为3 B节点 度为2 树 图状结构是一种比线性结构和树状结构更为复杂的非线性结构。广泛应用于计算机网络、通信工程等诸多领域。 ·图的概念 树 图中的节点关系：既可以是单向的，也可以是双向的，有无向图和有向图，有连通图和非连通图。 A C E B D A C E B D A C E B D A C E B D 无向图 有向图 连通图 非连通图 二叉树 树 ·二叉树的概念 二叉树是一个具有n（n≧0）个节点的一个有限集合，且各个节点的度小于或等于2，二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。 A B C D E F G H 二叉树 树 ·二叉树的形态 A A B A C (1)空二叉树 (2)只有根节点的单点树 (3)只有根节点和左子树 (4)只有根节点和右子树 A B C (5)左右子树均非空 二叉树 树 ·完全二叉树 设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达