顺序存储二叉树

顺序存储二叉树：

1. 二叉树的顺序存储结构是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系

2. 考虑对存储空间的浪费，顺序存储结构一般只适用于完全二叉树

3. 关系：
   3.1 第n个元素的左子结点为 2 * n 1
   3.2第n个元素的右子结点为 2 * n 2
   3.3第n个元素的父节点为 （n-1）/ 2
   3.4n:表示二叉树中的第几个元素（按0开始编号）

4. 应用：八大排序算法中的堆排序中会使用到顺序存储二叉树

代码实现

public class ArrBinaryTreeDemo {
    int[] arr;

    public ArrBinaryTreeDemo(int[] arr) {
        this.arr = arr;
    }

    /**
     * 方法重载preOrder,这样就不要反复输入0
     */
    public void preOrder(){
        this.preOrder(0);
    }

    /**
     * 完成对顺序存储二叉树的前序遍历
     * @param index 数组下标
     */
    public void preOrder(int index){
        //前序遍历应该先输出根节点,之后再进行递归
        System.out.println(arr[index]);
        //左，注意只要涉及到数组的index，都要进行判断是否越界。否则很容易出现index out of bounds exception
        if ((index * 2   1) < arr.length){
            this.preOrder(2 * index   1); //输入了这个数组下标，就要判断这个下标是否越界
        }
        //右
        if ((index*2 2) < arr.length){
            this.preOrder(2 * index   2);
        }

    }
    /**
     * 完成对顺序存储二叉树的中序遍历
     * @param index 数组下标
     */
    public void infixOrder(int index){

        //左，注意只要涉及到数组的index，都要进行判断是否越界。否则很容易出现index out of bounds exception
        if ((index * 2   1) < arr.length){
            this.preOrder(2 * index   1); //输入了这个数组下标，就要判断这个下标是否越界
        }
        //根
        System.out.println(arr[index]);

        //右
        if ((index*2 2) < arr.length){
            this.preOrder(2 * index   2);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        ArrBinaryTreeDemo arrBinaryTreeDemo = new ArrBinaryTreeDemo(arr);
        arrBinaryTreeDemo.preOrder();

    }
}

这篇好文章是转载于：学新通技术网