树：顺序存储二叉树

本文主要是介绍树：顺序存储二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1，顺序存储二叉树基本介绍

• 顺序存储二叉树是堆排序的基本思想
• 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换为树，树也可以转换为数组，如下图所示
  
• 顺序存储二叉树只考虑完全二叉树，并且元素间存在函数对应关系
  • 第n个元素的左子节点为：index = 2 * n + 1
  • 第n个元素的右子节点为：index = 2 * n + 2
  • 第n个元素的父节点为：index = （n - 1）/ 2
  • 其中n表示在完全二叉树中的第几个元素，同时也表示数组中的索引下标，从0开始

2，代码实现

package com.self.datastructure.tree;/*** 顺序存储二叉树* 只对完全二叉树有效** @author pj_zhang* @create 2020-03-22 18:40**/
public class ArrayBinaryTree {private static int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};/*** 讲一个二叉树的节点, 以数组的顺序按层依次存放, 则该二叉树肯定是一个完全二叉树* 在生成的完全二叉树中:* 第n个元素的左子节点 index = 2 * n + 1* 第n个元素的右子节点 index = 2 * n + 2* 第n个元素的父节点为 index = (n - 1) / 2* @param args*/public static void main(String[] args) {System.out.println("前序输出");preShowDetails(0);System.out.println("中序输出");middleShowDetails(0);System.out.println("后序输出");postShowDetails(0);}/*** 前序遍历* 输出结果: 0, 1, 3, 7, 8, 5, 9, 2, 5, 6** @param index 开始索引*/public static void preShowDetails(int index) {// 先输出当前节点System.out.println("前序输出: " + array[index]);// 再输出左侧节点if ((index * 2 + 1) < array.length) {preShowDetails(index * 2 + 1);}// 再输出右侧节点if ((index * 2 + 2) < array.length) {preShowDetails(index * 2 + 2);}}/*** 中序遍历* 输出结果: 7, 3, 8, 1, 9, 4, 0, 5, 2, 6** @param index 开始索引*/public static void middleShowDetails(int index) {// 先输出左侧节点if ((index * 2 + 1) < array.length) {middleShowDetails(index * 2 + 1);}// 再输出当前节点System.out.println("中序输出: " + array[index]);// 最后输出右侧节点if ((index * 2 + 2) < array.length) {middleShowDetails(index * 2 + 2);}}/*** 后序遍历* 输出结构: 7, 8, 3, 9, 4, 1, 5, 6, 2, 0** @param index 开始索引*/public static void postShowDetails(int index) {// 先输出左侧节点if ((index * 2 + 1) < array.length) {postShowDetails(index * 2 + 1);}// 再输出右侧节点if ((index * 2 + 2) < array.length) {postShowDetails(index * 2 + 2);}// 最后输出当前节点System.out.println("后序输出: " + array[index]);}}

这篇关于树：顺序存储二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---