Movle

1.Kafka之Consumer配置信息

1.Kafka之Producer配置信息

1.Kafka之Broker配置信息

1.查看当前服务器中的所有topic

1

bin/kafka-topics.sh --zookeeper bigdata13:2181 --list

2.创建topic

1

bin/kafka-topics.sh --zookeeper bigdata13:2181 --create --replication-factor 3 --partitions 1 --topic first

选项说明：

1
2
3
4
5

--topic 定义topic名

--replication-factor  定义副本数

--partitions  定义分区数

3.删除topic

1

bin/kafka-topics.sh --zookeeper bigdata11:2181 --delete --topic first

需要server.properties中设置delete.topic.enable=true否则只是标记删除或者直接重启。

4.发送消息

1
2
3
4
5

bin/kafka-console-producer.sh --broker-list bigdata11:9092 --topic first

>hello world

>itstar  itstar

5.消费消息

1

bin/kafka-console-consumer.sh --zookeeper bigdata11:2181 --from-beginning --topic first

–from-beginning：会把first主题中以往所有的数据都读取出来。根据业务场景选择是否增加该配置。

6.查看某个Topic的详情

1

bin/kafka-topics.sh --zookeeper bigdata11:2181 --describe --topic first 

一. 环境准备

1.集群规划

2.jar包下载

http://kafka.apache.org/downloads.html

3.虚拟机准备

(1).准备3台虚拟机

(2).配置ip地址

(3).配置主机名称

(4).3台主机分别关闭防火墙

4.安装jdk

5.安装Zookeeper

在hadoop2、hadoop3和hadoop4三个节点上部署Zookeeper
见之前的文章

二. Kafka集群部署

1.解压安装包

1

tar -zxvf kafka_2.11-0.11.0.2.tgz -C /opt/module/

2.修改解压后的文件名称

1

mv kafka_2.11-0.11.0.2/ kafka-2.11

3.在/opt/module/kafka目录下创建logs文件夹

1
2
3

cd /opt/module/kafka-2.11

mkdir logs

4.修改配置文件

1
2
3

cd config/

vi server.properties

输入以下内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#broker的全局唯一编号，不能重复

broker.id=0

#是否允许删除topic

delete.topic.enable=true

#处理网络请求的线程数量

num.network.threads=3

#用来处理磁盘IO的线程数量

num.io.threads=8

#发送套接字的缓冲区大小

socket.send.buffer.bytes=102400

#接收套接字的缓冲区大小

socket.receive.buffer.bytes=102400

#请求套接字的最大缓冲区大小

socket.request.max.bytes=104857600

#kafka运行日志存放的路径

log.dirs=/opt/module/kafka-2.11/logs

#topic在当前broker上的分区个数

num.partitions=1

#用来恢复和清理data下数据的线程数量

num.recovery.threads.per.data.dir=1

#segment文件保留的最长时间，超时将被删除

log.retention.hours=168

#配置连接Zookeeper集群地址

zookeeper.connect=hadoop2:2181,hadoop3:2181,hadoop4:2181

5.配置环境变量

1

vi /etc/profile

增加内容：

1
2
3
4

#KAFKA_HOME
export KAFKA_HOME=/opt/module/kafka-2.11

export PATH=$PATH:$KAFKA_HOME/bin

使环境变量生效：

1

source /etc/profile

6.分发安装包

1
2
3
4

cd /opt/module

scp -r /kafka root@hadoop3:/opt/module/
scp -r /kafka root@hadoop4:/opt/module/

7.分别在hadoop3和hadoop4上修改配置文件

1

vi /opt/module/kafka-2.11/config/server.properties

将broker.id改了

1
2
3
4
5

//bigdata12
broker.id=1

//bigdata13
broker.id=2

注：broker.id不得重复

8.启动集群

依次在hadoop2、hadoop3、hadoop4节点上启动kafka(加上& ,是在后台启动)

1
2
3
4
5
6
7
8

//hadoop2
bin/kafka-server-start.sh config/server.properties &

//hadoop3
bin/kafka-server-start.sh config/server.properties &

//hadoop4
bin/kafka-server-start.sh config/server.properties &

9.关闭集群

1
2
3
4
5
6
7
8

//hadoop2
bin/kafka-server-stop.sh stop

//hadoop3
bin/kafka-server-stop.sh stop

//hadoop4
bin/kafka-server-stop.sh stop

一.Kafka是什么

    Kafka是最初由Linkedin公司开发，是一个分布式、支持分区的(partition)、多副本的(replica)，基于zookeeper协调的分布式消息系统，它的最大的特性就是可以实时的处理大量数据以满足各种需求场景：比如基于hadoop的批处理系统、低延迟的实时系统、storm/Spark流式处理引擎，web/nginx日志、访问日志，消息服务等等，用scala语言编写，Linkedin于2010年贡献给了Apache基金会并成为顶级开源 项目。

二. 架构模型

三. JMS是什么

1.是什么：

JMS(Java Message Service)是Java提供的一套技术规范

2.作用：

    用来异构系统 集成通信，缓解系统瓶颈，提高系统的伸缩性增强系统用户体验，使得系统模块化和组件化变得可行并更加灵活

3.传输模型：

(1)点对点模式(一对一，消费者主动拉取数据，消息收到后消息清除)

    点对点模型通常是一个基于拉取或者轮询的消息传送模型，这种模型从队列中请求信息，而不是将消息推送到客户端。这个模型的特点是发送到队列的消息被一个且只有一个接收者接收处理，即使有多个消息监听者也是如此。

(2)发布/订阅模式(一对多，数据生产后，推送给所有订阅者)

    发布订阅模型则是一个基于推送的消息传送模型。发布订阅模型可以有多种不同的订阅者，临时订阅者只在主动监听主题时才接收消息，而持久订阅者则监听主题的所有消息，即使当前订阅者不可用，处于离线状态。

四.Kafka的特性

1.高吞吐量、低延迟：

    kafka每秒可以处理几十万条消息，它的延迟最低只有几毫秒，每个topic可以分多个partition, consumer group 对partition进行consume操作。

2.可扩展性：

kafka集群支持热扩展

3.持久性、可靠性：

消息被持久化到本地磁盘，并且支持数据备份防止数据丢失

4.容错性：

允许集群中节点失败（若副本数量为n,则允许n-1个节点失败）

5.高并发：

支持数千个客户端同时读写

五. 使用场景

1.日志收集：

    一个公司可以用Kafka可以收集各种服务的log，通过kafka以统一接口服务的方式开放给各种consumer，例如hadoop、Hbase、Solr等。

2.消息系统：

    解耦和生产者和消费者、缓存消息等。

3.用户活动跟踪：

    Kafka经常被用来记录web用户或者app用户的各种活动，如浏览网页、搜索、点击等活动，这些活动信息被各个服务器发布到kafka的topic中，然后订阅者通过订阅这些topic来做实时的监控分析，或者装载到hadoop、数据仓库中做离线分析和挖掘。

4.运营指标：

    Kafka也经常用来记录运营监控数据。包括收集各种分布式应用的数据，生产各种操作的集中反馈，比如报警和报告。

5.流式处理：

    比如spark streaming和storm

6.事件源

六.分布式模型

    Kafka每个主题的多个分区日志分布式地存储在Kafka集群上，同时为了故障容错，每个分区都会以副本的方式复制到多个消息代理节点上。其中一个节点会作为主副本(Leader)，其他节点作为备份副本(Follower，也叫作从副本)。主副本会负责所有的客户端读写操作，备份副本仅仅从主副本同步数据。当主副本出现故障时，备份副本中的一个副本会被选择为新的主副本。因为每个分区的副本中只有主副本接受读写，所以每个服务器端都会作为某些分区的主副本，以及另外一些分区的备份副本，这样Kafka集群的所有服务端整体上对客户端是负载均衡的。

    Kafka的生产者和消费者相对于服务器端而言都是客户端。

    Kafka生产者客户端发布消息到服务端的指定主题，会指定消息所属的分区。生产者发布消息时根据消息是否有键，采用不同的分区策略。消息没有键时，通过轮询方式进行客户端负载均衡；消息有键时，根据分区语义（例如hash）确保相同键的消息总是发送到同一分区。

    Kafka的消费者通过订阅主题来消费消息，并且每个消费者都会设置一个消费组名称。因为生产者发布到主题的每一条消息都只会发送给消费者组的一个消费者。所以，如果要实现传统消息系统的“队列”模型，可以让每个消费者都拥有相同的消费组名称，这样消息就会负责均衡到所有的消费者；如果要实现“发布-订阅”模型，则每个消费者的消费者组名称都不相同，这样每条消息就会广播给所有的消费者。

    分区是消费者现场模型的最小并行单位。如下图（图1）所示，生产者发布消息到一台服务器的3个分区时，只有一个消费者消费所有的3个分区。在下图（图2）中，3个分区分布在3台服务器上，同时有3个消费者分别消费不同的分区。假设每个服务器的吞吐量时300MB，在下图（图1）中分摊到每个分区只有100MB，而在下图（图2）中，集群整体的吞吐量有900MB。可以看到，增加服务器节点会提升集群的性能，增加消费者数量会提升处理性能。

    同一个消费组下多个消费者互相协调消费工作，Kafka会将所有的分区平均地分配给所有的消费者实例，这样每个消费者都可以分配到数量均等的分区。Kafka的消费组管理协议会动态地维护消费组的成员列表，当一个新消费者加入消费者组，或者有消费者离开消费组，都会触发再平衡操作。

    Kafka的消费者消费消息时，只保证在一个分区内的消息的完全有序性，并不保证同一个主题汇中多个分区的消息顺序。而且，消费者读取一个分区消息的顺序和生产者写入到这个分区的顺序是一致的。比如，生产者写入“hello”和“Kafka”两条消息到分区P1，则消费者读取到的顺序也一定是“hello”和“Kafka”。如果业务上需要保证所有消息完全一致，只能通过设置一个分区完成，但这种做法的缺点是最多只能有一个消费者进行消费。一般来说，只需要保证每个分区的有序性，再对消息假设键来保证相同键的所有消息落入同一分区，就可以满足绝大多数的应用。

一.排序的基本概念与分类

1.定义：

(1)排序：

假设含有n个记录的序列为{r₁,r₂,……,r_n}，其相应的关键字分别为{k₁,k₂,……,k_n}，需确定1,2,……,n的一种排列p₁,p₂,……,p_n，使其相应的关键字满足k_p1≤k_p2≤……≤k_pn(非递减或非递增)关系，即使得序列成为一个按关键字有序的序列{r_p1,r_p2,……,r_pn}，这样的操作就称为排序

2.排序的稳定性：

(1)假设k_i=k_j(1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中r_i领先于r_j(即i<j)。如果排序后r_i仍领先于r_j，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中r_j领先r_i，则称所用的排序方法是不稳定的

3.内排序与外排序

(1)内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中

(2)外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行

(3)对于内排序来说，排序算法的性能主要是受3个方面影响：

• 时间性能：高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数
• 辅助空间：评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间
• 算法的复杂性：这里指的是算法本身的复杂度，而不是指算法的时间复杂度

(4)内排序分为：插入排序、交换排序、选择排序和归并排序

二.冒泡排序

1.冒泡排序的基本思想：

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

2.冒泡排序算法：

3.冒泡排序代码实现：

1
2
3
4
5
6
7
8
9
10
11
12

```
#### 4.冒泡排序优化

#### 5.冒泡排序复杂度：
冒泡排序的时间复杂度为O(n2)。

### 三.简单选择排序
#### 1.简单选择排序算法：
##### (1)定义：
简单选择排序法(Simple Selection Sort)就是通过n-i次关键字间的比较，从n-i＋1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换之

##### (2)代码实现：

1
2
3
4
5
6
7
8
9
10
11

#### 2.简单选择排序复杂度分析：
(1)简单选择排序的“时间复杂度依然为O(n<sup>2</sup>)

(2)尽管与冒泡排序同为O(n2)，但简单选择排序的性能上还是要略优于冒泡排序

### 四.直接插入排序
#### 1.直接插入排序算法：
##### (1)定义：
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表 

##### (2)代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#### 2.直接插入排序复杂度分析
(1)直接插入排序法的时间复杂度为O(n<sup>2</sup>)

(2)同样的O(n2)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些

### 五.希尔排序
#### 1.希尔排序原理：
#### 2.希尔排序算法：
#### 3.希尔排序复杂度分析：

### 六.堆排序：
#### 1.定义：
##### (1)堆排序(HeapSort)，就是对简单选择排序进行的一种改进

##### (2)堆是具有下列性质的完全二叉树：

* 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆(如图所示)；
* 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

![堆](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy80MzkxNDA3LTZlODM2ZGEzMGM1NjY4NDUucG5n?x-oss-process=image/format,png)

#### 2.堆排序算法：
##### (1)堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法

##### (2)基本思想：
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了

##### (3)代码实现：

1
2
3
4
5
6
7
8
9
10
11

#### 3.堆排序复杂度分析：
##### (1)堆排序的时间复杂度为O(nlogn)

### 七.归并排序：
#### 1.归并排序算法：
##### (1)归并排序（Merging Sort）就是利用归并的思想实现的排序方法

##### (2)原理：
它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到|n/2|（|x|表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序 

##### (3)代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#### 2.归并排序复杂度分析：
##### (1)归并排序的算法复杂度为O(nlogn)

###### 3.非递归实现归并排序：
##### (1)代码实现：

##### (2)使用归并排序时，尽量考虑用非递归方法

### 八.快速排序：
#### 1.含义：
(1)希尔排序相当于直接插入排序的升级，它们同属于插入排序类
(2)堆排序相当于简单选择排序的升级，它们同属于选择排序类。
(3)而快速排序其实就是冒泡排序的升级，它们都属于交换排序类

#### 2.快速排序算法：
##### (1)基本思想：
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的

##### (2)代码实现：

```

3.快速排序复杂度分析：

(1)快速排序的算法复杂度为O(nlogn)

4.快速排序的优化

(1)优化选取枢轴
(2)优化不必要的交换
(3)优化小数组时的排序方案
(4)优化递归操作：

九.总结：

1.将内排序分为：插入排序、交换排序、选择排序和归并排序四类

2.排序算法复杂度：

3.从算法的简单性来看，我们将7种算法分为两类：

• 简单算法：冒泡、简单选择、直接插入
• 改进算法：希尔、堆、归并、快速

(1)从平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3种简单算法。

(2)从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑4种复杂的改进算法。

(3)从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序

(4)从稳定性来看，归并排序独占鳌头，对于非常在乎排序稳定性的应用中，归并排序是个好算法

一.查找概论

1.概念：

(1)查找表(Search Table)

是由同一类型的数据元素(或记录)构成的集合

(2)关键字（Key）

是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），称为关键码

(3)主关键字：

若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）

(4)次关键字：

对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字，次关键字也可以理解为是不以唯一标识一个数据元素（或记录）的关键字，它对应的数据项就是次关键码

2.查找表按照操作方式来分有两大种：静态查找表和动态查找表

(1)静态查找表(Static Search Table)：只作查找操作的查找表。

它的主要操作有：

• 查询某个“特定的”数据元素是否在查找表中
• 检索某个“特定的”数据元素和各种属性

(2)动态查找表(Dynamic Search Table)：

在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素
动态查找表的操作就是两个：

• 查找时插入数据元素
• 查找时删除数据元素

3.面向查找操作的数据结构称为查找结构

二.顺序表查找

1.顺序查找(Sequential Search):又叫线性查找，是最基本的查找技术

2.顺序表查找算法：

3.顺序表查找算法优化：

三.有序表查找

1.折半查找

(1)折半查找(Binary Search)技术，又称为二分查找。

它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

(2)折半查找的基本思想是：

在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止

(3)折半算法的时间复杂度为O(logn)

2.插值查找

插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式(key-a[low])/(a[high]-a[low])

3.斐波那契查找

(1)斐波那契查找(Fibonacci Search)，是利用黄金分割原理来实现的

(2)“斐波那契查找算法的核心在于：

• 当key=a[mid]时，查找就成功；
• 当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
• 当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个

4.三种有序表查找的区别在于：

• 折半查找是进行加法与除法运算(mid=(low＋high)/2)，
• 插值查找进行复杂的四则运算(mid=low＋(high-low)*(key-a[low])/(a[high]-a[low]))，
• 而斐波那契查找只是最简单加减法运算(mid=low＋F[k-1]-1)

四.线性索引查找

1.含义：

(1)索引是为了加快查找速度而设计的一种数据结构。

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息

(2)索引按照结构可以分为线性索引、树形索引和多级索引

(3)所谓线性索引就是将索引项集合组织为线性结构，也称为索引表

2.稠密索引

(1)稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项

(2)索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高了效率

3.分块索引

(1)分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

• 块内无序，即每一块内的记录不要求有序
• 块间有序

(2)定义的分块索引的索引项结构分三个数据项：

• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
• 存储了块中的记录个数，以便于循环时使用；
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历

(3)在分块索引表中查找，就是分两步进行：

• 一是在分块索引表中查找要查关键字所在的块
• 二是根据块首指针找到相应的块，并在块中顺序查找关键码

4.倒排索引

(1)倒排索引的索引项通用结构是：

• 次关键码，例如上面的“英文单词”；
• 记录号表，例如上面的“文章编号”。

(2)其中记录号表存储具有相同次关键字的所有记录的记录号,这样的索引方法就是倒排索引

(3)由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引

五.二叉排序树

1.含义：

(1)二叉排序树(Binary Sort Tree)，又称为二叉查找树。

它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

2.二叉排序树查找操作

(1)二叉树结构

1
2
3
4
5
6
7
8
9

/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef  struct BiTNode                 
{
    /* 结点数据 */
    int data;                           
    /* 左右孩子指针 */
    struct BiTNode *lchild, *rchild;    
} BiTNode, *BiTree;

(2)二叉树插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并
   返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点
   并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    /* 查找不成功 */
    if (!T)                                        
    {
        *p = f;
        return FALSE;
    }
    /* 查找成功 */
    else if (key == T->data)                       
    {
       *p = T;
       return TRUE;
    }
    else if (key < T->data)
        /* 在左子树继续查找 */
        return SearchBST(T->lchild, key, T, p);    
    else
        /* 在右子树继续查找 */
        return SearchBST(T->rchild, key, T, p);    
}

3.二叉排序树插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/* 当二叉排序树T中不存在关键字等于key的数据元
   素时， */
/* 插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{
    BiTree p, s;
    /* 查找不成功 */
    if (!SearchBST(*T, key, NULL, &p))    
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p)
            /* 插入s为新的根结点 */
            *T = s;                       
        else if (key < p->data)
            /* 插入s为左孩子 */
            p->lchild = s;                
        else
            /* 插入s为右孩子 */
            p->rchild = s;                
        return TRUE;
    }
    else
        /* 树中已有关键字相同的结点，不再插入 */
        return FALSE;                     
}

4.二叉排序树的删除操作：

(1)删除结点三种情况：

• 叶子结点；
• 仅有左或右子树的结点；
• 左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树T查找key，查找到时删除

5.二叉排序树总结：

(1)二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可

(2)一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树

六.平衡二叉树

1.含义：

(1)平衡二叉树(Self-Balancing Binary SearchTree或Height-Balanced Binary Search Tree)

是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1

(2)要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树

(3)距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树

2.平衡二叉树的实现原理：

(1)当最小不平衡子树根结点的平衡因子BF是大于1时，就右旋，小于-1时就左旋

3.平衡二叉树实现算法：

(1)二叉树结构定义

1
2
3
4
5
6
7
8
9
10
11

/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef struct BiTNode                  
{
    /* 结点数据 */
    int data;                           
    /* 结点的平衡因子 */
    int bf;                             
    /* 左右孩子指针 */
    struct BiTNode *lchild, *rchild;    
} BiTNode, *BiTree; 

(2)右旋操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/* 对以p为根的二叉排序树作右旋处理， */
/* 处理之后p指向新的树根结点，即旋转处理之前
   的左子树的根结点 */
void R_Rotate(BiTree *P)
{
    BiTree L;
    /* L指向P的左子树根结点 */
    L = (*P)->lchild;            
    /* L的右子树挂接为P的左子树 */
    (*P)->lchild = L->rchild;    
    L->rchild = (*P);
    /* P指向新的根结点 */
    *P = L;                      
} 

(3)左旋操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/* 对以P为根的二叉排序树作左旋处理， */
/* 处理之后P指向新的树根结点，即旋转处理之前
   的右子树的根结点0 */
void L_Rotate(BiTree *P)
{
    BiTree R;
    /* R指向P的右子树根结点 */
    R = (*P)->rchild;            
    /* R的左子树挂接为P的右子树 */
    (*P)->rchild = R->lchild;    
    R->lchild = (*P);
    /* P指向新的根结点 */
    *P = R;                      
}

七.多路查找树(B树)

1.含义：

(1)多路查找树(muitl-way search tree)，

其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

(2)四种特殊形式：2-3树、2-3-4树、B树和B+树

2.2-3树

(1)含义：

2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点)

(2)一个2结点包含一个元素和两个孩子(或没有孩子)，

且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子

(3)一个3结点包含一小一大两个元素和三个孩子(或没有孩子)，

如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素

(4)2-3树的插入实现：

对于2-3树的插入来说，与二叉排序树相同，插入操作一定是发生在叶子结点上。可与二叉排序树不同的是，2-3树插入一个元素的过程有可能会对该树的其余结构产生连锁反应

(5)2-3树插入分三种情况：

• 对于空树，插入一个2结点即可
• 插入结点到一个2结点的叶子上。应该说，由于其本身就只有一个元素，所以只需要将其升级为3结点即可
• 要往3结点中插入一个新元素。因为3结点本身已经是2-3树的结点最大容量(已经有两个元素)，因此就需要将其拆分，且将树中两元素或插入元素的三者中选择其一向上移动一层

(6)2-3树的删除实现：

• 所删除元素位于一个3结点的叶子结点上， 只需要在该结点处删除该元素即可，不会影响到整棵树的其他结点结构
• 所删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点，分四种情形，情形一，结点的双亲也是2结点，且拥有一个3结点的右孩子。若要删除结点1，那么只需要左旋即可；情形二，结点的双亲是2结点，它的右孩子也是2结点；情形三，此结点的双亲是一个3结点；情形四，当前树是一个满二叉树的情况
• 所删除的元素位于非叶子的分支结点。此时通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可

3.2-3-4树

(1)含义：

它其实就是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子(或没有孩子)，一个4结点要么没有孩子，要么具有4个孩子。如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素

4.B树

(1)含义：

结点最大的孩子数目称为B树的阶（order），因此，2-3树是3阶B树，2-3-4树是4阶B树。

(2)一个m阶的B树具有如下属性：

• 如果根结点不是叶结点，则其至少有两棵子树。
• 每一个非根的分支结点都有k-1个元素和k个孩子，其中。每一个叶子结点n都有k-1个元素，
• 所有叶子结点都位于同一层次。
• 所有分支结点包含下列信息数据

(3)在B树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程

(4)至于B树的插入和删除，方式是与2-3树和2-3-4树相类似的，只不过阶数可能会很大而已

5.B+树

(1)含义：

B+树是应文件系统所需而出的一种B树的变形树

(2)在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针

(3)一棵m阶的B+树和m阶的B树的差异在于：

• 有n棵子树的结点中包含有n个关键字；
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大(或最小)关键字

(4)B+树的插入、删除过程也都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已

八.散列表查找(哈希表)概述

1.散列表查找定义：

(1)散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f

(2)这种对应关系f称为散列函数，又称为哈希（Hash）函数

(3)按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。那么关键字对应的记录存储位置我们称为散列地址

2.散列表查找步骤：

(1)在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录

(2)当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录

3.散列主要是面向查找的存储结构。

九.散列函数的构造方法

1.好的散列函数的两个原则：

(1)计算简单

(2)散列地址分布均匀

2.直接定址法

3.数字分析法：

(1)抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段

(2)数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法

4.平方取中法

5.折叠法：

(1)含义：

折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址

6.除留余数法：

此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：

1

f(key)=key mod p(p≤m)

mod是取模（求余数）的意思

6.随机数法：

7.采用不同散列函数的因素：

(1).计算散列地址所需的时间
(2).关键字的长度
(3).散列表的大小
(4).关键字的分布情况
(5).记录查找的频率

十.处理散列冲突的方法：

1.开放定址法

2.再散列函数法

3.链地址法

4.公共溢出区法

十一.散列表查找实现

1.散列表查找算法实现

2.散列表查找性能分析

(1)如果没有冲突，散列查找是我们本章介绍的所有查找中效率最高的，因为它的时间复杂度为O(1)
(2)散列查找的平均查找长度取决于的因素

• 散列函数是否均匀
• 处理冲突的方法
• 散列表的装填因子，所谓的装填因子α=填入表中的记录个数/散列表长度。α标志着散列表的装满的程度。当填入表中的记录越多，α就越大，产生冲突的可能性就越大

一.图的定义

1.定义：

(1)图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

(2)图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分

(3)图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图

(4)图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度

(5)图上的边或弧上带权则称为网

(6)图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量

(7)无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林

二.图的抽象数据类型

三.图的存储结构

1.邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图
(1)设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

2.邻接表

(1)定义：

图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

3.十字链表

(1)十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度

4.邻接多重表

5.边集数组

(1)边集数组是由两个一维数组构成。

一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成

四.图的遍历

1.深度优先遍历

(1)深度优先遍历(Depth_First_Search)，也有称为深度优先搜索，简称为DFS

2.广度优先遍历

(1)广度优先遍历(Breadth_First_Search)，又称为广度优先搜索，简称BFS

五.最小生成树

1.普里姆(prim)算法

2.克鲁斯卡尔(Kruskal)算法

六.最短路径

1.迪杰斯特拉(Dijkstra)算法

2.弗洛伊德（Floyd）算法

七.拓扑排序

1.拓扑排序算法

八.关键路径

1.关键路径算法原理

2.关键路径算法

一.树的定义

1.定义：

(1)树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树

(2)在任意一棵非空树中：

• 有且仅有一个特定的称为根（Root）的结点；
• 当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树

(3)注意：

• n>0时，根结点是唯一的
• m>0时，子树的个数没有限制，但它们一定是互不相交的

2.结点的分类

(1)树的结点包含一个数据元素及若干指向其子树的分支。
(2)结点拥有的子树数称为结点的度（De-gree）
(3)度为0的结点称为叶结点（Leaf）或终端结点；
(4)度不为0的结点称为非终端结点或分支结点。
(5)除根结点之外，分支结点也称为内部结点。
(6)树的度是树内各结点的度的最大值

3.结点间的关系

(1)结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）
(2)同一个双亲的孩子之间互称兄弟（Sibling）
(3)结点的祖先是从根到该结点所经分支上的所有结点
(4)以某结点为根的子树中的任一结点都称为该结点的子孙

4.树的其他相关概念：

(1)结点的层次(Level):

从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树就在第l+1层。其双亲在同一层的结点互为堂兄弟。显然图6-2-6中的D、E、F是堂兄弟，而G、H、I与J也是堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度

(2)将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树

(3)森林（Forest）是m（m≥0）棵互不相交的树的集合

(4)线性表与树的区别

二.树的抽象数据类型

三.树的存储结构

双亲表示法、孩子表示法、孩子兄弟表示法可以实现对树的存储结构的表示

1.双亲表示法

2.孩子表示法

3.孩子兄弟表示法

四.二叉树的定义

1.二叉树的特点：

(1)每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的

(2)左子树和右子树是有顺序的，次序不能任意颠倒。

(3)即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。如图所示，树1和树2是同一棵树，但它们却是不同的二叉树。

2.二叉树具有5种基本形态：

(1).空二叉树
(2).只有一个根结点
(3).根结点只有左子树
(4).根结点只有右子树
(5).根结点既有左子树又有右子树”

3.特殊二叉树

(1)斜树：

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树

(2)满二叉树：

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

(a)满二叉树的特点有：

• 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
• 非叶子结点的度一定是2。
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

(3)完全二叉树：

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

• 首先，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的
• 其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的

(a)完全二叉树的特点：

• 叶子结点只能出现在最下两层。
• 最下层的叶子一定集中在左部连续位置。
• 倒数二层，若有叶子结点，一定都在右部连续位置。
• 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
• 同样结点数的二叉树，完全二叉树的深度最小”

五.二叉树的性质

1.性质一

性质1:在二叉树的第i层上至多有2<sup>i-1</sup>个结点（i≥1）”

2.性质二

性质2：深度为k的二叉树至多有2<sup>k</sup>-1个结点（k≥1）

3.性质三

性质3：对任何一棵二叉树T，如果其终端结点数为n<sub>0</sub>，度为2的结点数为n<sub>2</sub>，则n<sub>0</sub>=n<sub>2</sub>+1。

4.性质四

性质4：具有n个结点的完全二叉树的深度为|log<sub>2</sub>n+1|（|x|表示不大于x的最大整数）

5.性质五

性质5：如果对一棵有n个结点的完全二叉树（其深度为i）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：

• 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
• 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。”

六.二叉树的存储结构

1.二叉树顺序存储结构

2.二叉链表

七.遍历二叉树

1.二叉树遍历原理

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

2.二叉树遍历方法：

(1)前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示，遍历的顺序为：ABDGH-CEIF

前序遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);          
    /* 再先序遍历左子树 */
    PreOrderTraverse(T->lchild);    
    /* 最后先序遍历右子树 */
    PreOrderTraverse(T->rchild);    
}

(2)中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示，遍历的顺序为：GDHBAE-ICF

中序遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 中序遍历左子树 */
    InOrderTraverse(T->lchild);    
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);         
    /* 最后中序遍历右子树 */
    InOrderTraverse(T->rchild);    
}

(3)后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图所示，遍历的顺序为：GHDBIEFCA

后序遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 先后序遍历左子树 */
    PostOrderTraverse(T->lchild);    
    /* 再后序遍历右子树 */
    PostOrderTraverse(T->rchild);    
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);           
} 

(4)层序遍历：

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图所示，遍历的顺序为：ABCDEFGHI

3.推导遍历结果：

(1)二叉树遍历的两个性质：

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

(2)已知前序和后序遍历，是不能确定一棵二叉树的

八.二叉树的建立

1.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树T。 */
void CreateBiTree(BiTree *T)
{
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#')
      *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T)
            exit(OVERFLOW);
        /* 生成根结点 */
        (*T)->data = ch;                
        /* 构造左子树 */
        CreateBiTree(&(*T)->lchild);    
        /* 构造右子树 */
        CreateBiTree(&(*T)->rchild);    
    }
}

九.线索二叉树

1.线索二叉树原理

2.线索二叉树结构实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* 二叉树的二叉线索存储结构定义 */
/* Link==0表示指向左右孩子指针 */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link, Thread} PointerTag;    
/* 二叉线索存储结点结构 */
typedef struct BiThrNode                   
{
    /* 结点数据 */
    TElemType data;                        
    /* 左右孩子指针 */
    struct BiThrNode *lchild, *rchild;     
    PointerTag LTag;
    /* 左右标志 */
    PointerTag RTag;                       
} BiThrNode, *BiThrTree;” 

3.中序遍历线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

BiThrTree pre;                     /* 全局变量，始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
    if (p)
    {
        /* 递归左子树线索化 */
        InThreading(p->lchild);    
        /* 没有左孩子 */
        if (!p->lchild)            
        {
            /* 前驱线索 */
            p->LTag = Thread;      
            /* 左孩子指针指向前驱 */
            p->lchild = pre;       
        }
        /* 前驱没有右孩子 */
        if (!pre->rchild)          
        {
            /* 后继线索 */
            pre->RTag = Thread;    
            /* 前驱右孩子指针指向后继（当前结点p） */
            pre->rchild = p;       
        }
        /* 保持pre指向p的前驱 */
        pre = p;                   
        /* 递归右子树线索化 */
        InThreading(p->rchild);    
    }
}

十.树，二叉树，森林之间的转换

1.树转换为二叉树步骤：

(1)加线。在所有兄弟结点之间加一条连线。
(2)去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
(3)层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子

2.森林转换为二叉树步骤：

(1).把每个树转换为二叉树

(2).第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树

3.二叉树转化为树步骤：

(1).加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

(2).去线。删除原二叉树中所有结点与其右孩子结点的连线。

(3).层次调整。使之结构层次分明

4.二叉树转化为森林步骤：

(1).从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。

(2).再将每棵分离后的二叉树转换为树即可

5.树与森林的遍历

(1)树的遍历分为两种方式

• 一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树
• 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点

(2)森林的遍历也分为两种方式：

• 前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林
• 后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林