觉得文章有帮助的话,麻烦随手留下点赞收藏吧,关注小冷看更多干货学习文章
★ 这里是小冷的博客 ✓ 优质技术好文见专栏 个人公众号,分享一些技术上的文章,以及遇到的坑 当前系列:数据结构系列 源代码 git 仓库 数据结构代码地址 代码Git 仓库地址
从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组,
上图的二叉树的结点,要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 2)
要求在遍历数组 arr 时,仍然可以以前序遍历,中序遍历和后序遍历的方式完成结点的遍历
需求
给你一个数组 {1,2,3,4,5,6,7},要求以二叉树前序遍历的方式进行遍历。
前序遍历的结果应当为 1,2,4,5,3,6,7
编码思路
这里判断的思路首先是有一个数组转变成树看待的思想,
数组 : 1,2,3,4,5,6,7
树 (如下图)
我们可以用这个公式来证明一下,数组转树的正确性
比如我们要计算二的位置,2是1的左子节点,1是下标为0的元素 2*0+1 套用公式 = 1,之后的节点同理
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]);
}
}
这里我们先了解顺序存储二叉树,并且掌握他的节点计算思路和遍历思路,小冷之后的文章堆排序的时候会进行知识点的使用,提前预热