高中信息技术选择性必修1：树结构知识清单（粤教版）

高中信息技术选择性必修1：树结构知识清单（粤教版）一、树结构的基本概念与术语（基础▲）（一）树的定义与逻辑结构...（n≥0）个结点的有限集合T。当n=0时，称为空树，这是一种特殊情况。【基础】在任意一棵非空树中，应满足以下两个核心条件：第一，有且仅有一个特定的称为根（Root）的结点，它没有前驱；第二，当n>1时，其余结点可分为m（m>0）个互不相交的有限集合T1,T2,...,Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）1。树的结构定义采用了递归描述方法，即一棵树由根和若干棵子树构成，而子树本身也是一棵树。从逻辑结构上看，树是一种非线性结构，它表示的是数据元素之间一对多的关系，除根结点外，每个结点有且只有一个直接前驱，但可以有零个或多个直接后继1。（二）树的基本术语详解【重要】为了精准描述树形结构，必须掌握以下核心术语：1.结点的度（Degree）：指结点拥有的子树数，即该结点直接后继的个数1。2.树的度：指树内所有结点度的最大值。若树的度为m，则称该树为m叉树。3.叶子结点（Leaf）与分支结点（BranchNode）：度为0的结点称为叶子结点，也称终端结点；度大于0的结点称为分支结点，也称非终端结点或内部结点1。4.孩子结点（Child）与双亲结点（Parent）：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。这是一种一对多的层次关系1。5.兄弟结点（Sibling）：具有同一双亲的结点互称为兄弟1。6.结点的层次（Level）：从根开始定义，根为第1层，根的孩子为第2层，以此类推。若某结点在第i层，则其子树的根就在第i+1层。7.树的深度（Depth）或高度：树中结点的最大层次数，称为树的深度或高度1。空树的深度为0，只有根结点的树深度为1。8.有序树与无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。二叉树是一种特殊且重要的有序树。（三）树的基本性质根据树的定义，可以推导出以下基本性质：【高频考点】1.结点数与边数的关系：在一棵有n个结点的树中，一定有且仅有n1条边（即分支）。这是因为除根结点外，每个结点有且仅有一条边与其双亲相连4。2.度数方程：在一棵树中，所有结点的度数之和等于总分支数，也等于结点总数减1。即：总度数=n1。这一性质常用于求解树中各种度数结点的数量问题。二、二叉树（BinaryTree）的精讲（核心与重点★★★★★）二叉树是树形结构中最重要的形式，也是后续学习的基础。它不仅是考试的重中之重，更是解决实际问题的关键数据结构。（一）二叉树的定义与特征【基础】二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成6。这一定义同样是递归的。二叉树的特征在于：每个结点最多有两棵子树，即不存在度大于2的结点；并且二叉树是有序树，左右子树不能颠倒，即使只有一棵子树，也必须区分是左子树还是右子树6。（二）特殊的二叉树【高频考点】1.满二叉树（FullBinaryTree）：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，则称为满二叉树。换句话说，深度为k的满二叉树，其结点总数为2^k1，每一层上的结点数都是最大数目2。2.完全二叉树（pleteBinaryTree）：深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树【难点】2。完全二叉树的特点是：叶子结点只可能出现在最下面两层；最下层的叶子一定集中在左部连续位置；倒数第二层若有叶子结点，一定都在右部连续位置；如果结点度为1，则该结点只有左孩子，不存在只有右孩子的情况；同样结点数的二叉树，完全二叉树的深度最小6。（三）二叉树的核心性质（必须掌握）【重要】性质1：在二叉树的第i层上至多有2^(i1)个结点（i≥1）2。性质2：深度为k的二叉树至多有2^k1个结点（k≥1）2。性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1【高频考点】2。证明思路：设结点总数为n，分支总数为B，则n=n0+n1+n2，且B=n1。同时，从结点度数的角度看，分支数也等于n1+2n2。联立可得n0=n2+1。性质4：具有n个结点的完全二叉树的深度k为floor(log2n)+1【高频考点】2。其中floor(x)表示不大于x的最大整数。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第floor(log2n)+1层，每层从左到右），则对任一结点i（1≤i≤n），有：【重要】（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点floor(i/2)。（2）如果2i>n，则结点i无左孩子（即结点i为叶子结点）；否则其左孩子是结点2i。（3）如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+12。（四）二叉树的存储结构【重要】1.顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。【适用场景】这种存储方式仅适用于完全二叉树或满二叉树。对于一般的二叉树，如果采用顺序存储，需要将不存在的结点位置空出来，会造成大量的空间浪费6。在顺序存储中，根据性质5，我们可以通过数组下标快速找到任意结点的父结点和左右孩子。2.链式存储结构：由于顺序存储的局限性，通常采用链式存储结构来表示二叉树。二叉树的链式存储结点至少包含三个域：数据域（data）和两个指针域（left和right），分别指向左孩子和右孩子。这种存储结构称为二叉链表【基础】8。对于一棵有n个结点的二叉树，其二叉链表存储结构中总共有2n个指针域，其中n1个指针域指向实际结点，另外n+1个指针域为空（即^）7。这n+1个空指针是后续线索化二叉树的基础。三、二叉树的遍历算法（难点、高频考点、核心技能★★★★★）遍历二叉树是指按照某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。遍历是将非线性结构线性化的过程4。（一）深度优先遍历（DFS，DepthFirstSearch）根据访问根结点顺序的不同，深度优先遍历分为三种：前序遍历、中序遍历和后序遍历。三种遍历算法无论是递归还是非递归实现，其时间复杂度都是O(n)，空间复杂度取决于树的高度，最坏情况下为O(n)8。1.前序遍历（PreorderTraversal）（根左右）【高频考点】1.2.遍历规则：若二叉树为空，则空操作；否则：（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树2。2.3.递归算法思想：直接按照定义的顺序进行递归调用。3.4.非递归算法（栈实现）：【难点】先将根结点入栈。当栈非空时，弹出栈顶结点p并访问之。接着，如果p有右孩子，则将右孩子入栈；然后如果p有左孩子，则将左孩子入栈。注意入栈顺序是先右后左，这样才能保证出栈时是先左后右8。4.5.遍历结果特点：前序遍历序列的第一个结点一定是整棵树的根结点。6.中序遍历（InorderTraversal）（左根右）【高频考点】1.7.遍历规则：若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树2。2.8.递归算法思想：递归调用遍历左子树，然后访问根，再递归调用遍历右子树。3.9.非递归算法（栈实现）：【难点】从根结点开始，将当前结点p及其所有左孩子入栈，即p=p>left一直向左走，直到p为空。此时栈顶元素是树中最左边的结点，弹出并访问之。然后将p指向弹出结点的右孩子，重复上述过程，直到栈为空且p为空8。4.10.遍历结果特点：对于二叉排序树（BST），中序遍历的结果是一个递增的有序序列。11.后序遍历（PostorderTraversal）（左右根）【高频考点】1.12.遍历规则：若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点2。2.13.递归算法思想：先递归左右子树，最后访问根。3.14.非递归算法（双栈法或标记法）：【难点】后序遍历的非递归实现最复杂。一个巧妙的方法是使用两个栈：将根结点压入栈1。从栈1弹出结点p并压入栈2。然后，将p的左孩子和右孩子依次压入栈1。循环结束后，从栈2依次弹出的顺序即为后序遍历序列10。这是因为栈1的压入顺序是根、左、右，弹出到栈2的顺序是根、右、左，所以栈2的出栈顺序就是左、右、根。4.15.遍历结果特点：后序遍历序列的最后一个结点一定是整棵树的根结点。（二）广度优先遍历（BFS，BreadthFirstSearch）——层序遍历【重要】1.遍历规则：从上到下、从左到右，逐层访问树的结点8。2.算法实现（队列实现）：【重要】初始化一个队列，将根结点入队。当队列不为空时，循环执行：取出队首结点p并访问之；如果p有左孩子，将左孩子入队；如果p有右孩子，将右孩子入队810。这种算法利用队列的先进先出特性，保证了结点按层次顺序被访问。3.变式应用：基于层序遍历，可以衍生出许多高级算法，如之字形遍历（ZigzagTraversal），即奇数层从左到右，偶数层从右到左8。四、树、森林与二叉树的转换（拓展与思维）（一）树的存储结构在实际应用中，树（如m叉树）常通过转换为二叉树的形式进行存储和操作。树的存储方法主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法7。其中，孩子兄弟表示法是实现树与二叉树转换的关键。（二）树转换为二叉树【方法】将一棵树转换为二叉树的步骤如下（也称为左孩子右兄弟法）：1.在兄弟结点之间加一连线。2.对每个结点，只保留它与第一个孩子（左孩子）的连线，而抹去它与其它孩子之间的连线。3.以根结点为轴心，将树顺时针旋转一定角度，使之层次分明。转换后的二叉树，其根结点的右子树必为空，因为树根没有兄弟。（三）森林转换为二叉树【方法】1.将森林中的每一棵树分别转换为二叉树。2.将每棵树的根结点视为兄弟，从第二棵二叉树开始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子连接起来。（四）二叉树转换为树或森林【方法】...转换为树或森林是上述过程的逆过程。若二叉树中某结点x是其双亲y的左孩子，则把x的右孩子、右孩子的右孩子...，都与y用连线相连，最后删去所有原二叉树中的右孩子连线。五、考点剖析与解题策略（应考指南★★★★★）（一）常见题型与考查方式1.基础概念题：直接考查树的定义、术语、二叉树的性质（如叶子结点数与度为2结点数的关系）【基础】。2.性质计算题：给定结点数，求树的高度、叶子结点数、完全二叉树的结点编号关系等【高频考点】。3.遍历序列推导题：已知两种遍历序列（必含中序），求第三种遍历序列或还原二叉树【重中之重】。4.存储结构题：给定一个二叉树，写出其顺序存储的数组表示，或根据数组画出二叉树。5.算法设计题：设计递归或非递归算法实现二叉树的遍历、求深度、求叶子结点数等操作【难点】。6.应用题：利用树形结构解决实际问题，如表达式树、哈夫曼树（后续章节）等。（二）解题步骤与易错点分析【重要】1.已知先序和中序，还原二叉树（经典考法）1.2.解题步骤：（1）在先序序列中，第一个结点即为根结点。（2）在中序序列中找到根结点，根结点左侧为左子树的中序序列，右侧为右子树的中序序列。（3）根据左、右子树中序序列的长度，在先序序列中划分出左子树的先序序列和右子树的先序序列。（4）递归地对左子树和右子树重复上述步骤，直到所有子树都确定下来2。2.3.易错点：在划分先序序列时，必须严格按照中序序列的长度进行划分，不能出错。4.已知后序和中序，还原二叉树1.5.解题步骤：（1）在后序序列中，最后一个结点即为根结点。（2）在中序序列中找到根结点，划分出左右子树的中序序列。（3）根据左右子树的中序序列长度，在后序序列中划分出左右子树的后序序列（左子树的后序在前，右子树的后序在中，根在最后）。（4）递归进行。6.已知先序和后序，能否唯一确定二叉树？1.7.结论：不能。【难点】因为当一棵二叉树中所有非叶子结点都只有左孩子或都只有右孩子（即单支树）时，先序和后序序列不能区分左右。例如，先序为AB，后序为BA的二叉树，既可以是A为根B为左孩子，也可以是A为根B为右孩子4。因此，只有同时包含中序的两种遍历序列才能唯一确定一棵二叉树。（三）典型例题剖析例题1：某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，请给出后序遍历结果。【高频考点】解析：（1）由前序知，根结点为A。（2）由中序知，A左边的CB为左子树的中序，A右边的EDF为右子树的中序。因此左子树有2个结点，右子树有3个结点。（3）左子树的前序为BC（前序中紧跟A的2个结点），中序为CB。由前序BC知左子树的根为B，由中序CB知C在B左边，因此C是B的左孩子，B无右孩子。（4）右子树的前序为DEF（前序中剩下的3个结点），中序为EDF。由前序DEF知右子树的根为D。由中序EDF知，E在D左边，F在D右边，因此E是D的左孩子，F是D的右孩子。（5）画出二叉树后，后序遍历结果为：CBEFDA。例题2：一棵完全二叉树有700个结点，则叶子结点数为多少？【高频考点】解析：根据二叉树性质3（n0=n2+1）和完全二叉树的性质（n1为0或1），设总结点数n=n0+n1+n2。代入n0=n2+1，得n=2n2+n1+1。（1）若n1=0，则n=2n2+1，即n为奇数。700是偶数，不成立。（2）若n1=1，则n=2n2+2，即n为偶数。700=2n2+2，解得n2=349。因此，叶子结点数n0=n2+1=350。或者利用完全二叉树的性质：叶子结点数=floor(n/2)（当n为偶