顺序存储二叉树详解

顺序存储二叉树详解

说明

1. 顺序存储二叉树，即将一颗完全二叉树按照从上到下，从左到右的顺序存储到一个数组中，因为数组是顺序存储的结构，因此称为顺序存储二叉树
2. 给二叉树中各节点用 n 编号，从零开始，一直到最后 一个节点，对应于数组位置
3. 假设当前节点的编号为 n ,那么当前节点的左子节点编号为 2 * n + 1,右子节点编号为 2 * n + 2,同样也对应于数组中的位置
4. 因此将二叉树存储于数组后，可以按照左右子节点位置顺序实现前序中序后续遍历
5. 即用 n 代表当前元素索引，2 * n + 1代表当前元素的左子节点索引， 2 * n + 2 代表当前元素的右子节点索引
6. 因此可以使用递归对数组实现前序中序后续遍历，类似前序中序后续遍历一颗二叉树
7. 注意顺序存储二叉树一般是对完全二叉树而言
8. 源码见下

源码及分析

class ArrBinaryTree {

    private int[] arr;

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

    //后续重载
    public void postOrder(){
        this.postOrder(0);
    }

    //顺序存储二叉树后序遍历
    public void postOrder(int index) {
        //判断数组的合法性
        if (arr == null || arr.length == 0) {
            return;
        }
        //向左递归
        if (index * 2 + 1 < arr.length) {
            this.postOrder(index * 2 + 1);
        }
        //向右递归
        if (index * 2 + 2 < arr.length) {
            this.postOrder(index * 2 + 2);
        }
        //输出当前节点信息
        System.out.println(arr[index]);
    }

    //中序遍历重载
    public void infixOrder(){
        this.infixOrder(0);
    }
    //顺序存储二叉树中序遍历
    public void infixOrder(int index) {
        //判断数组的合法性
        if (arr == null || arr.length == 0) {
            return;
        }
        //向左递归
        if (index * 2 + 1 < arr.length) {
            this.infixOrder(index * 2 + 1);
        }
        //输出当前节点信息
        System.out.println(arr[index]);
        //向右递归
        if (index * 2 + 2 < arr.length) {
            this.infixOrder(index * 2 + 2);
        }
    }

    //顺序存储二叉树前序遍历
    public void preOrder(int index) {
        //判断数组的合法性
        if (arr == null || arr.length == 0) {
            return;
        }
        //输出当前节点信息
        System.out.println(arr[index]);
        //向左递归
        if (index * 2 + 1 < arr.length) {
            this.preOrder(index * 2 + 1);
        }
        //向右递归
        if (index * 2 + 2 < arr.length) {
            this.preOrder(index * 2 + 2);
        }
    }

    //因为index默认从0开始，因此可以重载此方法
    public void preOrder(){
        this.preOrder(0);
    }
}

顺序存储二叉树详解

原文：https://www.cnblogs.com/mx-info/p/14855772.html