13.树与二叉树 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

第十三章 树与二叉树 一、线性结构和非线性结构 线性结构的所有元素都是线性排列的，结构中必然存在唯一的“起点”和“终点”元素。且除首尾元素外，都有且只有一个“前驱”和“后继”节点。例：链表、队列、栈 非线性结构则完全相反，结构中可能存在多个“起点”和“终点”元素。所有节点都可能存在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）； (2)深度为k的二叉树最多有2k-1个节点（k>=1）； (3)度为2的节点个数（n2）和度为0的节点个数（n0）满足n0=n2+1的关系； 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__(self,value,left=None,right=None): #构造方法         self.value = value         self.left = left         self.right = right class tree: #二叉树类     def __init__(self): #构造方法         self.ro