一、完全二叉树非常适合顺序存储结构的原因

完全二叉树非常适合顺序存储结构的原因：完全二叉树是一种特殊二叉树，它保证所有叶子节点都在最下层，而且除了最下一层之外，其他层的节点都被填满，如果最下层不满，也必须沿着左侧连续添加节点。

一般情况下，如果将树的结点从上到下，每一层从左到右从1开始挨个编号，那么结点 i 的左孩子就是2i，右孩子就是2i+1，将这个规律反映到顺序存储中。我们可以根据数组的下标i也能找到左孩子（2i）和右孩子（2I+1），前提是数组下标 i=0位丢弃不用，从i=1开始存储树的编号为1的根结点，以此类推。所以，这样即使是将一棵树顺序存储到了一个一维数组中，结点 i 的左孩子就是2i，右孩子就是2i+1这套公式照样能够使用。

顺序存储结构可以用一个一维数组来实现，而完全二叉树的结构固定，数组的大小也是固定的。这种数组的实现方式不需要使用指针等引用类型，因此占用空间更小，访问速度更快。顺序存储的特点是连续的内存块，可以充分利用 CPU 缓存行的特性，减少一次访问需要多次跳跃的情况，因此顺序存储的数组访问速度更快。

运用完全二叉树的结构特点，可以通过下标计算父子节点的位置，大大简化了对树结构的操作。下标的计算公式是：对于节点i，它的左子节点下标为2i，右子节点下标为2i+1，父节点下标为i/2（向下取整），这些计算都可以通过位运算来实现，比加减乘除等运算更快。

由于完全二叉树除了最后一层可能不满，其他所有层都是满的，因此可以确保一个长度为 N 的完全二叉树只需要 2logN 表示。这也意味着在存储一个有 n 个节点的树时，使用数组只需要分配 2n 的空间，但是使用链表需要分配 n 个节点的空间，空间浪费很多。

二、完全二叉树简介

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。如果对满二叉树的结点进行编号，约定编号从根结点起, 自上而下，自左而右。则深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。从满二叉树和完全二叉树的定义可以看出，满二叉树是完全二叉树的特殊形态，即如果一棵二叉树是满二叉树，则它必定是完全二叉树。

完全二叉树代码实现：

#include #include  using namespace std; template struct TreeNode{    T data;    TreeNode *left;    TreeNode *right;    TreeNode(const T &x) : data(x),                           left(NULL),                           right(NULL) {}};template bool IsComplete(TreeNode *root){    //1.树为空，返回错误    if (root == NULL)    {        return false;    }    //2.树不为空    queue *> q;    q.push(root);    while (!q.empty())    {        TreeNode *较好 = q.front();        //2.1如果该节点两个孩子都有，则直接pop        if (较好->left && 较好->right)        {            q.pop();            q.push(较好->left);            q.push(较好->right);        }        //2.2如果该节点左孩子为空，右孩子不为空，则一定不是完全二叉树        if (较好->left == NULL && 较好->right)        {            return false;        }        //2.3如果该节点左孩子不为空，右孩子为空或者该节点为叶子节点，则该节点之后的所有结点都是叶子节点        if ((较好->left && 较好->right == NULL) || (较好->left == NULL && 较好->right == NULL))        {                        if (NULL != 较好->left && NULL == 较好->right)                         {                            q.push(较好->left);                            }            q.pop(); //则该节点之后的所有结点都是叶子节点            while (!q.empty())            {                较好 = q.front();                if (较好->left == NULL && 较好->right == NULL)                {                    q.pop();                }                else                {                    return false;                }            }            return true;        }    }    return true;} //满二叉树void test1(){    //       1    //   2       3    // 4    5  6   7    TreeNode *node1 = new TreeNode(1);    TreeNode *node2 = new TreeNode(2);    TreeNode *node3 = new TreeNode(3);    TreeNode *node4 = new TreeNode(4);    TreeNode *node5 = new TreeNode(5);    TreeNode *node6 = new TreeNode(6);    TreeNode *node7 = new TreeNode(7);    node1->left = node2;    node1->right = node3;    node2->left = node4;    node2->right = node5;    node3->left = node6;    node3->right = node7;    cout << IsComplete(node1) << endl;} //二叉树为空void test2(){    cout << IsComplete(NULL) << endl;} //3.二叉树不为空，也不是满二叉树，遇到一个结点左孩子为空，右孩子不为空void test3(){    //       1    //   2       3    // 4    5      7    TreeNode *node1 = new TreeNode(1);    TreeNode *node2 = new TreeNode(2);    TreeNode *node3 = new TreeNode(3);    TreeNode *node4 = new TreeNode(4);    TreeNode *node5 = new TreeNode(5);    TreeNode *node7 = new TreeNode(7);    node1->left = node2;    node1->right = node3;    node2->left = node4;    node2->right = node5;    node3->right = node7;    cout << IsComplete(node1) << endl;} //4.二叉树不为空，也不是满二叉树，遇到叶子节点,则该叶子节点之后的所有结点都为叶子节点void test4(){    //        1    //    2       3    // 4    5    TreeNode *node1 = new TreeNode(1);    TreeNode *node2 = new TreeNode(2);    TreeNode *node3 = new TreeNode(3);    TreeNode *node4 = new TreeNode(4);    TreeNode *node5 = new TreeNode(5);    node1->left = node2;    node1->right = node3;    node2->left = node4;    node2->right = node5;    cout << IsComplete(node1) << endl;} //4.二叉树不为空，也不是满二叉树，遇到左孩子不为空，右孩子为空的结点，则该节点之后的所有结点都为叶子节点void test5(){    //        1    //    2       3    // 4    5   6    TreeNode *node1 = new TreeNode(1);    TreeNode *node2 = new TreeNode(2);    TreeNode *node3 = new TreeNode(3);    TreeNode *node4 = new TreeNode(4);    TreeNode *node5 = new TreeNode(5);    TreeNode *node6 = new TreeNode(6);    node1->left = node2;    node1->right = node3;    node2->left = node4;    node2->right = node5;    node3->left = node6;    cout << IsComplete(node1) << endl;} int main(){    test1();    /*test2();*/    /*test3();*/    /*test4();*/    /*test5();*/    return 0;}

三、二叉树简介

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点非常多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

二叉树的特殊类型：

延伸阅读1：二叉树的性质

上一篇

为什么用于动态分配的内存区段会叫堆?

下一篇

软件测试和硬件测试的区别?