第四章 树（知识清单）信息技术浙教版2019选择性必修1

第四章 树 （知识清单） 【知识结构】 【考点清单】 1.树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 2.集合中的元素称为树的节点，n=0的树称为空树；树中某个节点下面的所有节点所构成的树称为该节点的子树。 3.树的两个节点之间如果有一条边连接，那么称这两个节点之间存在一条边；对于一棵具有n个节点的树，它有n–1条边。 4.树的一个节点所拥有的子树个数称为该节点的度（Degree），最大的节点的度称为树的度。 5.在树形结构中，没有前驱的节点称为根节点（Root），又称为开始节点。度为0的节点称为叶子节点（Leaf），它又称为终端节点。树中度不为0的节点称为分支节点或者称为非终端节点，除根节点外的分支节点统称为内部节点。 6.树中节点的层数（Level）从根开始计算，根的层数为1，其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的高度或深度（Depth）。 7.二叉树（Binary Tree）是一个具有n（n≥0）个节点的有限集合。当n=0时，二叉树是一棵空树；当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。 8.一棵二叉树有5种可能的形态，从左到右分别是：①空二叉树；②只有根节点的单点树；③只有根节点和左子树；④只有根节点和右子树；⑤左右子树均非空。 9.二叉树的性质： ①二叉树的第k层上最多有2k–1（k≥1）个节点。 ②深度为k的二叉树最多有2k –1（k≥1）个节点。 ③在任意一棵二叉树中，若度为2的节点数量为n2，叶子节点（度为0的节点）数为n0，则n0=n2+1。 10.完全二叉树：从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 11.对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。 12.对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。 13.二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节 点的指针来表示节点之间的关系。 14.二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。 15.二叉树的遍历方式有很多，主要有前序遍历、中序遍历和后序遍历等。 16.抽象数据类型（Abstract Data Type，简称ADT）是指一个数学模型及定义在该模型上的一组操作。 17.述抽象数据类型的标准格式： ADT 抽象数据类型名： Data 数据元素之间逻辑关系的定义 Operation 操作1 初始条件 操作结果描述 操作2 …… 操作n …… endADT 18.抽象数据类型主要体现了程序设计中问题分解、抽象和信息隐藏的特征。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$