C++csp-J初赛4

动态数组是一种基于数组的数据结构，也是序列容器，它可以在运行时动态地插入和删除元素和管理空间，可随机访问，不可在中间插入，也比数组具有更多的灵活性和功能。

链表是一个线性数据结构，可在内存中随机分布，一个存储单元分为值和指针，还有head和end，不可随机访问，可动态调整大小，遍历为：for(auto pos:list名称),pos为这一项的值，还可以排序，可在中间插入。

队列是一种先进先出的数据结构，首先插入的元素将首先被提取，依此类推。有一个称为“前”的元素，它是位于最前位置或位于第一个位置的元素，也有一个名为“后”的元素，它是位于最后位置的元素。在普通队列中，元素的插入在尾部，而删除则从前面开始。

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

树是一种非常重要的数据结构，它是由节点和边组成的，每个节点可以有多个子节点，但只有一个父节点，除了根节点外。树结构在算法和数据处理中有着广泛的应用，如二叉树、二叉搜索树、哈夫曼树等。

在二叉树的第$i$层上最多有2^(i-1)个结点$(i ≥1)$

深度为$k$的二叉树最多有$2^k−1$个结点

有中序和另外任意一种序才能组成二叉树

前序：中左右
中序：左中右
后序：左右中
层次：按层次从小到大逐个访问，同一层按从左到右逐个访问
叶结点遍历：从左到右依次访问叶子结点

过程：1.找根节点 2.在中序中找根节点，确定其左边的值和右边的值 3.重复前述步骤

构造哈夫曼树的步骤如下：

1 初始化森林：将给定的n个权值分别作为n棵只有一个结点的树。

2 选择最小权值结点：在森林中选取两个权值最小的树作为左右子树，构造一棵新的二叉树，并将新树的权值设为左右子树权值之和。

3 更新森林：删除选取的两棵树，并将新树加入森林。

4 重复步骤2和3：直到森林中只剩下一棵树，这棵树即为哈夫曼树。

哈夫曼树带权路径长度：带权路径长度是指树中所有叶子节点的权值与其到根节点路径长度乘积之和