数据结构基础
一、数据结构的有关概念
1．掌握数据结构的有关概念，理解逻辑结构与物理结构之间的关系。
1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
2. 数据元素：数据的基本单位，一个数据元素可由若干数据项组成。
3. 数据项：数据的不可分割的最小单位。
4. 数据对象：性质相同的数据元素的集合，是数据的一个子集。
5. 数据结构：指互相之间存在着一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）。
6. 抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作，只取决于它的一组逻辑特性，用一个三元组表示（D, S, P）。
7. 数据类型：是程序设计语言中的一个概念，它是一个值的集合和操作的集合。
8. 逻辑结构：是指数据之间关系的描述，与数据的存储结构无关。分为线性结构和非线性结构，通常分为四类结构：
9. 存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。它包括数据元素的表示和关系的表示，
2．掌握数据结构的几种基本结构。
逻辑结构：是指数据之间关系的描述，与数据的存储结构无关。分为线性结构和非线性结构，通常分为四类结构：
1. 集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
2. 线性结构：结构中的数据元素之间存在一对一的关系。
3. 树型结构：结构中的数据元素之间存在一对多的关系。
4. 图状结构（网状结构）：结构中的数据元素之间存在多对多的关系。
存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。它包括数据元素的表示和关系的表示，通常由四种基本的存储方法实现：
1. **顺序存储**方式。数据元素顺序存放，每个存储结点只含一个元素，存储位置反映数据元素间的逻辑关系，存储密度大。有些操作（如插入、删除）效率较差。
2. **链式存储**方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针，指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），且不能折半查找。
3. **索引存储**方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。
4. **散列存储**方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。
3．掌握抽象数据类型的表示与实现方法。
抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作，只取决于它的一组逻辑特性，用一个三元组表示（D, S, P）。
4．熟悉算法分析的分析方法。
语句频度 T(n)，又被称为时间频度，指的是该语句重复执行的次数
详情
一
int i = 1;
int k = 0;
int n = 10;
while(i <= n-1){
k += 10 * i; /*计算该语句频度*/
i++;
}
while 循环了多少次，就是该语句的频度 while 执行一次 i 自增 1 ，当 i>n-1 时退出，就是当 i=n 时退出 while，i 一开始为 1，所以 while 总共循环了 n-1 次; 频度 ：n-1
二
int i = 1;
int k = 0;
int n = 10;
do{
k += 10 * i; /*计算该语句频度*/
i++;
}while(i <= n-1);
循环了多少次，就是该语句的频度 循环体执行一次 i 自增 1 ，当 i>n-1 时退出，就是当 i=n 时退出循环体，i 一开始为 1
，所以循环体总共循环了 n-1 次; 频度 ：n-1
三
int i = 1;
int k = 0;
int n = 10;
while(i <= n-1){
i++;
k += 10 * i; /*计算该语句频度*/
}
循环了多少次，就是该语句的频度 循环体执行一次 i 自增 1 ，当 i>n-1 时退出，就是当 i=n 时退出循环体，i 一开始为 1
，所以循环体总共循环了 n-1 次; 频度 ：n-1
四
int k = 0;
int n = 10;
for(int i = 1; i <= n; i++){
for(int j = i; j<=n; j++){
k++; /*计算该语句频度*/
}
}
第一层循环 n 次 第二层循环 n+(n-1)+(n-2)+…+2+1 = n(n+1)/2 ,所以 k++ 执行了 n(n+1)/2 次
频度 ：n(n+1)/2
五
int n = 100;
int i = 0;
while(n >= (i+1)*(i+1)){
i++; /*计算该语句频度*/
}
循环体执行 floor(sqrt(n)) 次 频度: ⌊ n ⌋ \lfloor \sqrt{n}\rfloor⌊ n ⌋
六
int x = 0;
int i,j,k;
int n = 10;
for(i = 1; i <= n; i++) {
for(j = 1; j <= i ; j++) {
for(k = 1; k <= j; k++) {
x += 1; /*计算该语句频度*/
}
}
}
第一层 n 第二层 1+2+3+4+…+n 第三层 1+(1+2)+(1+2+3)+(1+2+3+4)+…+(1+2+3+4+…+n) = n(n+1)(2n+3)/12 频度：n(n+1)(2n+3)/12
七
int i = 1;
int j = 0;
int n = 10;
while(i+j <= n){
if(i > j)/*计算该语句频度*/ j++;
else i++;
}
注意：if 语句不管真假都会判断一次，所以循环了多少次就判断了多少次 if 语句 当 i+j=n+1 时退出循环 所以循环次数为
(n+1)-1 = n 所以频度为 n
八
int x = 91;
int y = 100;
while(y > 0){
if(x > 100){ /*计算该判断语句频度*/
x -= 10;
y--;
}else{
x++;
}
}
看 while 循环体中的 if 语句频度就看 while 循环次数 开始 x=91 ,循环了 10 次，每次都执行 else ，直到
x=101 当 x=101，循环了 1 次，if 条件成立，x 又变成了 91 ，而 y=99; while
循环还没退出之前都是按照这规律循环，直到 y=0 退出 while ，一共重复了 100 遍上面的规律，每次 11 次循环，
所以该语句频度为 100*11 = 1100
注意
int k = 1;
for(int i = 1; i <= n ;i++){ //(1)
k++; //(2)
}
(1)语句频度是n+1 i 变量在第一个 for 循环中，从取 i = 0 开始执行，直到i=n时为止，至此，i
执行了n次。加上最后i=n+1跳出循环的判断，故，频度共n+1 次；(2)语句频度是n 当 i = n+1时跳出循环，所以里面的循环体一共执行了 n 次0
时间复杂度 简单的说，就是保留语句频度的最高次幂，并且把系数去掉。 如T(n)=2n^2+n+1=O(n)
二、线性表
掌握线性表的顺序存储方法及链式存储方法。
线性表的基本概念
- 线性表：是具有相同数据类型的 n 个数据元素的有限序列。
- 特点：
-
存在惟一的第一个元素。
-
存在惟一的最后一个元素。
-
除第一个元素之外，每个元素均只有一个直接前驱。
-
除最后一个元素之外，每个元素均只有一个直接后继。
- 线性表的存储结构：
- 顺序存储结构：顺序表
- 链式存储结构：链表
熟悉线性表的建立、插入、删除、搜索与归并算法。
2.2. 顺序表
顺序表的基本概念
-
顺序表：用顺序存储的方式实现线性表。顺序存储，将逻辑上相邻的元素存储在相邻的物理位置上。
-
特点：
- 随机访问，即可以在 O ( 1 ) O(1)O(1) 时间内找到第 i 个元素。
- 存储密度高，每个节点只存储数据元素。
- 拓展容量不方便（即使使用动态分配的方式实现，拓展长度的时间复杂度也比较高，因为需要把数据复制到新的区域）。
- 插入删除操作不方便，需移动大量元素：O ( n ) O(n)O(n)
#define MaxSize 10 // 定义最大长度
typedef struct {
int data[MaxSize]; // 使用静态的数组存放数据元素
int length; // 顺序表的当前长度
}SqList;
// 初始化顺序表
void InitList(SqList &L) {
L.length = 0; // 顺序表初始长度为0
}
// 在顺序表i位置插入e
bool ListInsert(SqList &L, int i, int e) {
if (i < 1 || i > L.length+1) // 判断i的范围是否有效
return false;
if (L.length >= MaxSize) // 判断存储空间是否已满
return false;
for (int j = L.length; j >= i; j--) // 将第i个元素之后的元素后移
L.data[j] = L.data[j-1];
L.data[i-1] = e; // 在位置i处放入e
L.length++; // 长度+1
return true;
}
// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList &L, int i, int &e) {
if (i < 1 || i > L.length) // 判断i的范围是否有效
return false;
e = L.data[i-1]; // 将被删除的元素赋值给e
for (int j = i; j < L.length; j++) //将第i个位置后的元素前移
L.data[j-1] = L.data[j];
L.length--;
return true;
}
// 查找第一个元素值为e的元素，并返回其位序
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++)
if (L.data[i] == e)
return i+1; // 数组下标为i的元素值等于e，返回其位序i+1
return 0; // 没有查找到
}
int main() {
SqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
ListInsert(L, 3, 3);
return 0;
}
2.3.1. 单链表的基本概念
- 单链表：用链式存储实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。
- 特点：
- 优点：不要求大片连续空间，改变容量方便。
- 缺点：不可随机存取，要耗费一定空间存放指针。
- 两种实现方式：
- 带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
- 不带头结点，麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。
2.3.2. 单链表的实现
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
// 初始化一个单链表（带头结点）
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
if (L == NULL) //内存不足，分配失败
return false;
L->next = NULL; //头结点之后暂时还没有结点
return true;
}
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
return False;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh，p最后会等于NULL
p = p->next;
j++;
}
//p值为NULL说明i值不合法
if (p==NULL)
return false;
//在第i-1个结点后插入新结点
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
//将结点s连到p后
return true;
}
// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L;
//循环找到第i-1个结点
while(p!=NULL && j<i-1){
//如果i>lengh，p和p的后继结点会等于NULL
p = p->next;
j++;
}
if(p==NULL)
return false;
if(p->next == NULL)
return false;
//令q暂时保存被删除的结点
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q)
return true;
}
// 查找数据域为e的结点指针，否则返回NULL
LNode * LocateElem(LinkList L, ElemType e){
LNode *P = L->next;
// 从第一个结点开始查找数据域为e的结点
while(p!=NULL && p->data != e){
p = p->next;
}
return p;
}
3．了解一元多项式的表示方法及其应用。
三、栈和队列
1．掌握栈和队列的顺序存储方法及链式存储方法。
3.1. 栈
3.1.1. 栈的基本概念
- 栈是特殊的线性表：只允许在一端进行插入或删除操作，其逻辑结构与普通线性表相同。
- 栈顶：允许进行插入和删除的一端 （最上面的为栈顶元素）。
- 栈底：不允许进行插入和删除的一端 （最下面的为栈底元素）。
- 空栈：不含任何元素的空表。
- 特点：后进先出（后进栈的元素先出栈）、LIFO（Last In First Out）。
- 缺点：栈的大小不可变，解决方法：共享栈。
2．熟悉进栈、出栈、进队、出队的实现方法。
3.1.3. 栈的顺序存储实现
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶元素
}SqStack;
// 初始化栈
void InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
}
// 新元素进栈
bool Push(SqStack &S, ElemType x){ // 判断栈是否已满
if(S.top == MaxSize - 1)
return false;
S.data[++S.top] = x;
return true;
}
// 出栈
bool Pop(SqStack &x, ElemType &x){ // 判断栈是否为空
if(S.top == -1)
return false;
x = S.data[S.top--];
return true;
}
共享栈（两个栈共享同一片空间）：
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}ShStack;
// 初始化栈
void InitSqStack(ShStack &S){
S.top0 = -1;
S.top1 = MaxSize;
}
3.1.4. 栈的链式存储实现
typedef struct Linknode{
ElemType data; //数据域
Linknode *next; //指针域
}Linknode,*LiStack;
// 初始化栈
bool InitStack(LiStack &L){
L = (Linknode *)malloc(sizeof(Linknode));
if(L == NULL)
return false;
L->next = NULL;
return true;
}
// 新元素入栈
bool pushStack(LiStack &L,ElemType x){
Linknode *s = (Linknode *)malloc(sizeof(Linknode));
if(s == NULL)
return false;
s->data = x;
// 头插法
s->next = L->next;
L->next = s;
return true;
}
// 出栈
bool popStack(LiStack &L, int &x){
// 栈空不能出栈
if(L->next == NULL)
return false;
Linknode *s = L->next;
x = s->data;
L->next = s->next;
free(s);
return true;
}
3.2. 队列
3.2.1. 队列的基本概念
- 队列是操作受限的线性表：只允许在一端进行插入 (入队)，另一端进行删除 (出队)。
- 队头：允许删除的一端。
- 队尾：允许插入的一端。
- 空队列：不含任何元素的空表。
- 特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）。
3.2.3. 队列的顺序存储实现
注意：
-
循环队列不能使用Q.rear == Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！
-
解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize == Q.front作为判断队列是否已满的条件。（主流方法）
-
解决方法二：设置 size 变量记录队列长度。
#define MaxSize 10; //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
// 初始化时，队头、队尾指针指向0
// 队尾指针指向的是即将插入数据的数组下标
// 队头指针指向的是队头元素的数组下标
Q.rear = Q.front = 0;
}
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
// 如果队列已满直接返回
if((Q.rear+1)%MaxSize == Q.front) //牺牲一个单元区分队空和队满
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
// 如果队列为空直接返回
if(Q.rear == Q.front)
return false;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
3.2.4. 队列的链式存储实现
// 链式队列结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}
// 链式队列
typedef struct{
// 头指针和尾指针
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 初始化时，front、rear都指向头结点
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front -> next = NULL;
}
// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
// 队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
if(Q.front == Q.rear)
return false;
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next;
// 如果p是最后一个结点，则将队头指针也指向NULL
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return true;
}
3．栈和对列的简单应用。
3.3.1 栈在括号匹配中的应用
- 栈在括号匹配中的应用
- 用栈实现括号匹配：
- 最后出现的左括号最先被匹配 （栈的特性——LIFO）。
- 遇到左括号就入栈。
- 遇到右括号，就“消耗”一个左括号（出栈）。
- 匹配失败情况：
- 扫描到右括号且栈空，则该右括号单身。
- 扫描完所有括号后，栈非空，则该左括号单身。
- 左右括号不匹配。
- 用栈实现括号匹配：
- 栈在表达式求值中的应用
中序表达式转后序表达式的具体规则如下：
- 准备两个栈（java.util.Stack），栈number用来存储数据和后序表达式的结果，栈action用来存储op(+、-、、/)。
2. 数字直接压入number栈，如果action栈为空，则op(+、-、、/)压栈，如果不为空，遵循 3 中的规则。
3. 遇到op(+、-、*、/)时检查此操作符和栈顶操作符的优先级，如果优先级高于栈顶操作符，则此操作符压入action栈，否则将栈顶操作符弹出压入number栈(number栈存储结果)，此操作符压栈。
4. 如果遇到“（”则直接压入action栈，如果 中检查优先级时栈顶的操作符为“（”则认为任何操作符的优先级高于“（”，直接将操作符压栈。
5. 如果遇到“）”则action弹栈并压入number栈，直到遇到“（”。
6. 中序表达式结束之后如果action栈不为空，则action弹栈并依次压入number栈。
7.所有操作结束后number中存储的就是后序表达式的反序，将number栈中的元素顺序反过来就是后序表达式
一
2 * ( 5 - 1 )
二
5 + 60 * ( 3 - 1 ) / ( 6 - 4 ) + 3
三
(23+34*45/(5+6+7))
一
2 5 1 - *
二
5 60 3 1 - * 6 4 - / 3 + +
三
23 34 45 * 5 6 + 7 + / +
3.3.4. 队列的应用
- 树的层次遍历
- 图的广度优先遍历
4．递归的实现。
四、串
1．掌握串的有关概念，了解顺序存储方法及链式存储方法。
4.1. 串的基本概念
- 串：即字符串（String）是由零个或多个字符组成的有限序列。
- 串的长度：中字符的个数 n，n = 0 n = 0n=0 时的串称为空串。
- 子串：串中任意个连续的字符组成的子序列。
- 主串：包含子串的串。
- 字符在主串中的位置：字符在串中的序号。
- 子串在主串中的位置：子串的第一个字符在主串中的位置 。
2．了解串的有关操作的实现方法。
- StrAssign(&T, chars)：赋值操作。把串 T 赋值为 chars。
- StrCopy(&T, S)：复制操作。由串 S 复制得到串 T。
- StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
- StrLength(S)：求串长。返回串 S 中元素的个数。
- ClearString(&S)：清空操作。将 S 清为空串。
- DestroyString(&S)：销毁串。将串 S 销毁（回收存储空间）。
- Concat(&T, S1, S2)：串联接。用 T 返回由 S1 和 S2 联接而成的新串 。
- SubString(&Sub, S, pos, len)：求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
- Index(S, T)：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为 0。
- StrCompare(S, T)：比较操作。若 S>T，则返回值>0；若 S=T，则返回值=0；若 S<T，则返回值<0。
3．了解串的模式匹配算法。
int index_BF(String S,String A){
int i=1,j=1;
while(i<=S->length&&j<=A->length){
printf("%c=%c\n",S->data[i],A->data[j]);
if(S->data[i]==A->data[j]){
i++;
j++;
}else{
i=i-j+2; //计算出下一个比较开始下标
j=1;
}
}
if(j>=A->length){
return i-A->length;
}else{
return -1;
}
}
void get_next(String S){
int next[S->length];//定义返回值变量
next[1]=0;
int i=1, j=0;
while(i<S->length){
if(j==0||S->data[i]==S->data[j]){
i++;j++;
next[i]=j;
}else{
j=next[j];
}
}
}
4．串的简单应用。
五、数组与广义表
1． 掌握数组的顺序存储方法及矩阵的压缩存储方法。
数据压缩
三角矩阵：主对角线两边对称
压缩思想：使用线性结构存储主对角线下三角部分，或者上三角部分达到压缩的效果。
元素存储线性结构位置：下三角或者上三角n-1项数列求和，再加上当前行。
上三角公式：i行号，j列。
稀疏矩阵：只有少数的元素是非空的
压缩是思想：使用数组或者链表去记录每个元素的（行、列、值）达到压缩效果。(是无法随机存取的)
如：array[1]={0,0,1}
array[2]={1,2,5}
array[3]={2,0,3}
十字链表法：记录稀疏矩阵的行排序和列排序。
压缩思想：记录行标和列表是数组达到压缩效果，但是有记录了行下一个元素位置和列下一个元素位置。
可以通过行数组或者列数组，遍历行列数据。
对角矩阵:主对角线或者反对角线的两边空元素对称
压缩思想：通过对角数，将8*8矩阵变成7*8矩阵 。
为了以后叙述方便，我们定义几个量：
diag：对角线条数
size：方阵高度
firstRowNum= ，第一行元素数（表达式易证）
2． 掌握矩阵的转置算法和矩阵的相加算法的实现。
3． 了解广义表在m元多项式中的简单应用。
广义表
广义表具有如下重要的特性：
（1）广义表中的数据元素有相对次序；
（2）广义表的长度定义为最外层包含元素个数；
（3）广义表的深度定义为所含括弧的重数。其中原子的深度为0，空表的深度为1；
（4）广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；
（5）广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值；
（6）任何一个非空广义表GL均可分解为表头head(GL) = a1和表尾tail(GL) = ( a2,…,an) 两部分。
为了简单起见,下面讨论的广义表不包括前面定义的再入表和递归表，即只讨论一般的广义表。
另外,我们规定用小写字母表示原子，用大写字母表示广义表的表名。例如：
A=() B=(e) C=(a,(b,c,d)) D=(A,B,C)=((),(e),(a,(b,c,d))) E=((a,(a,b),((a,b),c)))
其中A是一个空表，其长度为0；
B是只含有单个原子e的表，其长度为1；
C有两个元素，一个是原子a，另一个是子表，其长度为2；
D有三个元素，每个元素都是一个表，其长度为3；
E中只含有一个元素，是一个表，它的长度为1；
六、树和二叉树
1． 熟悉树和二叉树的有关定义，掌握二叉树的顺序存储结构和链式存储结构的实现方法。
5.1. 树的概念
5.1.1. 树的定义和基本术语
- 树是n（n≥0）个结点的有限集合，n = 0时，称为空树。
- 空树中应满足：
1. 有且仅有一个特定的称为根的结点。
2. 当n > 1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每个集合本 身 又是一棵树，并且称为根结点的子树。 - 度：树中一个结点的孩子个数称为该结点的度。所有结点的度的最大值是树的度。
- 度大于0的结点称为分支结点，度为0的结点称为叶子结点。
- 结点的层次（深度）：从上往下数。
- 结点的高度：从下往上数。
- 树的高度（深度）：树中结点的层数。
- 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
- 若树中结点的各子树从左至右是有次序的，不能互换，则该树称为有序树，否则称为无序树。
- 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
- 森林：森林是m（m≥0）棵互不相交的树的集合。
5.1.2. 树的常考性质
- 结点数 = 总度数 + 1
- 度为 m 的树、m 叉树的区别：
| 度为m的树 | m叉树的区别 |
|---|---|
| 任意结点的度≤m（最多m个孩子） | 任意结点的度≤m（最多m个孩子） |
| 至少有一个结点度=m（有m个孩子） | 允许所有结点的度都＜m |
| 一定是非空树，至少有m+1个结点 | 可以是空树 |
- 度为 m 的树第 i 层至多有 mi-1个结点（i≥1）；m 叉树第 i 层至多有 m i-1个结点（i≥1）。
- 高度为 h 的 m 叉树至多有
(
h
h
−
1
)
(
m
−
1
)
6
\frac{(h^h -1)(m-1)}{6}
6(hh−1)(m−1)
个结点。（等比数列求和） - 高度为 h 的 m 叉树至少有 h 个结点；高度为 h、度为 m 的树至少有（h+m-1）个结点。
- 具有 n 个结点的 m 叉树的最小高度为[
l
o
g
m
(
n
(
m
−
1
)
+
1
)
log_m(n(m-1)+1)
logm(n(m−1)+1)]
5.2. 二叉树
5.2.1. 二叉树的定义
二叉树是 n（n≥0）个结点的有限集合：
或者为空二叉树，即 n = 0。
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。
二叉树的特点：
每个结点至多只有两棵子树。
左右子树不能颠倒（二叉树是有序树）。
二叉树的五种状态：
\qquad\qquad
空二叉树
\qquad\qquad
只有左子树
\qquad\qquad
只有右子树
\qquad\qquad
只有根节点
\qquad\qquad
左右子树都有
2．掌握二叉树的建立及二叉树的几种遍历算法，了解树和森林的遍历方法。
3．了解最优线索二叉树、二叉树和哈夫曼树、b+树的应用。
4．其他简单应用。
七、图
1． 熟悉图的有关定义，掌握图的数组存储结构和邻接表存储结构的实现方法。
2．了解图的深度优先遍历算法和广度优先算法。
3．了解最小生成树、拓扑排序、关键路径的有关算法。
4．其他简单应用。
八、查找
1． 掌握静态查找表的几种查找方法。
2．掌握哈希表的构造方法及其冲突处理方法。
九、内部排序和外部排序
1． 掌握内部排序和外部排序的概念。
2． 熟悉插入排序、选择排序及常用的几种排序方法。能分析几种常用的排序算法的时间复杂度与空间复杂度。