选择性必修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个叶子节点的权值和从根节点到该路径的长度。
学科网(北京)股份有限公司