选择性必修1 专题四 树及应用-【导与练】2024高考信息技术一轮复习高中总复习第1轮教师用书word（浙江专用）

专题四　树及应用 一、树与二叉树 1.树(Tree)的几个基本概念 树是一种非线性的数据结构。 (1)树可以描述为由n(n≥0)个节点构成的一个有限集合以及在该集合上定义的一种节点关系。 (2)节点(Node):集合中的元素称为树的节点,n=0的树称为空树。 根节点:在树形结构中,没有前驱的节点称为根节点(Root),又称为开始节点。 父节点、孩子节点:在树形结构中,对于两个以边直接连接的节点,上端节点称为下端节点的父节点(Parent),下端节点称为上端节点的孩子节点(Child),简称为子节点。 (3)子树:树中某个节点下面所有节点所构成的树称为该节点的子树。 (4)边:树的两个节点之间如果有一条边连接,那么称这两个节点之间存在一条边。 对于一棵有n个节点的树,它有(n-1)条边。 (5)度(Degree) 节点的度:树的一个节点所拥有的子树个数称为该节点的度。 树的度:最大的节点的度称为树的度。 节点的度和树的度共同体现了树的宽度。 (6)叶子节点:度为0的节点称为叶子节点(Leaf),又称为终端节点。 (7)树的深度(高度):树中节点的层数(Level)从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的高度或深度(Depth)。 2.二叉树 (1)二叉树的定义 二叉树是指除根节点外的所有节点可分为两个互不相交的有限集合,分别称为左子树和右子树,左子树和右子树也是二叉树。 二叉树的所有节点的度都小于或等于2,当n=0时,二叉树是一棵空树。 二叉树的子树有左右之分,且左右子树的次序不能颠倒。 (2)二叉树的高度(深度) 二叉树中节点的最大层数称为二叉树的深度或高度。 (3)二叉树的五种形态: 3.特殊的二叉树 (1)满二叉树 符合满二叉树的两个条件为: ①每个节点的度数为2或为0。 ②所有叶子节点都在同一层。 (2)完全二叉树 符合完全二叉树的两个条件为: ①至多只有最下面两层中的节点度数小于2。 ②最下一层的叶子节点都依次排列在该层最左边位置。 (3)哈夫曼树 ①哈夫曼树又称最优二叉树。 ②树的带权路径长度(WPL)的计算公式为:WPL=Wi×Pi,其中,n为树中叶子节点的个数,Wi和Pi分别是第i个叶子节点的权值和从根节点到该路径的长度。 ③最优二叉树是指在具有n个带权叶子节点的所有二叉树中,称带权路径长度WPL最小的二叉树。 正确区分满二叉树和完全二叉树的方法: (1)满二叉树的判断方法:指叶子节点都在最下面一层上,除叶子节点外其他每个节点的度数为2。 (2)完全二叉树的判断方法:可将一棵二叉树先变为满二叉树,然后从上到下,同层从左到右的次序从1开始连续编号,如果能按从大到小的顺序连续删除该满二叉树的若干节点后得到该二叉树,则该二叉树为完全二叉树。 4.二叉树的性质 (1)二叉树的第k层上最多有2k-1(k≥1)个节点。 (2)深度为k的二叉树最多有(2k-1)(k≥1)个节点。 (3)在任意一棵二叉树中,若度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2+1。 二、二叉树的基本操作 1.建立二叉树的方法 建立二叉树的操作方法为:按照树层的顺序进行,先由第1层开始,依次到下一层,在每一层中按照从左到右的顺序创建节点。 2.用数组实现二叉树的创建 (1)完全二叉树 ①从二叉树的根节点开始,按从上到下、自左向右的顺序对n个节点进行编号,根节点的编号为0,最后一个节点的编号为n-1。 ②然后依次将二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一对应。 (2)非完全二叉树 ①对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示。 ②然后按照完全二叉树的方法,将节点存储在数组中。 3.用链表实现二叉树的创建 二叉树用链表实现时,二叉树的节点至少需要3个域:一个数据域和两个指针域。如下图所示: 其中lchild和rchild是指针域,存放指向节点的左孩子节点和右孩子节点的指针,data是数据域。 4.二叉树的遍历 (1)二叉树的遍历是指按照一定的规则和次序访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。 (2)根据访问根节点的先后顺序可以分为:前序遍历、中序遍历和后序遍历。 ①前序遍历 前序遍历,也称为先序遍历,前序遍历的规则为:若二叉树为空,则空操作返回;否则,先访问根节点,再访问左子树,最后访问右子树。 ②中序遍历 中序遍历的规则为:若二叉树为空,则空操作返回;否则,先访问左子树,再访问根节点,最后访问右子树。 ③后序遍历 后序遍历的规则为:若二叉树为空,则空操作返回;否则,先访问左子树,再访问右子树,最后访问根节点。 　　二叉树的三种遍历是根据访问根节点的先后次序来命名的,前序遍历的访问顺序为根左右(BL