软件(三):树与二叉树、图、检索与排序
对应计算机软件技术「二、数据结构」后三条:树与二叉树的性质、遍历和哈夫曼树,图的概念、存储结构与遍历,顺序查找、二分查找和散列查找,常用排序方法的过程、复杂度与稳定性。
本节导读
这一节对应「二、数据结构」的后三条:「树与二叉树的概念及其应用」「图的概念及其存储结构」「检索与排序」。树和图是非线性结构:树是一对多,图是多对多。检索(查找)和排序是对各种结构最常做的两种运算。
学完要做到:会用二叉树的性质计算结点数,会由两种遍历序列还原二叉树,会构造哈夫曼树;会算邻接矩阵、邻接表的规模,会写深度优先和广度优先遍历序列;会做二分查找和线性探测散列;说清常用排序的过程、复杂度和稳定性。
树与二叉树
树是 n 个结点的有限集,有唯一的根,其余结点分成互不相交的子树。结点的子树个数叫度,度为 0 的结点叫叶子。
二叉树每个结点最多两棵子树,且分左右。主要性质:
- 第 i 层最多 2i−1 个结点;深度为 k 的二叉树最多 2k−1 个结点。
- 叶子数 n0 与度为 2 的结点数 n2 满足 n0=n2+1。
- n 个结点的完全二叉树深度为 ⌊log2n⌋+1;按层编号后,编号大于 ⌊n/2⌋ 的结点都是叶子。
遍历:先序(根、左、右),中序(左、根、右),后序(左、右、根),层次遍历按层从左到右。由先序和中序(或后序和中序)可以唯一确定一棵二叉树:先序的第一个是根,在中序里把它左右分开。
应用:哈夫曼树(带权路径长度 WPL 最小的二叉树)——每次选两个权最小的结点合并,用于哈夫曼编码;二叉排序树——左子树都比根小、右子树都比根大,中序遍历得到有序序列。
图的概念及其存储结构
图由顶点集和边集组成,分有向图和无向图。无向图所有顶点的度之和等于边数的 2 倍;n 个顶点的无向完全图有 n(n−1)/2 条边。
| 存储结构 | 做法 | 规模 |
|---|---|---|
| 邻接矩阵 | n×n 矩阵,有边处为 1(或权值) | n2 个元素,适合稠密图 |
| 邻接表 | 每个顶点一个链表,挂上它的邻接点 | 无向图 2e 个边结点,有向图 e 个,适合稀疏图 |
遍历:深度优先(DFS)从某顶点出发,沿一个未访问的邻点一直走下去,走不通再回退,类似树的先序;广度优先(BFS)先访问所有邻点,再一层层向外,借助队列。图的典型应用还有最小生成树(普里姆、克鲁斯卡尔算法)、最短路径(迪杰斯特拉算法)和拓扑排序。
检索
- 顺序查找:逐个比较,等概率下查找成功的平均查找长度为 (n+1)/2,对表没有要求。
- 二分查找:要求顺序存储且有序。取中间位置 mid=⌊(low+high)/2⌋ 比较,相等则成功,小了在左半找(high=mid−1),大了在右半找(low=mid+1);最多比较 ⌊log2n⌋+1 次。
- 二叉排序树查找:从根开始,比根小走左子树,比根大走右子树。
- 散列查找:用散列函数(如除留余数法 H(key)=keymodp)直接算地址;不同关键字算出同一地址叫冲突,常用开放定址法(线性探测:依次试 H+1、H+2、…)或链地址法处理。
本节后面还有约 1496 字:报名学员看全文
每门课前 10 节免费看全文;从第 11 节起,完整教程要报名后由顾问在后台为你的账号开通才能看。
题库账号可以直接登录,但第 11 节起的完整教程要报名后由后台开通才能看。
学完练一练
按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。第 11 节起的课后练习报名学员才能练。
本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。