文档内容
~ 2025年教师资格证·《信息技术》~
数 据 结 构 与 算 法 3 / 5
主讲老师 孙珍珍
粉笔教师教育 粉笔教师P273
四、栈与队列
（一）栈
特点1：只有一端开口，称为栈顶（top）；另一端封闭，称为栈底
特点2：只能在栈顶进行插入和删除，即入栈和出栈
特点3：先进后出（后进先出）
特点4：栈顶指针的具体位置不唯一P273
（一）栈
2.栈的顺序存储
Ø假设top指向栈顶元素
①位置：进栈/出栈在栈顶；②指针：进栈top+1 出栈top-1；③细节：一次性进/出的个数不限，但有顺序要求P274
（一）栈
3.栈的链式存储书上无
试题巩固
1.（2022 上·高中）栈是一个操作受限的数据结构，对其进行插入和删除必须在（ ）。
A.栈底 B.栈顶 C.任意位置 D.指定位置
2.（2023 下 · 高中）如果将 4 个数据元素 W 、X 、Y 、Z 依次全部放入一个堆栈中，那么第二个
移除的元素是（ ）。
A. X
B. W
C. Z
D. YP274
（二）队列
1.队列的定义：允许一端进行插入，另一端进行删除的线性表。
特点1：两端开口，队头（front）和队尾（rear）
特点2：入队在队尾，出队在队头
特点3：先进先出（后进后出）
特点4：队头和队尾指针的具体位置不唯一P275
（二）队列
2.队列的顺序存储
（1）顺序队列：假设队头指针front 指向队头元素，队尾指针rear指向队尾元素的下一个位置
①位置：进队在队尾，出队在队头；②指针：空队rear=front 进队rear＋1 出队 front + 1 ；
③细节：一次性进/出队的个数不限，但有顺序要求P275
（二）队列
（2）循环队列 【首尾相连的环】
Ø假设队头指针front 指向队头元素，队尾指针rear指向队尾元素的下一个位置。
①空队：front=rear ②满队：(rear+1)%n = front ③进队：(rear＋1)%n ④出队：(front＋1)%nP276
（二）队列
3.队列的链式存储书上无
试题巩固
（2021上·高中）栈和队列都是（ ）。
A.顺序存储的线性结构
B.链式存储的线性结构
C.限制存储点的线性结构
D.限制存储点的非线性结构
—个队列的输入序列是 1、2、3、4，则队列的输出序列是（ ）。
A. 3、2、4、1 B. 4、3、2、1
C. 1、2、3、4 D. 1、4、3、2第四节 树和二叉树P277
一、树
（一）树的定义
特点1：节点有限，可以为0。每一个分支又称为一棵树
特点2：除根节点外，其余节点有且只有一个前驱，根节点无前驱
特点3：除叶子节点外，所有节点可以有不止一个后继
特点4：n个节点有n-1条边P277
（二）树的相关术语
1.祖先、子孙、双亲、孩子、兄弟
2.节点的度、树的度
3. 分支节点、叶子节点
4.节点的层次、树的深度
5.有序树、无序树
6.路径、路径长度P278
二、二叉树
（一）二叉树的基本概念
1.二叉树的定义
特点1：每个节点最多有 2 棵子树
特点2：二叉树的子树严格区分左子树和右子树
特点3：有5种基本形态P279
（一）二叉树的基本概念
2.特殊二叉树
（1）满二叉树
特点1：除了叶子节点外，每个节点都有两个子节点
特点2：所有叶子节点都在同一层级上P279
（一）二叉树的基本概念
2.特殊二叉树
（2）完全二叉树
特点1：按满二叉树编号，中间无空缺
特点2：除了最后一层外，每一层都被完全填满
特点3：最后一层的所有节点都尽可能地集中在左边书上无
试题巩固
下列关于完全二叉树的说法，错误的是（ ）。
A.若一个节点没有左孩子，则它必为叶子节点
B.叶子节点的双亲的左兄弟一定不是叶子节点
C.若第i个节点为叶子节点，则编号大于i的节点一定是叶子节点
D.节点按二叉树的层序进行编号，第i个结点的右孩子编号为2iP280
（二）二叉树的性质
Ø性质 1：在二叉树的第 k 层上至多有 2k–1 个节点（k≥ 1）。
Ø性质 2：深度为 h 的二叉树至多有 2h –1 个节点（h ≥ 1）。P280
（二）二叉树的性质
Ø性质 3：如果其叶子节点数为 n ，度为 2 的节点数为 n ，则 n =n +1。
0 2 0 2P280
（二）二叉树的性质
Ø性质 4：具有 n 个节点的完全二叉树的深度为⌊log n⌋ + 1 。
2书上无
试题巩固
1.一棵具有 5 层的二叉树最多有 __________ 个节点。
2.某二叉树共有 7 个节点，其中叶子节点只有一个，则该二叉树的深度为__________。P280
（三）二叉树的存储结构
1.顺序存储结构
Ø用一维数组存储二叉树中的各个节点
【例 1】将 10 个节点的完全二叉树采用顺序结构进行存储。
下标： 1 2 3 4 5 6 7 8 9 10P281
（三）二叉树的存储结构
1.顺序存储结构
【例 2】将下图只有 6 个节点的二叉树采用顺序结构进行存储。
下标： 1 2 3 4 5 6 7 8 9 10P281
（三）二叉树的存储结构
2. 链式存储结构
Ø二叉树每个节点由数据域和指针域（左孩子和右孩子）组成
【例 】将 10 个节点的完全二叉树采用链式结构进行存储。P282
（四）二叉树的遍历
遍历：是依次访问二叉树中所有节点，使得每个节点有且仅被访问一次。
1.先序遍历
Ø根、左、右
方法1：根、左、右
方法2：左侧加点，再描边P282
（四）二叉树的遍历
2.中序遍历
Ø左、根、右
方法1：左、根、右
方法2：下方加点，再描边P283
（四）二叉树的遍历
3.后序遍历
Ø左、右、根
方法1：左、右、根
方法2：右侧加点，再描边P283
（四）二叉树的遍历
4.层遍历
Ø从上到下，从左到右
方法：从上到下，从左到右书上无
试题巩固
（2021上·高中）某二叉树结构如下图所示，其前序遍历的结果是（ ）。
A.ABDFGCEIH
B.ABDFGCEHI
C.ABDGFCEHI
D.ABDGFCEIH书上无
试题巩固
（2024 上·高中）某二叉树结构如下图所示，其中序遍历的结果是（ ）。
A. DBGFAEICH
B. DBGFAECIH
C. DBFGAEICH
D. DBFGACEIH下
节
内
容在 粉 笔
遇 见 不 一 样 的 自 己
粉笔教师教育 粉笔教师
