数据结构基础知识08--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（八） 【知识要点】 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)二叉树的高度(深度) 二叉树中节点的最大层数称为二叉树的深度或高度。 (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的节点数多1个。 5.建立二叉树的方法 建立二叉树的操作方法为：按照二叉树层的顺序进行，先由第1层开始，依次到下一层，在每一层中按照从左到右的顺序创建节点。 6.用数组实现二叉树的创建 (1)完全二叉树 ①从二叉树的根节点开始，按从上到下、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n－1。 ②然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 (2)非完全二叉树 ①对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。 lchild data rchild ②然后按照完全二叉树的方法，将节点存储在数组中。 7.用链表实现二叉树的创建 二叉树用链表实现时，二叉树的节点至少需要三个域：一个数据域和两个指针域。如图所示。 其中lchild和rchild是指针域，存放指向节点的左孩子节点和右孩子节点的指针，data是数据域。 8.二叉树的遍历 (1)二叉树的遍历是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。 (2)根据访问根节点的先后顺序可以分为：前序遍历、中序遍历和后序遍历。 ①前序遍历 前序遍历，也称为先序遍历，前序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。 ②中序遍历 中序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。 ③后序遍历 后序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。 二叉树的三种遍历是根据访问根节点的先后次序来命名的，前序遍历的访问顺序为根左右(BLR)，中序遍历的访问顺序为左根右(LBR)，后序遍历的访问顺序为左右根(LRB)