文档介绍：常见数据结构
线性表、栈、队列、二叉树、图
1
可编辑版
（一）、线性表
线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，。例如：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，
每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。
2
可编辑版
（二）、栈
栈是允许在一端进行插入和删除操作的特殊线性表。
允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；
栈中元素个数为零时称为空栈。栈结构也称为后进先出表（LIFO）。
a1 a2 …… an
栈底
栈顶
MAXSIZE
TOP
3
可编辑版
队列(Queue)的定义
队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。
允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。
队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。
设队列q=(a0，a1，a2，…，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2， …，an-1的次序入队，出队也只能按照这个次序。
队列和栈相反，队列的操作是按先进先出（First In First Out）的原则进行的，又称为先进先出的线性表（简称FIFO表）。
三、队列
4
可编辑版
（四）、二叉树
类型与定义
5
可编辑版
二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。
A
B
C
D
E
F
G
H
K
根结点
左子树
右子树
E
F
6
可编辑版
二叉树的五种基本形态：
N
空树
只含根结点
N
N
N
L
R
R
右子树为空树
L
左子树为空树
左右子树均不为空树
7
可编辑版
介绍基本术语
叶子结点
结点
结点总数
深度
层
a
b
c
d
e
f
g
h
i
j
结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次累计。
树中结点的最大层次称为树的深度或高度。
8
可编辑版
性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1)
用归纳法证明：
归纳基：
归纳假设：
归纳证明：
i = 1 层时，只有一个根结点，
2i-1 = 20 = 1；
假设对所有的 j，1≤ j i，命题成立;
二叉树上每个结点至多有两棵子树，
则第 i 层的结点数 = 2i-2 2 = 2i-1 。
9
可编辑版
性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
证明：
基于上一条性质，深度为 k 的二叉树上的结点数至多为
20+21+ +2k-1 = 2k-1
10
可编辑版