4.1树与二叉树 课件-2022-2023学年浙教版（2019）高中信息技术选修1

4.1树与二叉树 选修一数据结构 树形逻辑结构的应用 试分析左图的数据结构，与我们之前学习过数据结构（数组、链表、字符串、队列、栈）有何区别？ 提示：可从前驱节点和后继节点描述 树的基本概念 1.可以描述为由n（n>=0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 节点：集合中的元素 空树：n=0的树 节点 节点 节点 节点 树的基本概念 子树：树中某个节点下面的所有节点所构成的树。 边：具有 n 个节点的树有 n-1 条边。 树的基本概念 节点的度：树的一个节点所拥有的子树个数 树的度：最大的节点的度。 节点的层数： 从根开始计算，根的层数为1 树的深度： 树中节点的最大层数 叶子节点 度为0 树的深度 根节点 度为5 B节点 度为2 5 4 线性表是一种特殊的树状结构，度为1。 A B G H C D E F I J K L M A节点的度为___________,B节点的度为______，I节点的度为 。 该树的度为____________。 该树的深度为____________。 5 2 3 5 该树共有____________个节点、________条边。 13 12 4 练习 树的基本概念 根节点：没有前驱的节点。 叶子节点：度为 0 的节点。 分支节点：度不为 0 的节点。 父节点或双亲节点： 上端节点称为下端节点的父节点。 孩子节点： 下端节点称为上端节点的孩子节点。 兄弟节点： 具有同一父节点的节点 A C D F G H J K L M A B E I，4个 B是H的父节点 H是B的孩子节点 H与G是兄弟节点 树的基本概念 A B G H C D E F I J K L 根节点/分支节点 叶子节点 叶子节点 叶子节点 叶子节点 叶子节点 叶子节点 叶子节点 叶子节点 分支节点 /内部节点 分支节点 /内部节点 分支节点 /内部节点 A节点的度为5，孩子节点为BCDEF F节点的父节点为A 层数为2 G、H为兄弟节点 该树的度为5——体现一棵树的宽度 该树的深度为4——体现一棵树的高度 树的基本概念 【思考】树形结构与我们之前学习过的线性结构有什么区别？ 线性结构 树形结构 除首尾元素外，每个元素均有且仅有一个直接前驱和一个直接后继。 树形结构是比较复杂的非线性结构， 1.只有一个没有前驱、只有后继的根节点 2.有多个没有后继只有一个直接前驱的叶子节点 3.其余节点都只有一个直接前驱和多个直接后继 树的基本概念 下列是否为树形结构？ 否，除根节点外，任何一个节点都有且仅有一个前驱 二叉树的基本概念 在猜数字游戏中，甲方事先在纸上写出一个100以内的正整 数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了” 或是“猜小了”，直至猜出正确结果。 乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果，具体过程可以抽象成下图的二叉树结构。 二叉树的基本概念 概念：是特殊的树，是一个具有n（n>=0）个节点的有限集合。 特点：①各节点的度都<=2 ② 分为左子树和右子树，且左右子树有序 A B C D E F G H A B C D E F G H ≠ 二叉树的基本概念 二叉树的形态 A A B A C (1)空二叉树 (2)只有根节点的单点树 (3)只有根节点和左子树 (4)只有根节点和右子树 A B C (5)左右子树均非空 练习 2.某棵树有5个节点,树的度和深度均为3,请画出这棵树所有可能的形态。 二叉树的性质 ①二叉树的第k层上最多有2k-1（k>=1）个节点。 应用： （1）如图所示： 第1层上最多只有 个节点； 第2层上最多只有 个节点 ……以此类推 第k层上最多只有 个节点。 1 2 2k-1 二叉树的性质 ②深度为k的二叉树最多有2k-1（k>=1）个节点。 应用： 根据性质①可知，第1层节点数最多为20。第2层节点数最多为21，以此类推，深度为k的二叉树节点最多有20+21+22+……+2k-1= 2k-1 （2）某二叉树深度为3，则该二叉树最多有______个节点。 7 二叉树的性质 应用： 如图甲，度为2的节点数为 ，叶子节点数为 ； 如图乙：度为2的节点数为 ，叶子节点数为 。 1 2 ③在任意一棵二叉树中，若度为2的节点数量为n2，叶子节点数为n0， 则 n0=n2+1 2 3 二叉树的性质 推理过程： ① 总节点数 n: ② 边的数量n-1 : 综上可知 : ③在任意一棵二叉树中，若