![](https://csdnimg.cn/release/download_crawler_static/13034152/bg3.jpg)
栈是一种特殊的线性表,只允许在表的一端进行插入和删除的线性表;插入,删除的一
端为栈顶,另一端为栈底;当表中没有元素时为空栈。
栈是一种后进先出(或先进后出 Last In First Out)的线性表。栈具有记忆功能。栈的实
例:火车调度,子弹夹。
2、栈的存储结构
顺序存储结构:用一组地址连续的存储单元即一维数组来存储;
链式存储:用线性链表来存储;
3、栈的基本运算
(1) 入栈运算,在栈顶位置插入元素;
(2) 退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);
(3) 读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。
【考点 9】队列
1.队列的基本概念
队列是一种特殊的线性表,只允许在表的一端插入,在另一端删除,允许插入的一端是
队尾(rear),允许删除的一端为队头(front);当表中没有元素是空队列;队列是一种先进
先出的线性表。(FIFO)
2、队列的存储结构
顺序存储:一维数组。
链式存储:线性链表。
3、队列的运算:
(1) 入队运算:从队尾插入一个元素; (2) 退队运算:从队头删除一个元素。
4、队列的顺序存储结构一般采用循环队列的形式。循环队列 s=0 表示队列为空;s=1 且
front=rear 表示队满。
5、计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。
【考点 10】树的基本概念
树是一种非线性结构,是 n 个结点的有限集。当 n=0 时为空树,n>0 时为非空树。结点的
度:结点所拥有的子树的个数。
叶子结点:度为 0 的结点。
分支结点:除叶子结点以外的结点。
结点的层次:根结点在第一层,同一层上左右结点的子结点在下一层。
树的深度:所处层次最大的那个结点的层次。
树的度:树中所有结点的度的最大值。
【考点 11】二叉树及其基本性质
1、二叉树的概念
二叉树是一种特殊的树形结构,每个结点最多只有两棵子树,且有左右之分不能互换,因此,
二叉树有五种不同的形态。
2、二叉树的性质
性质 1 在二叉树的第 k 层上,最多有 2
k-1
(k≥1)个结点。
性质 2 深度为 m 的二叉树最多有 2
m
-1 个结点。
性质 3 在任意一棵二叉树中,度为 0 的结点(叶子结点)总是比度为 2 的结点多一个。
性质 4 具有 n 个结点的二叉树,其深度不小于[log
2
n]+1,其中[log
2
n]表示为 log
2
n 的整数部分。
【考点 12】满二叉树与完全二叉树
满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上
的结点数都达到最大值,即在满二叉树的第 k 层上有 2
k-1
个结点,且深度为 m 的满二叉树有