4.1树与二叉树课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第四章浙教版（2019））

4.1 树与二叉树 《数据与数据结构》 一、树的概念 数据元素前面只有一个元素，后面可以有0个或多个元素相邻，所有元素之间的关系特征像一颗倒放的树。 数据元素之间存在一对多的关系（非线性的数据结构） 一、树的概念 可以描述为由n(n>=0)个节点(Node)构成的一个有限集合以及在该集合上定义的一种节点关系。 ① 树：集合中的元素称为树的节点，n=0的树为空树。 树的两个节点之间如果有一条边连接，那么称这两个节点之间存在一条边。 对于一棵具有n个节点的树，它有n-1条边。 A B C D E F 一、树的概念 A B C D E F G H I J K L M 第1层 第2层 第3层 第4层 子树：树中某个节点下面的所有节点所构成的树称为该节点的子树。 共?层(树的深度)，? 个节点，? 条边 A节点的子树有 B G H C D E I J K L M F 共4层(树的深度)，13个节点，12条边 一、树的概念 ② 度 节点的度：树的一个节点所拥有的子树数目。 树的度：一棵树中，最大的节点的度称为树的度。 A节点的度为 5 该树的度为 5 A B C D E F G H I J K L M 第1层 第2层 第3层 第4层 5 2 0 0 2 0 0 3 0 0 0 0 0 左图每个节点的度为？ 一、树的概念 ③ 节点 根节点(Root)：没有前驱、只有后继，也称为开始节点。 叶子节点：没有后继(度为0)、只有一个前驱，也称为终端节点。 分支节点：度不为0的节点。 根节点： A 叶子节点： G,H,C,D,K,L,M,J,F A B C D E F G H I J K L M 第1层 第2层 第3层 第4层 5 2 0 0 2 0 0 3 0 0 0 0 0 一、树的概念 A B C D E F G H I J K L M 第1层 第2层 第3层 第4层 父节点：上端节点称为下端节点的父节点或双亲节点。 孩子节点：下端节点称为上端节点的孩子节点。 兄弟节点：具有同一父节点的节点称为兄弟节点。 A节点是C节点的 父节点 G节点是B节点的 孩子节点 K,L,M节点互为 兄弟节点 一、树的概念 ④ 层数 从根开始计算，根的层数为1，其他节点层数加1。 最大层数称为树的高度或深度。 A B C D E F G H I J K L M 第1层 第2层 第3层 第4层 该树的深度为4 二、二叉树的概念 二叉树：是一个具有n（n>=0）个节点的有限集合。由根节点和两棵互不相交的左子树和右子树组成。重要特征：所有节点的度都小于或者等于2（0、1、2）。 A B C D E F G H 左子树 右子树 2 2 1 2 0 0 0 0 二、二叉树的概念 ① 二叉树的5种基本形态 ① 空二叉树 ② 只有根节点 ③ 只有根节点和左子树 ④ 只有根节点和右子树 ⑤ 左右子树均非空 二、二叉树的概念 ② 特殊的二叉树 A B C D E F G 第1层 第2层 第3层 A B C D E G 满足条件： (1)至多只有最下面两层中的节点度数小于2。 (2)最下一层的叶子节点都依次排列在该层最左边位置。 满足条件： (1)每个节点的度为2或0； (2)所有叶子节点都在同一层。 2 2 2 0 0 0 0 2 2 1 0 0 0 第1层 第2层 第3层 主要关系：满二叉树一定是完全二叉树，但完成二叉树不一定是满二叉树。 满二叉树 完全二叉树 三、二叉树的性质 ①二叉树的第k层上最多有__________个节点 ②深度为k的二叉树最多有___________个节点 ③在任意一棵二叉树中，若度为2的节点数量为n2，叶子节点（度为0的节点）数为n0，则 _________ 2k-1(k≥1) 2k -1(k≥1) n0=n2+1 A B C D E G A B C D A B C D E F G 第1层 第2层 第3层 1=20 2=21 4=22 2 2 2 0 0 0 0 每层节点数 第K层 2 1 0 0 2 2 1 0 0 0 四、实践与体验：二叉树的效率 假设在指定人群中，有一人携带了某种传染病病毒。现在需要通过病毒检测找出此人，分单样检测或混合检测两种方法，每次检测成本为100元。请分别用两种方法查找此人，并统计各自需要的检测成本。 1 2 3 4 5 6 7 8 四、实践与体验：二叉树的效率 1 2 3 4 5 6 7 8 单检法 混检法 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 5 6 7 8 5 6 +100 +100 +100 +100 +100 +100 +100 +100 +100 五、课堂总结 树的基本概念 子树 节点 度 深度 根节点 叶子节点 分支节点 父节点 孩子节点 兄弟节点 二叉树 基本形态 特殊的二叉树 性质 满二叉树 完全二叉树 2k-1 2k -1 5种 节点的度 树的度 最大层数 $$