2023年高考信息技术专题13 树与二叉树 知识点梳理(选修)(浙教版2019精品.pdfVIP

第十三章 树与二叉树 一、线性结构和非线性结构 线性结构的所有元素都是线性排列的，结构中必然存在唯一的“起点”和“终点”元素。且除首 尾元素外，都有且只有一个“前驱”和“后继”节点。例：链表、队列、栈 非线性结构则完全相反，结构中可能存在多个“起点”和“终点”元素。所有节点都可能存在0 个或多个“前驱”和“后继”节点。例：树、图 二、树形结构 树可以描述为由n （n=0）个节点和n-1条边构成的一个有限集合，以及在该集合上定义的 一种节点关系。树形结构是一种特殊的非线性结构，其特点是：只有一个没有“前驱”，只有 “后继”的根节点。有多个只有“前驱”没有“后继” 的叶子节点，其余节点均只有一个“前驱”和 多个“后继” 。 树的示例 1.描述树形结构的词 1.1节点名称（Node）： 根节点：树中唯一没有前驱的节点，也称开始节点(A) 叶子节点：树中没有后继的节点，也称终端节点(G,H,C,D,K,L,M,J,F) 分支节点：除叶子节点之外的所有节点(A,B,E,I) 内部节点：除根节点之外的分支节点(B,E,I) 1.2节点关系： 父子关系：节点间的前驱后继关系又称父子关系。例：B 是G 的父节点；G 是B 的子节点 兄弟关系：同一父节点下的所有节点关系称兄弟关系。例：G 和H 是兄弟节点 1.3度（Degree）： 节点的度：一个节点拥有的子树（后继节点）的个数称之为该节点的度。 树的度：一棵树中最大的度称之为树的度。 例：图中A 点的度为5，是该树中度最大的点，故该树的度为5 。 1.4层/深（Level）: 节点的层：节点的层数从根节点开始计算，根节点的层数为1。每经过一条边，层数加 1。 树的高度/深度（Depth ）：树中节点最大层数称为树的高度或深度。 例：图中K 点的深度为4，是该树中深度最大的点，故该树深度为4 。 三、二叉树 二叉树是树形结构的一种特殊情况，二叉树的度=2 。 1.完全二叉树和满二叉树 满二叉树：所有节点度为2 或0；所有叶子节点在同一层 完全二叉树：最多只有最深两层节点的度小于 2 ；最深一层的叶子节点依次排列在最左边。 2.二叉树的性质 (1)二叉树第k 层上最多有2k-1 个节点（K=1 ）； k (2)深度为k 的二叉树最多有2-1个节点（k=1）； (3)度为2 的节点个数（n ）和度为0的节点个数（n ）满足n =n+1 的关系； 2 0 0 2 3.二叉树的遍历 （以图中最左边二叉树为例） (1)前序遍历：先访问根节点，再访问左子树，最后访问右子树。例：A-B-D-E-C-G (2)中序遍历：先访问左子树，再访问根节点，最后访问右子树。例：D-B-E-A-C-G (3)后序遍历：先访问左子树，再访问右子树，最后访问根节点。例：D-E-B-G-C-A (4)层序遍历：从根节点开始，从上到下，从左到右。例：A-B-C-D-E-G 4.二叉树的建立和实现方式 （以图中最左边二叉树为例） 4.1数组实现 用数组存储二叉树之前，需要先将非完全二叉树补全为完全二叉树，然后按照层序遍历的顺 序逐个节点存储，中间空节点用空字符()或者None填充 tree = [A,B,C,D,E,,G] 这样存储的二叉树，父节点索引F 和左子节点索引C1 满足C1=2*F+1；右子节点索引C2 满 足C2=C1+1 4.2链表实现 用链表存储二叉树，链表头指针指向树根节点，节点格式定义为：[左指针，值域，右指针] tree_root = 0 tree_item = [[1,A,2],[3,B,4],[-1,C,5],[-1,D,-1],[-1,E,-1], [-1,G,-1]] 4.3列表实现 用列表存储二叉树，需要将子树嵌套到父节点的列表中，格式：[节点名，左子树，右子树]， 嵌套终点是节点的左右子树皆为None tree_list = [A,[B,[D,None,None],[E,None,None]],[C,None,[G,None,None]]] 4.4类实现 和链表类相似，抽象时也需要先将节点抽象为节点类，然后再抽象二叉树类。下面给出了二 叉树及其遍历的代码实现。遍历过程用到了递归【详见第14章】。 class node: #节点类 def __init