前言
觉得文章有帮助的话，麻烦随手留下点赞收藏吧，关注小冷看更多干货学习文章
★ 这里是小冷的博客 ✓ 优质技术好文见专栏 个人公众号，分享一些技术上的文章，以及遇到的坑 当前系列：数据结构系列 源代码 git 仓库 数据结构代码地址 代码Git 仓库地址
目录
- 前言
- 顺序存储二叉树
- 顺序存储二叉树的概念
- 顺序存储二叉树的特点:
- 顺序存储二叉树遍历
- 代码实现
- 前言
顺序存储二叉树
顺序存储二叉树的概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，
上图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 2) 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
顺序存储二叉树的特点:
- 顺序二叉树通常只考虑完全二叉树
- 第 n 个元素的左子节点为 2 * n 1（计算公式）
- 第 n 个元素的右子节点为 2 * n 2 （计算公式）
- 第 n 个元素的父节点为 (n-1) / 2
- n : 表示二叉树中的第几个元素
顺序存储二叉树遍历
需求
给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。
前序遍历的结果应当为 1,2,4,5,3,6,7
编码思路
这里判断的思路首先是有一个数组转变成树看待的思想，
数组 ： 1,2,3,4,5,6,7
树 （如下图）
- 第 n 个元素的左子节点为 2 * n 1（计算公式）
- 第 n 个元素的右子节点为 2 * n 2 （计算公式）
我们可以用这个公式来证明一下，数组转树的正确性
比如我们要计算二的位置，2是1的左子节点，1是下标为0的元素 2*0 1 套用公式 = 1，之后的节点同理
代码实现
代码语言：javascript复制package com.hyc.DataStructure.tree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.tree
* @className: ArrayTreeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/4 19:07
* @version: 1.0
*/
public class ArrayTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrayTree arrayTree = new ArrayTree(arr);
//452 6731
arrayTree.postOrder(0);
}
}
class ArrayTree {
private int[] arr;
public ArrayTree(int[] arr) {
this.arr = arr;
}
// 顺序存储树的前序遍历
// 遍历公式 找到n的第n个左结点 n*2 1 找到n的第n个右节点 n*2 2
// 输入参数 int index 为开始遍历到根节点 即为 数组下标0
public void preOrder(int index) {
//非空判断 避免空指针
if (arr == null || arr.length == 0) {
System.out.println("该树 为空 不能遍历");
}
// 前序遍历先输出自己
System.out.println(arr[index]);
// 之后递归遍历左结点
//判断index 是否越界
if ((2 * index 1) < arr.length) {
preOrder(index * 2 1);
}
// 之后递归遍历右边结点
//判断index 是否越界
if ((2 * index 2) < arr.length) {
preOrder(index * 2 2);
}
}
public void infixOrder(int index) {
//非空判断 避免空指针
if (arr == null || arr.length == 0) {
System.out.println("该树 为空 不能遍历");
}
// 递归遍历左结点
//判断index 是否越界
if ((2 * index 1) < arr.length) {
infixOrder(index * 2 1);
}
// 中序遍历输出自己
System.out.println(arr[index]);
// 递归遍历右边结点
//判断index 是否越界
if ((2 * index 2) < arr.length) {
infixOrder(index * 2 2);
}
}
public void postOrder(int index) {
//非空判断 避免空指针
if (arr == null || arr.length == 0) {
System.out.println("该树 为空 不能遍历");
}
// 递归遍历左结点
//判断index 是否越界
if ((2 * index 1) < arr.length) {
postOrder(index * 2 1);
}
// 递归遍历右边结点
//判断index 是否越界
if ((2 * index 2) < arr.length) {
postOrder(index * 2 2);
}
// 后序遍历输出自己
System.out.println(arr[index]);
}
}这里我们先了解顺序存储二叉树，并且掌握他的节点计算思路和遍历思路，小冷之后的文章堆排序的时候会进行知识点的使用，提前预热
