顺序存储二叉树_数据结构

文章目录

- 顺序存储二叉树：
- 代码实现

顺序存储二叉树：

二叉树的顺序存储结构是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系
考虑对存储空间的浪费，顺序存储结构一般只适用于完全二叉树
关系：
3.1 第n个元素的左子结点为 2 * n + 1
3.2第n个元素的右子结点为 2 * n + 2
3.3第n个元素的父节点为（n-1）/ 2
3.4n:表示二叉树中的第几个元素（按0开始编号）
应用：八大排序算法中的堆排序中会使用到顺序存储二叉树

代码实现

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();

    }
}