大数据分析应用-初级
第一部分 基础知识
一、大数据法律法规、政策文件、相关标准
二、计算机基础知识
三、信息化基础知识
四、密码学
五、大数据安全
六、数据库系统
七、数据仓库.
第二部分 专业知识
一、大数据技术与应用
二、大数据分析模型
三、数据科学
数据结构与算法
- 大数据分析应用-初级
- 前言
- 一、树的描述方法与应用
- 练习题目
前言
数据结构与算法
4、掌握树的描述方法与应用。
一、树的描述方法与应用
树的基本概念
1、树的定义：树是一种非线性的数据结构，它是由 n（n≥0）个节点组成的有限集合。
当 n = 0 时，称为空树；
当 n＞0 时，有且仅有一个特定的称为根的节点，其余节点可分为 m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树，并且称为根的子树。
2、基本术语：
- 节点（Node）：树中的元素称为节点。每个节点可以包含数据以及指向其他节点的指针（引用）。例如，在一个存储员工信息的树结构中，每个员工的信息可以存储在一个节点中。
- 边（Edge）：连接节点的线称为边。它表示节点之间的关系，通常体现为父子关系。比如在二叉树中，一个父节点通过边与它的两个子节点相连。
- 根节点（Root）：树中没有父节点的节点是根节点。它是树的起始点，所有其他节点都是根节点的后代。以公司组织架构树为例，公司的 CEO 所在的节点可以看作是根节点。
- 叶子节点（Leaf）：没有子节点的节点称为叶子节点。在文件系统树中，文件对应的节点通常是叶子节点，因为它们没有下属的子文件或文件夹。
- 子节点和父节点：如果存在一条边从节点 A 连接到节点 B，那么 B 是 A 的子节点，A 是 B 的父节点。例如在家族族谱树中，子女节点是父母节点的子节点。
- 深度（Depth）和高度（Height）：节点的深度是从根节点到该节点的边的数量。树的高度是树中所有节点深度的最大值。例如，一棵简单的三层二叉树，根节点深度为 0，叶子节点深度为 2，树的高度为 2。
- 层次（Level）：根节点在第 0 层，根节点的子节点在第 1 层，以此类推。
3、树的性质：例如树中的节点数等于所有节点的度数加 1（节点的度数指该节点拥有的子节点个数）；度为 k 的树中第 i 层上最多有 k^(i - 1) 个节点等，这些性质有助于深入理解树的内在规律和特点。
二、树的存储结构
1、双亲表示法：采用一组连续的存储空间（如数组）来存储树中的节点，同时在每个节点结构里设置一个指针域（或存储位置信息）用于指示该节点的双亲节点所在位置。其优势在于查找节点的双亲方便，但查找子节点相对麻烦，需遍历整个存储结构查找具有特定双亲标记的节点。
2、孩子表示法：针对每个节点，运用链表来存储其所有的子节点。常见做法是用一个数组存放每个节点以及指向其孩子链表的头指针，便于查找节点的子节点，不过查找双亲节点就需要额外设计或者遍历查找了。
3、孩子兄弟表示法：利用二叉链表来表示树结构，让节点的第一个指针指向其第一个孩子节点，第二个指针指向其右兄弟节点。通过这种方式可将树结构转换为二叉树结构，进而能借助二叉树相关操作算法来处理树的问题。
二叉树
二叉树概念
- 1、二叉树的定义：二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点，并且二叉树的子树有左右之分，次序不能随意颠倒。
- 2、几个特殊的二叉树
- （1）斜树：所有节点都只有左子树或者只有右子树的二叉树，其结构类似一条斜线，在实际应用中效率较低，但可作为一种极端的二叉树形态用于理论对比等情况。
- （2）满二叉树：深度为 k 且有 2^(k + 1) - 1 个节点的二叉树，特点是每一层的节点数都达到了该层所能容纳的最大节点数，结构非常规整，常用于研究二叉树的性质和算法分析基础模型等。
- （3）完全二叉树：设二叉树深度为 k，除第 k 层外，其他各层 (1~k - 1) 的节点数都达到最大个数，第 k 层所有节点都连续集中在最左边，这种二叉树在数组存储时能很好地利用下标来计算父子节点位置，在很多高效存储和算法应用场景中被广泛使用。
- （4）二叉排序树：又称为二叉查找树，它是一种有序的二叉树，对于树中任意一个节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值，常用于数据的快速查找、插入和删除操作等场景。
- （5）平衡二叉树：左右子树的高度差保持在一个较小的规定范围内（如 AVL 树要求左右子树高度差绝对值不超过 1）的二叉树，通过特定的调整机制（如旋转操作）在节点插入或删除时维持平衡，保障了查找等操作在最坏情况下也能有较好的时间复杂度，一般为 O (log n)。
- 3、二叉树的性质：例如二叉树的第 i 层上最多有 2^(i - 1) 个节点；深度为 k 的二叉树最多有 2^k - 1 个节点等，这些性质是对二叉树结构特点的量化描述，便于进行相关算法分析和实现。
- 4、二叉树的存储结构
- （1）顺序存储结构：将二叉树的节点按照一定顺序存放在数组中，一般根节点存放在下标为 1 的位置（也有从 0 开始的情况），然后根据节点间父子关系的规律（如对于下标为 i 的节点，其左子节点下标为 2i，右子节点下标为 2i + 1 等情况）来定位其他节点，适合完全二叉树等规则结构的存储，对于非完全二叉树可能会造成空间浪费。
- （2）链式存储结构：通过节点结构体中设置指针域来分别指向左子节点和右子节点，以链式的方式连接各个节点，这种存储结构能灵活地表示各种形态的二叉树，不受节点数量和分布的严格限制，但访问某个节点时需要顺着指针链逐个查找，可能相对顺序存储在某些情况下效率稍低一点。
遍历二叉树
- 1、先序遍历：遵循先访问根节点，接着访问左子树，最后访问右子树的顺序。递归实现比较直观，例如对于二叉树 T，根节点为 r，左子树为 L，右子树为 R，其先序遍历顺序就是 r - L - R，常用于复制二叉树、输出二叉树的表达式前缀形式等应用场景。
- 2、中序遍历：按照先访问左子树，然后访问根节点，最后访问右子树的顺序进行。即对于二叉树 T 顺序为 L - r - R，对于表达式树可输出表达式的中缀表示形式（可能需加括号体现运算优先级），在很多基于二叉树结构的求值、排序等算法中有重要应用。
- 3、后序遍历：先访问左子树，再访问右子树，最后访问根节点，顺序为 L - R - r。在二叉树删除、计算后缀表达式等场景中较为常用，例如利用后序遍历可以方便地释放二叉树占用的内存空间等。
- 4、递归算法和非递归算法的转换
- （1）中序遍历的非递归算法：通常借助栈来实现，模拟递归过程中系统栈的操作，通过不断压入和弹出节点来完成中序遍历，避免了递归可能带来的栈溢出等问题，在处理大数据量二叉树时更具优势。
- （2）先序遍历的非递归算法：同样利用栈，按照先序遍历的规则将节点压入和弹出栈，实现与递归先序遍历相同的遍历效果，且在一些特定的程序环境下（如对栈空间有限制要求等）能更好地控制资源使用。
- （3）后序遍历的非递归算法：相对复杂一些，需要额外标记节点的访问状态等，通过巧妙地利用栈结构来实现后序遍历，保证节点按照正确的后序顺序被访问，常用于需要非递归方式处理二叉树后序遍历的算法实现中。
- 5、层次遍历：按照树的层次，从根节点开始，一层一层地从左到右访问节点，常借助队列来实现。例如在进行广度优先搜索（BFS）应用于二叉树时，采用这种遍历方式，对于求树的高度、统计每层节点数量等与层次相关的问题处理很有效。
- 6、由遍历序列构造二叉树：一般来说，仅通过一种遍历序列（如先序、中序或后序）无法唯一确定一棵二叉树，但如果知道中序遍历序列以及另外一种遍历序列（先序或后序），则通常可以唯一确定一棵二叉树，通过分析不同遍历序列中节点出现的顺序规律来逐步构建二叉树的结构。
线索二叉树
- 1、线索二叉树原理：利用二叉树中那些原本为空的指针（指向 NULL 的左指针或右指针），将其指向树中其他有意义的节点，比如让空的左指针指向该节点在某种遍历顺序下的前驱节点，空的右指针指向后继节点，以此来加快遍历速度以及方便获取节点的遍历顺序相关信息。
- 2、线索二叉树的结构实现：在二叉树节点结构体的设计上，除了常规的指向左子节点和右子节点的指针域外，还会添加标志位来区分该指针是正常的指向子节点的指针还是线索指针，便于在遍历和操作过程中准确判断和使用。
- 3、二叉树的线索化
- （1）中序线索二叉树：按照中序遍历的顺序对二叉树进行线索化，使得在中序遍历过程中可以更便捷地找到节点的前驱和后继节点，对于需要频繁查询中序遍历相关前驱、后继的应用场景很有帮助。
- （2）先序和后序线索二叉树：类似中序线索二叉树的做法，分别按照先序和后序遍历的顺序对二叉树进行线索化，各自适用于对应遍历顺序下需要快速获取节点前后关联节点的情况，不过实现和使用相对中序线索二叉树会复杂一些。
树、森林与二叉树的转化
- 1、树转换为二叉树：运用孩子兄弟表示法的思路，将树的每个节点的第一个孩子作为二叉树节点的左子节点，其兄弟节点作为右子节点，依次转换，这样就可以把一棵树转换为二叉树结构，便于利用二叉树已有的算法和存储方式来处理原本树结构的数据和操作。
- 2、森林转化为二叉树：先把森林中的每棵树都转换为二叉树，然后以第一棵二叉树的根节点作为最终二叉树的根节点，将后面的二叉树依次作为前一棵二叉树根节点的右子树，从而将整个森林转化为一棵二叉树，拓展了森林结构数据处理的途径和方式。
树和森林的遍历
- 1、树的遍历：主要有先根遍历（类似二叉树的先序遍历，先访问根节点，再依次遍历子树）和后根遍历（先遍历子树，最后访问根节点）两种常见方式，不同的遍历方式在处理树结构数据时能获取不同顺序的节点信息，可应用于树结构数据的分析、统计等场景。
- 2、森林的遍历：可以分为先序遍历森林（先访问森林中第一棵树的根节点，再先序遍历第一棵树的子树，接着按先序遍历其余树）和中序遍历森林（对森林中的每棵树分别进行中序遍历）等方式，通过合适的遍历方式来提取森林结构中蕴含的信息以及进行相关处理操作。
树与二叉树的应用
二叉排序树
- 1、定义：前面已提及，它是一种有序二叉树，满足左子树节点值小于根节点值，右子树节点值大于根节点值的特性，基于此有序结构可方便地进行数据查找、插入和删除等操作。
- 2、二叉排序树的常见操作
- （1）查找操作：从根节点开始，比较要查找的值与当前节点的值，小于则往左子树找，大于则往右子树找，若找到相等的值则查找成功，若遍历到叶子节点还未找到则查找失败，平均时间复杂度一般为 O (log n)，但最坏情况下可能退化为 O (n)。
- （2）插入操作：同样从根节点开始比较，根据值的大小关系找到合适的位置（叶子节点位置），然后插入新节点，保证插入后二叉排序树的有序性依然成立。
- （3）删除操作：较为复杂，需要分情况讨论，比如要删除的节点是叶子节点、只有一个子节点或者有两个子节点等不同情况，要通过合适的调整来维持二叉排序树的结构和排序特性。
- 3、小结（引申出平衡二叉树）：由于二叉排序树在最坏情况下性能不佳（如插入顺序为有序时会退化为斜树），所以引出了平衡二叉树，通过自动平衡机制来保证树的高度相对稳定，进而保障操作的高效性。
平衡二叉树
- 1、定义：左右子树高度差保持在规定范围内（常见如 AVL 树的高度差绝对值不超过 1）的二叉树，通过旋转等调整手段来维持平衡。
- 2、平衡二叉树的查找：其查找操作与二叉排序树类似，但由于其平衡特性，保证了查找的时间复杂度在最坏情况下也能维持在 O (log n)，比普通二叉排序树在最坏情况时有更好的性能表现。
- 3、平衡二叉树的插入：在插入新节点后，会检查树的平衡情况，若出现不平衡则及时进行相应的旋转操作（如左旋、右旋、先左旋后右旋、先右旋后左旋等）来恢复平衡，确保树始终保持平衡二叉树的特性。
哈夫曼树和哈夫曼编码
- 1、哈夫曼树的定义和原理：哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩等领域。其原理是对于给定的一组带有权值的节点，通过特定的构造算法构建二叉树，使得带权路径长度（节点的权值乘以该节点到根节点的路径长度之和）最小，达到优化数据表示和传输等目的。
- 2、哈夫曼树的构造：一般从给定的权值节点集合开始，先选取权值最小的两个节点构建一棵新的二叉树（作为左右子节点，新节点的权值为这两个节点权值之和），然后将新二叉树作为一个新的节点放回集合中，不断重复这个过程，直到构建出一棵完整的哈夫曼树。
- 3、哈夫曼编码：基于哈夫曼树来为字符等元素进行编码，从根节点到叶子节点的路径，规定向左分支编码为 0，向右分支编码为 1（或反之），这样每个叶子节点对应的编码就是哈夫曼编码，具有无前缀性（即任何一个编码都不是其他编码的前缀），能有效减少数据编码后的长度，实现数据压缩效果，常用于文本压缩、通信编码等场景。
练习题目
一、单选题
1. 树的根节点（ ）
A. 有且只有一个
B. 可以有多个
C. 最多两个
D. 数量不定
答案：A
解析：根据树的定义，树是由 n（n≥0）个节点组成的有限集合。当 n＞0 时，有且仅有一个特定的称为根的节点，所以树的根节点有且只有一个。
2. 在二叉树的顺序存储结构中，对于下标为 i 的节点，其左子节点的下标通常为（ ）（假设根节点下标从 1 开始）
A. 2i
B. 2i + 1
C. i + 1
D. i - 1
答案：A
解析：在二叉树的顺序存储结构中，若根节点下标从 1 开始，那么对于下标为 i 的节点，其左子节点下标为 2i，右子节点下标为 2i + 1。这是由二叉树顺序存储的规律决定的，这样的存储方式便于利用数组下标来访问节点之间的父子关系。
3. 以下哪种遍历方式可以得到二叉树节点的后缀表达式（ ）
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
答案：C
解析：后序遍历的顺序是先访问左子树，再访问右子树，最后访问根节点。对于表达式树，后序遍历可以得到表达式的后缀表示形式。后缀表达式在计算表达式的值时非常方便，因为它不需要考虑运算符的优先级，按照顺序依次处理操作数和运算符即可。
4. 满二叉树一定是（ ）
A. 完全二叉树
B. 平衡二叉树
C. 二叉排序树
D. 线索二叉树
答案：A
解析：满二叉树是深度为 k 且有 2^(k + 1) - 1 个节点的二叉树，其每一层的节点数都达到最大值。完全二叉树是除第 k 层外，其它各层 (1~k - 1) 的节点数都达到最大个数，第 k 层所有的节点都连续集中在最左边。满二叉树满足完全二叉树的定义，所以满二叉树一定是完全二叉树。但满二叉树不一定是平衡二叉树（平衡二叉树主要是左右子树高度差有要求）、二叉排序树（有节点值大小顺序要求）和线索二叉树（需要额外线索化处理）。
5. 哈夫曼树是一种（ ）
A. 满二叉树
B. 完全二叉树
C. 带权路径长度最短的树
D. 平衡二叉树
答案：C
解析：哈夫曼树是一种带权路径长度最短的二叉树。它是通过将权值小的节点放在离根节点较远的位置，权值大的节点放在离根节点较近的位置构建出来的。它既不是满二叉树，也不一定是完全二叉树和平衡二叉树。
二、多选题
1. 以下属于树的存储结构的有（ ）
A. 双亲表示法
B. 孩子表示法
C. 孩子兄弟表示法
D. 顺序存储结构
答案：ABC
解析：双亲表示法是采用一组连续的存储空间来存储树中的节点，同时在每个节点结构中设置一个指针域用于指示该节点的双亲节点在数组中的位置；孩子表示法是针对每个节点，用链表来存储其所有的子节点；孩子兄弟表示法是用二叉链表来表示树结构，让节点的第一个指针指向其第一个孩子节点，第二个指针指向其右兄弟节点。而顺序存储结构一般是用于存储线性结构或者特殊的树结构（如完全二叉树），单独说顺序存储结构不是树典型的存储结构表述方式。
2. 二叉树的遍历方式有（ ）
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 逆序遍历
答案：ABC
解析：二叉树常见的遍历方式有先序遍历（先访问根节点，然后访问左子树，最后访问右子树）、中序遍历（先访问左子树，然后访问根节点，最后访问右子树）和后序遍历（先访问左子树，然后访问右子树，最后访问根节点）。没有逆序遍历这种在二叉树标准遍历方式中的说法。
3. 以下关于平衡二叉树的描述正确的是（ ）
A. 左右子树的高度差保持在一个较小的范围内
B. 插入和删除节点时可能需要进行旋转操作来保持平衡
C. 能保证查找操作的时间复杂度在最坏情况下为 O (log n)
D. 一定是满二叉树
答案：ABC
解析：平衡二叉树是左右子树的高度差保持在一个较小的范围内（例如 AVL 树要求左右子树高度差绝对值不超过 1）的二叉树。在插入或删除节点时，为了维持平衡，可能需要进行旋转操作（如左旋、右旋等）。由于其平衡特性，保证了查找操作的时间复杂度在最坏情况下也能维持在 O (log n)。平衡二叉树不一定是满二叉树，它主要强调的是树的平衡性质，而满二叉树是对节点数量和结构的一种特定定义。
4. 二叉排序树的特点包括（ ）
A. 左子树所有节点的值都小于根节点的值
B. 右子树所有节点的值都大于根节点的值
C. 可以用于高效的查找、插入和删除操作
D. 一定是平衡二叉树
答案：ABC
解析：二叉排序树又称为二叉查找树，它的特点是对于树中任意一个节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。基于这个有序结构，可以用于高效的查找（通过比较节点值大小决定向左或向右子树查找）、插入（找到合适的叶子节点位置插入新节点）和删除操作（分多种情况处理以保持排序特性）。但二叉排序树不一定是平衡二叉树，它在插入顺序特殊的情况下可能会退化为斜树，导致性能下降。
5. 以下关于线索二叉树的说法正确的是（ ）
A. 利用了二叉树中空的指针来加速遍历
B. 线索二叉树有中序线索二叉树、先序线索二叉树和后序线索二叉树
C. 需要在节点结构中添加标志位来区分指针类型
D. 线索二叉树只能用于二叉树的中序遍历
答案：ABC
解析：线索二叉树是利用二叉树中那些空的指针（原本指向 NULL），将其指向树中的其他节点，用于加快遍历速度。根据线索化的遍历顺序不同，有中序线索二叉树、先序线索二叉树和后序线索二叉树。在节点结构设计上，除了常规的指向左子节点和右子节点的指针域外，还会添加标志位来区分该指针是正常的指向子节点的指针还是线索指针。线索二叉树不仅可以用于中序遍历，也可以用于先序和后序遍历，只是中序线索二叉树相对更常用一些。
三、判断题
1. 树中的节点数等于所有节点的度数加 1。（ ）
答案：正确
解析：度数是指节点拥有的子节点个数。除根节点外，每个节点都有一条边指向它，这些边的数量等于所有节点的度数之和。再加上根节点（没有边指向它），所以树中的节点数等于所有节点的度数加 1。
2. 完全二叉树一定是满二叉树。（ ）
答案：错误
解析：满二叉树是深度为 k 且有 2^(k + 1) - 1 个节点的二叉树，每一层节点数都达到最大值。完全二叉树是除第 k 层外，其它各层 (1~k - 1) 的节点数都达到最大个数，第 k 层所有的节点都连续集中在最左边。完全二叉树不一定是满二叉树，例如一个深度为 3 的完全二叉树，第 3 层可能只有部分节点，不是满二叉树的结构。
3. 二叉树的先序遍历和后序遍历序列可以唯一确定一棵二叉树。（ ）
答案：错误
解析：仅通过二叉树的先序遍历和后序遍历序列不能唯一确定一棵二叉树。因为先序遍历是先根节点，然后左子树、右子树；后序遍历是先左子树、右子树，然后根节点。这两种遍历方式对于一些结构不同但部分节点值相同的二叉树可能会产生相同的序列。但如果知道中序遍历序列以及另外一种遍历序列（先序或后序），则通常可以唯一确定一棵二叉树。
4. 哈夫曼树的构造过程中，每次选取权值最大的两个节点构建新的二叉树。（ ）
答案：错误
解析：哈夫曼树的构造过程是每次选取权值最小的两个节点构建一棵新的二叉树（作为左右子节点，新节点的权值为这两个节点权值之和），然后将新二叉树作为一个新的节点放回集合中，不断重复这个过程，直到构建出一棵完整的哈夫曼树。目的是使得最终构建的二叉树带权路径长度最短。
5. 在树的双亲表示法中，查找节点的子节点非常方便。（ ）
答案：错误
解析：在树的双亲表示法中，采用一组连续的存储空间来存储树中的节点，并且在每个节点结构中设置一个指针域用于指示该节点的双亲节点在数组中的位置。这种表示法便于查找节点的双亲，但查找子节点不太方便，需要遍历整个数组查找具有相同双亲下标的节点。
