顺序存储二叉树
1. 介绍
- 从数据存储来看,数组的存储方式和树的存储方式是可以互相转换的,即数组可以转换成树,树也可以转换成数组;
- 遍历数组arr时,仍然可以以前序遍历、中序遍历、后序遍历的方式得到二叉树。
2. 顺序存储二叉树的特点
- 顺序存储二叉树通常只考虑完全二叉树;
- 下标为i的元素的左子节点为:2 × i + 1;
- 下标为i的元素的右子节点为:2 × i + 2;
- 下标为i的元素的父节点为:(n - 1) / 2
3. 代码实现顺序存储二叉树的前、中、后序遍历
package com.datastructure;
import java.util.ArrayList;
import java.util.List;
/**
* @author SnkrGao
* @create 2023-05-09 10:51
*/
public class ArrayBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
System.out.println("前序遍历:");
System.out.println(arrayBinaryTree.preorderTraversal());
System.out.println("中序遍历:");
System.out.println(arrayBinaryTree.inorderTraversal());
System.out.println("后序遍历:");
System.out.println(arrayBinaryTree.postorderTraversal());
}
}
class ArrayBinaryTree {
private int[] arr; // 用于存储数据
public ArrayBinaryTree(int[] arr) {
this.arr = arr;
}
// 重载preorderTraversal,方便调用
public List<Integer> preorderTraversal() {
if (arr.length == 0) {
System.out.println("数组为空,无法遍历二叉树!");
return new ArrayList<>();
}
List<Integer> resList = new ArrayList<>();
preorderTraversal(0, resList);
return resList;
}
// 重载inorderTraversal,方便调用
public List<Integer> inorderTraversal() {
if (arr.length == 0) {
System.out.println("数组为空,无法遍历二叉树!");
return new ArrayList<>();
}
List<Integer> resList = new ArrayList<>();
inorderTraversal(0, resList);
return resList;
}
// 重载postorderTraversal,方便调用
public List<Integer> postorderTraversal() {
if (arr.length == 0) {
System.out.println("数组为空,无法遍历二叉树!");
return new ArrayList<>();
}
List<Integer> resList = new ArrayList<>();
postinorderTraversal(0, resList);
return resList;
}
public List<Integer> preorderTraversal(int index, List<Integer> list) {
// 注意是顺序存储二叉树,list中放的是下标index对应的数组中的元素
list.add(arr[index]);
if (2 * index + 1 < arr.length) {
list = preorderTraversal(2 * index + 1, list);
}
if (2 * index + 2 < arr.length) {
list = preorderTraversal(2 * index + 2, list);
}
return list;
}
public List<Integer> inorderTraversal(int index, List<Integer> list) {
if (2 * index + 1 < arr.length) {
list = inorderTraversal(2 * index + 1, list);
}
list.add(arr[index]);
if (2 * index + 2 < arr.length) {
list = inorderTraversal(2 * index + 2, list);
}
return list;
}
public List<Integer> postinorderTraversal(int index, List<Integer> list) {
if (2 * index + 1 < arr.length) {
list = postinorderTraversal(2 * index + 1, list);
}
if (2 * index + 2 < arr.length) {
list = postinorderTraversal(2 * index + 2, list);
}
list.add(arr[index]);
return list;
}
}
标签:index,arr,遍历,List,list,二叉树,顺序存储
From: https://www.cnblogs.com/SnkrGao/p/17384535.html