浙教版（2019）高中信息选修一 2021—2022学年 4.1-4.2树与二叉树 知识点整理

树与二叉树 1.线性结构和非线性结构 线性结构的所有元素都是线性排列的，结构中必然存在唯一的“起点”和“终点”元素。且除首尾元素外，都有且只有一个“前驱”和“后驱”节点。 非线性结构则完全相反，结构中可能存在多个“起点”和“终点”元素。所有节点都可能存在0个或多个“前驱”和“后继”节点。 2.树形结构 树可以描述为由n（n>=0）个节点构成的一个有限集合，以及在该集合上定义的一种节点关系。 树形结构是一种特殊的非线性结构，其特点是：只有一个没有“前驱”，只有“后继”的根节点。有多个只有“前驱”没有“后继”的叶子节点，其余节点均只有一个“前驱”和多个“后继”。 3.描述树形结构的词 1）度（Degree）： 一个节点拥有的子树（后继节点）的个数称之为该节点的度,一棵树中最大的度称之为树的度。 2)节点（Node）： 没有前驱的节点称为根节点或开始节点；没有后驱的节点称为叶子节点或终端节点。 树中度不为0的节点称为分支节点，除根节点之外的分支节点称为内部节点。 节点间的前驱和后驱关系也称之为父子关系。 3)层数（Level）: 节点的层数从根节点开始计算，根节点的层数为1。树中节点最大层数称为树的高度或深度（Depth） 4.二叉树 二叉树是树形结构的一种特殊情况，其最大度为2。 1)完全二叉树和满二叉树 满二叉树：所有节点度为2或0；所有叶子节点在同一层 完全二叉树：最多只有最下两层度小于0；最下一层的叶子节点都在最左边。 2)二叉树的性质 二叉树第k层上最多有2k-1个节点（K>=1）； 深度为k的二叉树最多有2k-1个节点（k>=1）； 度为2的节点个数（n0）和度为0的节点个数（n2）满足n0=n2+1的关系； 3)二叉树的遍历：前序遍历（根左右），中序遍历（左根右），后序遍历（左右根） #二叉树的实现方式 <--这是用来举例的二叉树 #1.数组实现 #用数组实现二叉树，从根节点开始，从上而下，从左到右存储 #非完全二叉树需先补全为为完全二叉树后存储 #而又基于数组定义(元素数据类型相同)，空节点用''空字符填充 tree_s = ['A','B','C','','D','','E'] #2.链表实现 #用链表实现二叉树，头指针指向根节点 #节点格式：[左子树指针，值域，右子树指针] tree_item_head = 0 tree_item = [[1,'A',2],[-1,'B',3],[-1,'C',4],[-1,'D',-1],[-1,'E',-1]] #3.列表实现 #用列表实现二叉树格式[节点名称，左子树，右子树] tree_list = ['A',['B',None,['D',None,None]],['C',None,['E',None,None]]] #4.类实现 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.root = None def bulid(self,data):#假装这里有个建立二叉树的方法 def preTraverse(self,p): #前序遍历 if p is None: return print(p.value,end=',') self.preTraverse(p.left) self.preTraverse(p.right) def midTraverse(self,p): #中序遍历 if p is None: return self.midTraverse(p.left) print(p.value,end=',') self.midTraverse(p.right) def afterTraverse(self,p): #后序遍历 if p is None: return self.afterTraverse(p.left) self.afterTraverse(p.right) print(p.value,end=',') import random t = tree() list1 = [];n=0 while n<10: r = random.randint(0,99) if r not in list1: list1.append(r) t.build(r) #提纲上没有，我自己瞎写了一个 n+=1 print(r,end=',') t.preTraverse(t.root) t.midTraverse(t.root) t.afterTraverse(t.root) #基于数组存储二叉树的遍历 tree_s = ['A','B','C','','D','','E'] #前提：父节点f和子节点c的索引关系：c=2*f+1 #1.前序遍历 def preTraverse(tree_s,p): f=p;c=f*2+1 print(tree_s[f ... ...