第13章 树（含逆波兰表达式）知识点梳理—2024届高考信息技术二轮复习知识点梳理

第十三章 树 1.树是一种非线性的数据结构用它能很好的描述有分支和层次特性的数据集合 2.树可以描述为由n(n>=0)个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 3.集合中的元素称为树的节点，n=0的树称为空树；树中某个节点下面的所有节点所构成的树称为该节点的子树。 4.树的两个节点之间如果有一条边连接，那么称为这两个节点之间存在一条边；对于一颗具有n个节点的树，它由n-1条边。 5.如下图：下图中的树中共有13个节点、12条边、节点B、G、H构成节点A的一颗子树 图1.1 6.树的一个节点所拥有的子树个数称为该节点的度，最大的节点的度称为树的度。如图4.1，节点A的度为5，节点B的度为2，节点I的度为3，因此此树的度为5。 7.在树形结构中，没有前驱的节点称为根节点，又称为开始节点（图1.1的A节点）。 8.度为0的节点称为叶子节点，又称为终端节点（图1.1的G、H、C、D、K、L、M、J、F） 9.树中度不为0的节点称为分支节点或非终端节点，除根节点外的分支节点统称为内部节点（图1.1的B、E、I节点） 10.在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的父节点或双亲节点。相应的下端节点称为上端节点的孩子节点。如图4.1所示，节点K、L、M都是节点I的孩子节点。反过来，节点I是节点K、L、M的父节点，节点K、L、M是兄弟节点 11.树中节点的层数从根开始计算，根的层数为1，其余节点的层数等于其父节点的层数加1 12.树中节点的最大层数称为树的高度或深度 13.二叉树是一个具有n(n>=0)个节点的有限集合；当n=0时，二叉树是一颗空树；当n!=0是，则是一颗由根节点和两颗互不相交的分别称为这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。 14 二叉树的分类如下图：从左到右分别是为1.空二叉树、2.只有根节点的单点树、3.只有根节点和左子树、4.只有根节点和右节点、5.有根节点和左右子树 图1.2 14.完全二叉树:这一类二叉树至多只有最下面两层中的节点度数小于2，且最下面一层的叶子节点都依次排列在该层的最左边位置。如下图： 图1.3 15.二叉树的性质如下： （1）二叉树的第k层上最多有2k–1（k≥1）个节点。 （2）深度为k的二叉树最多有2k –1（k≥1）个节点。 （3）在任意一棵二叉树中，若度为2的节点数量为n2，叶子节点（度为0的节点）数为 n0，则n0=n2+1。 16.二叉树的遍历：二叉树的遍历根据根节点的访问顺序，可以分为 前序遍历、中序遍历、后序遍历。 17.前序遍历规则：先访问根节点，再访问左子树，最后访问右子树。如下图1.4： 最后访问顺序为：A-B-D-H-E-C-F-I-G-J-K 18.中序遍历规则：先访问左子树，再访问根节点，最后访问右子树。如下图1.5： 最后访问顺序为：D-H-B-E-A-I-F-C-J-G-K 19.后序遍历规则：先访问左子树，再访问右子树，最后访问根节点。如下图1.6： 最后访问顺序为：H-D-E-B-I-F-J-K-G-C-A 图1.4 图1.5 图1.6 逆波兰表达式： 逆波兰式是一种将待计算量写在前, 把运算符写在后（通常是两数之后）的计算式，比如： 中序表达式 逆波兰表达式 A + B A B + A * B A B * A +B * C A B C * + A * ( B + C ) A B C + * 表1.1 逆波兰表达式可以通过栈、叉树等数据结构存储，其中二叉树用的较多，通过二叉树存储 通过前序、中序、后序遍历中的其中一种方法，可以遍历出一个表达式。 例如：有如下二叉树存储的逆波兰表达式 a+(b-c) 图1.7 当前二叉树的中序遍历为a+(b-c),【注意：b-c外的括弧，是因为他们与a不在同一子树所以增加】 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$