更前面的知识：树的概念
先来说说前面的芝士：

• 路径长度 从根结点到目标结点经过的结点数量（边的数量）。
• 权值 一个结点的权值可以是人为赋予的一个数。
• 结点的带权路径长度 从根节点到当前结点的路径长度乘结点的权值。
• 树的带权路径长度 整个树中叶子结点的带权路径长度总和。

哈夫曼树是二叉树，且哈夫曼树的带权路径长度最小，哈夫曼编码会用到。

二叉树的前序遍历中序遍历和后序遍历是比较重要的CCF办的比赛要考（雾。可以通过这三个遍历的顺序结果确定整个树的结构。前序遍历是根左右，中序遍历是左根右，后序遍历是左右根。（不想多写什么了）

队列和栈都是线性数据结构，它们一个是先进先出，一个是先进后出，有着不同的使用场景。这两个数据结构基于链表，也可以用数组模拟这样的数据结构，通过 C++ 中 STL 提供的容器也可以更加方便快捷地实现。

队列

队列 (queue) 是在一端插入另一段删除的线性表，遵循先进先出，类似于排队，可以称为先进先出 (FIFO) 表。队列中，允许入队 (enqueue) 的一端为队尾，允许出队 (dequeue) 的一端为队头。以后的广度优先搜索就会用到它。

这不，刚学完深搜没多久，又来写广搜笔记了（话说我队列笔记还没来得急写呢）。广度优先搜索，广搜，英文为Breadth First Search，简称 BFS。是从一个结点向其他方向的结点不断扩散，如同一道水晕在湖面上荡漾开来。主要可以用来找路径权值一定的最短路径。
深搜可以用到队列先进先出的特性。当一个结点准备扩散时，即弹出队列，再将接下来扩散到结点加入队列。随后按照队首扩散、弹出，不断循环。这也是叫它广度优先搜索的原因。

树也是一种数据结构，它是非线性数据结构，它能很好地描述一个数据集合中的分支和层次，是一个比较重要的课题，以后的搜索和竞赛都有可能要用到它。树形结构的应用非常广泛，什么索引、语法结构。虽说概念比较繁琐 老师讲了一个小时。有点让人头疼（我咕了好多篇笔记了）。

树的概念

前面

前置芝士，简单说一下这些奇怪的名称：

• 树中的每一个元素称为结点 node。
• 两个结点之间的线称为边 edge。
• 通过几条边，这几条边组成路径。