顺序存储二叉树
顺序存储二叉树的概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，
上图的二叉树的结点，要求以数组的方式来存放 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，之后的节点同理
代码实现
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]); } }
这里我们先了解顺序存储二叉树，并且掌握他的节点计算思路和遍历思路
