乐趣区

关于java:我所知道的数据结构之顺序存储二叉树

jiezi

前一篇咱们学数据结构：树，那么这一篇学习的是的：顺序存储二叉树

一、什么是顺序存储二叉树

首先先来看看概念:什么是顺序存储二叉树

从数据存储来看：[数组]存储形式 和[树]的存储形式 能够 相互转换，即是数组能够转换为树、树也能够转换为数组

依据这样的个性就会发现一些特点

顺序存储通常思考齐全二叉树！那么 什么是齐全二叉树呢？

二、什么是齐全二叉树

咱们首先回顾一下 什么是二叉树

简略地了解，满足以下两个条件的树就是二叉树：

  1. 自身是有序树；
  2. 树中蕴含的各个节点的度不能超过 2，即只能是 0、1 或者 2

上一篇文章咱们提到在二叉树中，还有两个非凡的类型：满二叉树与齐全二叉树。

[满二叉树]：除了叶子节点外，所有节点都有两个节点。

[齐全二叉树]：除了最初一层以外，其余层节点个数都达到最大，并且最初一层的叶子节点向左排列

三、通过示例意识顺序存储二叉树

示例一：数组 arr{1,2,3,4,5,6,7}，要求 以二叉树前序遍历 进行遍历，遍历后果为1,2,4,5,3,6,7

咱们定义顺序存储二叉树：ArrBinaryTree

// 定义顺序存储二叉树
class ArrBinaryTree{private int[] arr;// 存储数据结点的数组

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

    public void preOrder(){this.preOrder(0);
    }

    /**
     * 编写二叉树前序遍历办法
     * 二叉树前序遍历：先输入父节点，再遍历左子树和右子树
     * 第 n 个元素的左节点为 2 * n + 1
     * 第 n 个元素的右节点为 2 * n + 2
     */
    private void preOrder(int index){
        // 判断数组是否为空
        if(arr == null || arr.length == 0){System.out.println("数组为空，不能进行二叉树前序遍历");
            return;
        }
        // 输入以后元素
        System.out.println(arr[index]);

        // 左递归 避免数组越界
        if((2 * index + 1) < arr.length){preOrder((2 * index + 1));
        }

        // 右递归 避免数组越界
        if((2 * index + 2) < arr.length){preOrder((2 * index + 2));
        }

    }
}

咱们进行应用 [ 二叉树前序遍历 ] 看看是否输入{1,2,4,5,3,6,7}

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

        // 创立一个顺序存储二叉树
        ArrBinaryTree arrTree = new ArrBinaryTree(arr);
        arrTree.preOrder();}
}

// 运行后果如下：//1 2 4 5 3 6 7

增强练习

联合前一篇文章，依据中序、后序的规定实现对数组进行二叉树中序、后续遍历的形式代码编写

四、顺序存储二叉树利用实例

八大排序算法中的堆排序、就会应用到顺序存储二叉树，对于堆排序会放在前面的文章中进行解说与分享。

退出移动版