开云体育中国-火力全开！CBA比赛数据创纪录

开云阅读：9 2025-11-30 23:10:49 评论：0

公共基础

二级Office必考的考点

专业性很强

如果没有好的复习资料

是相当枯燥、晦涩、难懂的

你还为公共基础难懂

苦大愁深吗？

你还为不知如何拿下选择题

焦头烂额吗？

今天开始，小编带着大家

远离枯燥、远离专业术语

白话学懂公共基础！

　　程林高手武功秘籍--公共基础知识

　　1.7 倒置的树--树与二叉树

　　1.7.1 树的基本概念

　　数据结构中的树类似于把生活中的树倒置（树根朝上，叶子在最下面），如图16-10。我们在磁盘根目录下建立文件夹，在一个文件夹下再建立多个子文件夹，一个子文件夹下还可以再建立子文件夹，这就是一种"树"的结构。树是非线性结构，其所有元素之间具有明显的层次特性。像我们生活中对树的称呼一样，数据结构中树的结点也可分别被称为根结点、分支结点（非终端结点）、叶子结点（终端结点），要注意的是根在上、叶子在下。

　　除根结点和叶子结点外，每个结点的前驱（前件）只有一个，而后继（后件）有多个，这类似于一个文件夹的上一级文件夹只有一个，而在它下面可以建立多个子文件夹。树的根结点是唯一没有前驱（前件）的结点，叶子结点都没有后继（后件）。

　　也可以把树想象为一个家族的"家谱"，上面为祖先，下面为子孙，下一层就是下一代子孙。这样每个结点的唯一前驱（前件）结点也称这个结点的父结点，多个后继（后件）结点也称这个结点的子结点（孩子结点），父结点相同的各结点互称兄弟结点，如图16-10。

　　一个结点所拥有的子结点个数称该结点的度（分支度），也就是它的孩子数。所有结点中最大的度称树的度。树的最大层次称树的深度。图16-10中，结点C的度为2，A的度为3，D的度为0，E的度为0，树的度为3；树有3层，树的深度为3。

　　1.7.2 二叉树及其基本性质

　　二叉树是树的一种特殊情况，每个结点至多有两个分支（也可有一个分支或没有分支），如图16-11。那么二叉树中就只有3类结点：其分支度分别为0、1、2（其中分支度为1的结点包括向左分支的结点和向右分支的结点，都算作分支度为1的一类中）。根结点的左边部分称左子树，右边部分称右子树，左右子树不能互换。

　　二叉树的基本性质：

　　（1）在二叉树的第k层上，最多有2k-1 (k≥1)个结点；

　　（2）深度为m的二叉树最多有2m -1个结点；

　　（3）度为0的结点（叶子结点）总是比度为2的结点多一个；

　　性质3巧记

性质3也是最重要的性质，可以这样来记：

我们是四海八荒最大的二级Office公众号，关注我们公众号的小伙伴多数是大学生，还没孩子呢，人数那是相当的多！虽然国家放开生二胎了，恩，刚刚放开，有两孩子的还没那么多！

没孩子的总比两孩子的多一个

（度为0就是没孩子，度为2就是有两孩子）

记住这个性质，很多题都能破了！

　　【随讲随练16-17】一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）。

　　A.219 B.221 C.229 D.231

　　【答案】A

　　【分析】叶子结点为70个，故度为2的结点70-1=69个。总结点数69+80+70=219

　　【随讲随练16-18】设二叉树共有150个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为（）。

　　A.71 B.70 C.69 D.不可能有这样的二叉树

　　【答案】D

　　每一层上的所有结点数都达到最大的二叉树称满二叉树；除最后一层外，每一层上的结点数都达到最大，只允许最后一层上缺少右边的若干结点的二叉树称完全二叉树，如图16-12。显然，满二叉树也是完全二叉树，但完全二叉树不一定是满二叉树。在满二叉树中，不存在度为1的结点；在完全二叉树中，度为1的结点或者有0个或者有1个。

　　【例】已知一棵完全二叉树共有m个结点，求其叶子结点数：

　　设叶子结点数为x，则度为2的结点数为x-1；然后分两种情况计算：

　　（1）度为1的结点数为0时：x+x-1+0=m，解方程求x可得第1种结果。

　　（2）度为1的结点数为1时：x+x-1+1=m，解方程求x可得第2种结果。

　　上述两个方程的解中舍去不合理的结果（例如非整数的结果）即为所求。

　　【随讲随练16-19】一棵完全二叉树共有360个结点,则在该二叉树中度为1的结点个数为（）。

　　A.0 B.1 C.180 D.181

　　【答案】B

　　【随讲随练16-20】在深度为7的满二叉树中，度为2的结点个数为（）。

　　A.64 B.63 C.32 D.31

　　【答案】B

　　【分析】按照二叉树的“性质（2）深度为m的二叉树最多有2的m次方–1个结点”，深度为7至多有2的7次方–1=127个结点；满二叉树刚好是至多的结点，因此含127个结点。设度为2的结点有x个，则度为0的结点（叶子）有x+1个。而满足二叉树度为1的结点必有0个，得x+x+1+0=127，解得x=63。

　　1.7.3 二叉树的存储结构

　　二叉树也既可以顺序存储，又可以链式存储。顺序存储一般用于满二叉树或完全二叉树，按层序将各结点依次存储到一个数组的各元素中。在链式存储中，每个结点有两个指针域，一个指向左子结点，一个指向右子结点，如图16-13是图16-12右图二叉树的链式存储结构。二叉树的链式存储结构也称二叉树链表（二叉链表）。注意二叉链表是采用链式存储方式的二叉树，它的本质是树，因此是非线性结构。

　　【随讲随练16-21】下列链表中，其逻辑结构属于非线性结构的是（）。

　　A.二叉链表 B.循环链表 C.双向链表 D.带链的栈

　　【答案】A

　　【随讲随练16-22】能从任意一个结点开始没有重复地扫描到所有结点的数据结构是（）。

　　A.循环链表 B.双向链表 C.二叉链表 D.有序链表

火力全开！CBA比赛数据创纪录

　　【答案】A

　　1.7.4 二叉树的遍历

　　二叉树的遍历，就是对二叉树中的各个结点进行访问，使每个结点仅被访问一次。如图16-11的二叉树，可按层次从上到下依次访问ABCDEFGHI，这就是一种遍历；当然也可以从下到上依次访问IHGFEDCBA，这又是一种遍历。显然遍历方式不同，遍历序列就不同。按层次遍历是最简单的遍历方式，此外二叉树还有许多其他的遍历方式，比较重要的有以下3种：

　　（1）前序遍历（DLR）：首先访问根结点，然后遍历左子树，最后遍历右子树；

　　（2）中序遍历（LDR）：首先遍历左子树，然后访问根结点，最后遍历右子树；

　　（3）后序遍历（LRD）：首先遍历左子树，然后遍历右子树，最后访问根结点。

　　上述遍历名称中的"前"、"中"、"后"实际代表的是遍历时"根结点"在前、中、后：前序是先访问根，中序是中间访问根，后序是最后访问根。而左、右均是依"从左到右"的顺序。如图16-14的二叉树，其前序遍历序列是ABC（根、左、右），中序遍历序列是BAC（左、根、右），后序遍历序列是BCA（左、右、根）。

　　那么对于图16-11的二叉树，左、右不是一个结点，该如何遍历呢？在遍历到其左、右时，需将左、右单独提出，将提出后的部分单独考虑则又是一棵二叉树，即左子树、右子树。单独考虑子树的二叉树，将子树的二叉树按同样方式遍历。如果子树的左、右还不是一个结点，再将子树的左、右子子树单独提出遍历……直到左、右都仅剩一个结点为止。例如对图16-11的二叉树求前序遍历序列，分析过程可表示为图16-15。每层都是按照"根、左、右"的顺序写出子树的遍历序列，然后再将子树的遍历序列代回上一层。最终得前序遍历序列为：ABDGCEHIF。

　　（如此详细的分析，如此细致的图，只有玩转这样的书才有。比起那些连一张图也没有的速背手册如何？哪个易于理解呢？）

　　类似地，可得图16-11的二叉树的中序遍历序列为DGBAHEICF，后序遍历序列为GDBHIEFCA。在中序（后序）遍历时，提出子树和代回子树结果到上一层的方式与求前序遍历序列的都相同，只不过任何一个层次的子树都要按照中序（后序）的方式遍历：即左、根、右（左、右、根）的顺序。总之二叉树遍历的关键是按照"子树"的思想，将问题逐一缩小，而每一个小问题又都是同样的"遍历"问题。

　　【例】已知一棵二叉树前序遍历序列为ABDGCFK，中序遍历序列为DGBAFCK，则它的后序遍历序列是？

　　【答案】GDBFKCA

　　【分析】应先画出此二叉树，然后再求其后序遍历序列。

火力全开！CBA比赛数据创纪录