数据结构——二叉树的存储结构（Java实现）

二叉树的定义

二叉树（Binary Tree）是n(n≥0)个结点的有限集合，该集合或者为空集，或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。

二叉树的定义也采用了递归，听起来有些绕，如果了解了树的结构的话，二叉树也可以定义为：

二叉树是每个结点最多只有两个分支的树结构。

下列图中均为二叉树：

              

注意：

• 二叉树是不存在度大于2的结点，不是只有两棵子树，0、1、2棵子树都是可以的。
• 左子树和右子树是有顺序的，次序不能颠倒。即时某个结点只有一颗子树，也要区分左子树还是右子树

二叉树的类型

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树。如下图

满二叉树的特点有：

1. 叶子只能出现在最下一层。
2. 非叶子结点的度一定是2。
3. 在同样深度的二叉树中，满二叉树的结点个人最多，叶子树最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1≤≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。如下图：

这个特殊二叉树可能有些难理解，首先满二叉树一定是一棵完全二叉树，但是完全二叉树不一定是满二叉树。后序看完二叉树的层序遍历，可能就比较好理解了。

二叉树的存储结构

二叉树的顺序存储结构

二叉树的顺序存储结构是用一个数组来存储二叉树中的结点，根据二叉树的特性，结点的存储位置可以反映结点之间的逻辑关系。

我们先来看完全二叉树的顺序存储结构：

如上图，将这棵二叉树存入在一维数组中，相应的下标对应其同样的位置。

那么对于不是完全二叉树的表示方法呢？我们再来看一般二叉树的顺序存储结构：

其实对于一般二叉树来说，还是按照层序遍历把结点存储在一维数组中，只是在没有结点的位置用一个特殊的占位符来标识，图中用的"#"，实际编码中也可以直接用null。注意图中没有结点的位置用了半透明的结点来填充，便于理解。

顺序存储结构的优缺点

二叉树的顺序存储结构比较直观，通过观察数组就可以很清晰的看出二叉树的轮廓，由于每一个结点的位置都是按照完全二叉树的层序遍历来排列的，所以可以利用完全二叉树的特性来操作二叉树。

1. 读取左/右子树：假设数组的长度为n，结点的序号为i(i > 1), 如果序号为2i处的值不为"#", 则序号2i为序号i的左子树；如果序号为2i+1处的值不为"#"，则序号2i+1为序号i的右子树。（同样的，我们可以用这一特性来判断某一个结点是否有左/右子树）。
2. 对于任意结点序号i (i > 1), 它的双亲结点的序号为i / 2。
3. 对于任意结点序号i (i > 1), 它所在的层数为log2(i) + 1。

基于以上这些特性，我们在对二叉树做插入删除操作时，就很直观。

但是顺序存储有一个常见的缺点——存储空间的浪费，上述的二叉树基本都接近完全二叉树，数组中为空的结点较少，所以看不出来，我们看下面这个二叉树。

这个二叉树，结点数为5，但是却占用了长度为15的数组，也就是说有10个存储单位是占位符，被浪费掉了。所以二叉树的顺序存储一般只适合完全二叉树，或者某些特殊情况。

二叉树的链式存储结构

既然顺序存储可能会造成空间的浪费，那么我来考虑链式存储结构，二叉树每个结点包含一个元素和两个指向孩子的指针。所以我们可以这么设计：

public class BiNode {

    public String data;

    public BiNode leftChild;

    public BiNode rightChild;
}

具体的结构如下图：

链式存储的优点是节省空间，遍历（以后的文章会讲到）方便。而当我们需要查找某一个结点时，就会比较繁琐，因为有可能需要遍历整个二叉树的结构，才能完成查找。

对此，如果我们能在顺序存储和链式存储之间转换的话，就可以解决大多数的问题了。

顺序存储转链式存储算法如下：

/**
     * 将二叉树的顺序存储结构转换为链式存储结构
     * @param nodes 顺序存储结构数组
     * @return
     */
    public static final BiTree convertFromArray(String[] nodes) {

        BiNode root = new BiNode();

        root.data = nodes[1];

        createBiTreeNode(root, nodes, 1);
        return new BiTree(root);
    }


    private static BiNode createBiTreeNode(BiNode root, String[] nodes, int position) {

        if (position * 2 >= nodes.length) {
            return root;
        }

        if (!TextUtils.isEmpty(nodes[position * 2])) {
            BiNode leftChild = new BiNode();
            leftChild.data = nodes[position * 2];
            root.leftChild = leftChild;
            createBiTreeNode(root.leftChild, nodes, position * 2);
        }

        if (!TextUtils.isEmpty(nodes[position * 2 + 1])) {
            BiNode rightChild = new BiNode();
            rightChild.data = nodes[position * 2 + 1];
            root.rightChild = rightChild;
            createBiTreeNode(root.rightChild, nodes, position * 2 + 1);
        }
        return root;
    }

算法分析：

1. 首先找到根结点nodes[1]，设置为链式结构的root；
2. 根据完全二叉树的特性，对于任意一个结点i，它的左孩子和2i，右孩子为2i+1； 所以从根结点开始递归的访问它的左孩子（2i结点），直到左孩子不存在；然后再递归的访问它的右孩子（2i+1结点），直到右孩子不存在。
3. 整个递归访问过程结束后，二叉树数组结构就转换为链式结构了。

————————————————————————————————————

文末推荐个人开发的app，Google Play : 数据结构与算法教程 （需要*）

    

提供了丰富的动画演示、模拟场景来帮助你更好的理解抽象的数据结构和复杂的算法。（文中的动图都是从app中截取的片段）