作者：解学武

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。对的，你没有看错，虽然树是非线性存储结构，但也可以用顺序表存储。

需要注意的是，顺序存储只适用于完全二叉树。对于普通的二叉树，必须先将其转化为完全二叉树，才能存储到顺序表中。

满二叉树也是完全二叉树，可以直接用顺序表存储。

一棵普通二叉树转化为完全二叉树的方法很简单，只需要给二叉树额外添加一些结点，就可以把它"拼凑"成完全二叉树。如图 1 所示：
图 1 左侧是普通二叉树，右侧是转化后的完全（满）二叉树。解决了二叉树的转化问题，接下来学习如何顺序存储完全（满）二叉树。

所谓顺序存储完全二叉树，就是从树的根结点开始，按照层次将树中的结点逐个存储到数组中。

例如存储图 2 中的完全二叉树，各个结点在顺序表中的存储状态如图 3 所示：

 

存储由普通二叉树转化来的完全二叉树也是如此，比如将图 1 中的普通二叉树存储到顺序表中，树中结点的存储状态如图 4 所示：

由此就实现了完全二叉树的顺序存储。

二叉树的顺序存储结构用 C 语言表示为：

#define NODENUM 7  //二叉树中的结点数量
#define ElemType int //结点值的类型
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[MaxSize];

下面是用 BiTree 存储图 1 中二叉树的 C 语言代码：

#include <stdio.h>
#define NODENUM 7
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];

//存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}
//查找某个结点的双亲结点的值
ElemType Parent(BiTree T, ElemType e) {
    int i;
    if (T[0] == 0) {
        printf("存储的是一棵空树\n");
    }
    else
    {
        if (T[0] == e) {
            printf("当前结点是根节点，没有双亲结点\n");
            return 0;
        }
        for (i = 1; i < NODENUM; i++) {
            if (T[i] == e) {
                //借助各个结点的标号(数组下标+1)，找到双亲结点的存储位置
                return T[(i + 1) / 2 - 1];
            }
        }
        printf("二叉树中没有指定结点\n");
    }
    return -1;
}

//查找某个结点的左孩子结点的值
ElemType LeftChild(BiTree T, ElemType e) {
    int i;
    if (T[0] == 0) {
        printf("存储的是一棵空树\n");
    }
    else
    {
        for (i = 1; i < NODENUM; i++) {
            if (T[i] == e) {
                //借助各个结点的标号(数组下标+1)，找到左孩子结点的存储位置
                if (((i + 1) * 2 < NODENUM) && (T[(i + 1) * 2 - 1] != 0)) {
                    return T[(i + 1) * 2 - 1];
                }
                else
                {
                    printf("当前结点没有左孩子\n");
                    return 0;
                }
            }
        }
        printf("二叉树中没有指定结点\n");
    }
    return -1;
}

//查找某个结点的右孩子结点的值
ElemType RightChild(BiTree T, ElemType e) {
    int i;
    if (T[0] == 0) {
        printf("存储的是一棵空树\n");
    }
    else
    {
        for (i = 1; i < NODENUM; i++) {
            if (T[i] == e) {
                //借助各个结点的标号(数组下标+1)，找到左孩子结点的存储位置
                if (((i + 1) * 2 + 1 < NODENUM) && (T[(i + 1) * 2] != 0)) {
                    return T[(i + 1) * 2];
                }
                else
                {
                    printf("当前结点没有右孩子\n");
                    return 0;
                }
            }
        }
        printf("二叉树中没有指定结点\n");
    }
    return -1;
}

int main() {
    int res;
    BiTree T = { 0 };
    InitBiTree(T);

    res = Parent(T, 3);
    if (res != 0 && res != -1) {
        printf("结点3的双亲结点的值为 %d\n", res);
    }

    res = LeftChild(T, 2);
    if (res != 0 && res != -1) {
        printf("结点2的左孩子的值为 %d\n", res);
    }

    res = RightChild(T, 2);
    if (res != 0 && res != -1) {
        printf("结点2的右孩子的值为 %d\n", res);
    }
    return 0;
}

执行结果是：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 0 3 #
结点3的双亲结点的值为 2
结点2的左孩子的值为 3
当前结点没有右孩子

程序中实现查找某个结点的双亲结点和孩子结点，用到了完全二叉树具有的性质：将树中节点按照层次并从左到右依次标号 1、2、3、...（程序中用数组下标+1 表示），若节点 i 有左右孩子，则其左孩子节点的标号为 2*i，右孩子节点的标号为 2*i+1。

总结

虽然二叉树是非线性存储结构，但也可以存储到顺序表中。

顺序表只能存储完全二叉树，普通的二叉树必须先转化为完全二叉树之后才能用顺序表存储。

实际场景中，并非每个二叉树都是完全二叉树，用顺序表存储普通二叉树或多或少存在空间浪费的情况。