一、背景

由于vector是顺序存储结构，所以如果发生了扩容，需要重新申请一块更大的连续内存空间，并将原数据复制过去，所以存储地址有可能发生变化。顺序表相邻（逻辑地址相邻）的两个节点，在内存中具有相邻的物理地址。线性表存储的数据是依次排列的，具有一对一的相连方式。链表相邻（逻辑地址相邻）的两个节点，在内存中的物理地址不一定相同。的对应关系的数据存储结构。如下图所示是我们比较常用的二叉树结构，二叉树具有1对2

完全二叉树是这样定义的：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）上面的定义看起来比较复杂。所有节点只存在3种情况：1、有左右2个孩子；2、只有左孩子；3、没有孩子（叶节点），即不存在只有右孩子的情况；我们采用层序遍历的方式遍历节点，当遍历到某一个节点，它只有左孩子

标识符可以理解为一个名字。主要用来标识变量、函数、类、模块和其他对象的名称。

先遍历根（父）节点、再遍历左节点、最后遍历右节点。注意这里说的遍历并不是行走。毕竟我们能够先取到的指针只有根节点指针，而如果想找一个节点，则一定要先找到它的根节点。这里的遍历指的是“介绍”这棵树的方式。通常来讲，我们是使用的打印的方式“介绍”一棵树的。所以，先序遍历展开来讲是如果一棵树上有根节点，则先输出根节点，再输出左孩子节点、最后输出右孩子节点。例如，上述图1中的二叉树，先序遍历输出是先遍历输