【数据结构与算法】顺序储存二叉树的介绍和程序实现

1. 顺序储存二叉树的介绍

从数据储存来看，顺序储存二叉树的底层是用数组来储存数据的，如下图所示：

而遍历顺序储存二叉树，仍然可以以前序遍历、中序遍历、后序遍历的方式进行遍历

顺序存储二叉树的特点：

• 顺序储存二叉树通常只考虑完全二叉树
• 第n个元素的左子节点为 2 ∗ n + 1 2 * n + 1 2∗n+1。其中n为index
• 第n个元素的右子节点为 2 ∗ n + 2 2 * n + 2 2∗n+2
• 第n个元素的父节点为 ( n − 1 ) / 2 (n-1) / 2 (n−1)/2

顺序存储二叉树应用实例： 八大排序算法中的堆排序，就会使用到顺序存储二叉树。堆排序的应用参考地址

2. 顺序储存二叉树的程序实现

public class ArrayBinaryTreeDemo {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        // 创建一个ArrayBinaryTree
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
        arrayBinaryTree.preOrder();
    }

}

// ArrayBinaryTree实现
class ArrayBinaryTree {
    // 用数据保存ArrayBinaryTree的数据
    private int[] array;

    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }

    // 重载preOrder
    public void preOrder() {
        this.preOrder(0);
    }

    // 顺序存储二叉树的前序遍历实现。参数为数组的下标
    public void preOrder(int index) {
        // 如果数组为空，或者array.length = 0，则不能遍历
        if (array == null || array.length == 0) {
            System.out.println("数组为空，不能完成顺序储存二叉树的前序遍历");
        }

        // 输出当前元素
        System.out.println(array[index]);

        // 向左递归遍历
        if ((index * 2 + 1) < array.length) {
            preOrder(2 * index + 1);
        }

        // 向右递归遍历
        if ((index * 2 + 2) < array.length) {
            preOrder(2 * index + 2);
        }
    }

}

运行程序，结果如下：

1
2
4
5
3
6
7