完全二叉树为什么最适合顺序存储结构?
顺序存储充分利用满二叉树的特性，即每层的节点数分别为1、2、4、8等等2i+1，一个深度为i的二叉树最多只能包含2i-1个节点，因此只要定义一个长度为2i-1的数组即可存储这颗二叉树。 对于普通的不是满二叉树的，那些空出来的节点对应的数组元素留空即可，因此顺序存储会造成一定的空间浪费。如果是完全二叉树，就不会有空间浪费的情况；若是只有右子树，那么会造成相当大的浪费。 二叉树算法思路： 1、如果树为空，则直接返回错。 2、如果树不为空：层序遍历二叉树。 3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。 4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。 5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
二叉树_顺序存储
满二叉树 (Full Binary Tree) 所有分支结点都有存在左子树和右子树，并且所有叶子结点都在同一层上。 完全二叉树 (Complete Binary Tree) 如果一棵具有n个结点的二叉树与满二叉树的前n个结点的结构相同，则称这棵二叉树为完全二叉树。 重要性质 ： 对于一棵有n个结点的 完全二叉树 的结点按照从上至下和从左至右的顺序对所有结点从零开始到 n-1 进行顺序编号，则对于序号为i的结点(0≤i≤n),有： (1)如果 i=0，则结点i是二叉树的根；如果i>0，则其 双亲 是结点 (i-1)/2 （整除）。 (2)如果2i+1≥n，则结点i无左孩子；否则，其 左孩子 是结点 2i+1 。 (3)如果2i＋2≥n，则结点i无右孩子；否则，其 右孩子 是结点 2i＋2 。 根据上面两点，得到二叉树顺序存储的实现： 定义： 获取双亲节点下标： 左子节点下标： 右子节点下标： 主函数测试： 总结： 1、对于完全二叉树或接近于完全的二叉树，用顺序存储可以省空间简化操作；否则，都不适宜用顺序存储。 2、顺序存储结构通病：必须预先给出数组的存储空间大小MaxSize。