Java数据结构-顺序存储二叉树(光头强带你去砍树)

        上次讲完了二叉树,这次就将一个特别的数据结构,顺序存储二叉树,顺序存储二叉树是啥,是二叉树?是数组?是链表?还是哈希表????欸,现在先不告诉你,等等再告诉你,让你着急, 嘿嘿/

        我们将会从以下几点开始阐述:

        顺序存储二叉树的概述  顺序存储二叉树的创建思想  顺序存储二叉树的代码实现与分析  顺序存储二叉树的应用与展望  结论

        如果喜欢博主的话,戳这关注我哦!

        精彩频道:

                SQL的DBMS区  Java的数据结构区 Java的数据结构区  SE的基础知识点区

        往期精彩:

               二叉树的实现

        顺序存储二叉树这种数据结构其实是数组,没错,线索化二叉树是一个数组,不过该数组的遍历方法和删改方法都按照二叉树的思想去完成,这就称为我们的顺序存储二叉树!

        顺序存储二叉树本质上阐述了数组和二叉树这两种数据结构是可以相互转换的

满二叉树:

如果所有的叶子节点都在最后一层,而且节点总是等于2^n-1(n代表树高) ,我们称为满二叉树完全二叉树

如果所有的叶子节点都在倒数第一层和倒数第二层,且左子树的叶子节点在倒数第一层连续,右子树的叶子节点在倒数第二层连续,我们称为完全二叉树注意:连续的意思是相邻两个节点在同一条直线上,突出或者凹进去就不算连续 顺序存储二叉树的节点知识‍️

顺序存储二叉树的节点编号从0开始(数组下标从0开始而决定) 第N个元素的左子节点是2N+1(N表示下标)第N个元素的右子节点是2N+2(N表示下标)第N个元素的父节点是(N-1)/2

 创建一个顺序存储二叉树类,里面应该有数组属性,并提供对应的构造方法 创建里面对应的方法 注意的是:顺序存储二叉树我们理解起来一定要把他当作是一个二叉树去对待,不要把他当成 数组去对待

public class BinaryTreeArrays {
    public int[] arrays;

    public BinaryTreeArrays(int[] arrays) {
        this.arrays = arrays;
    }
}

里面先创建一个数组属性,用于为顺序存储二叉树提供数据结构的支持创建对应的构造方法,初始化数组属性 

public void prefixPrint() {
        prefixPrint(0);
    }
public void prefixPrint(int index) {
        if (arrays == null || arrays.length == 0) {
            System.out.println("顺序存储二叉树没有元素");
            return;
        }
        System.out.println(arrays[index]);
        if ((2*index+1) < arrays.length) {
            prefixPrint(2*index+1);
        }
        if ((2*index+2) < arrays.length) {
            prefixPrint(2*index+2);
        }
    }

index对应着思路中的N,表示着第几个元素的下标在遍历之前,我们要先判断一下该数组引用是否为空,或者该数组是否没有元素,若符合两种情况,则直接退出(校验意识)根据二叉树前序遍历的思想,我们要先输出当前节点,即sout(array[index])根据左子节点是2N+1,则先判断一下是否下标越界(避免越界异常,更是符合了二叉树不会遍历空节点),如果不是越界则递归进入左子树根据右节点是2N+2,同上 注意的是:因为遍历二叉树是从根节点开始的,而0就是代表的根节点,所以每次都要输入0,不方便,如引入方法重载机制

 public void infixPrint() {
        infixPrint(0);
    }

    public void suffixPrint() {
        suffixPrint(0);
    }
public void infixPrint(int index) {
        if (arrays == null || arrays.length == 0) {
            System.out.println("顺序存储二叉树没有元素");
            return;
        }
        if ((2*index+1) < arrays.length) {
            prefixPrint(2*index+1);
        }
        System.out.println(arrays[index]);
        if ((2*index+2) < arrays.length) {
            prefixPrint(2*index+2);
        }
    }

    public void suffixPrint(int index) {
        if (arrays == null || arrays.length == 0) {
            System.out.println("顺序存储二叉树没有元素");
            return;
        }
        if ((2*index+1) < arrays.length) {
            suffixPrint(2*index+1);
        }
        if ((2*index+2) < arrays.length) {
            suffixPrint(2*index+2);
        }
        System.out.println(arrays[index]);
    }

        略~~~ 

        哎呀小伙伴可能会问了,这啥呀这是,这么简单,这不没用,其实不然,顺序存储二叉树引出了一个非常重要的算法,这个算法就是堆排序,就是那个八大排序算法的最后一个,这篇博客先不阐述,下篇博客再给大家带来精彩的堆排序

        虽说顺序存储二叉树篇幅很短,也较容易理解,但是他短小而精悍,为后续的堆排序立下了基础,最后,我来总结一下必须掌握的几点

        1.各个节点对应的下标如何

        2.用何种思想思考该数据结构

        下一站:线索化二叉树