摘要:本文主要介绍了Java编程开发-数据结构与算法「顺序二叉树」,通过具体的内容向大家展现,希望对大家Java编程开发的学习有所帮助。
本文主要介绍了Java编程开发-数据结构与算法「顺序二叉树」,通过具体的内容向大家展现,希望对大家Java编程开发的学习有所帮助。
基本概念
从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树可以转换成数组。如下图所示:
顺序存储二叉树的特点:
顺序存储通常只考虑完全二叉树;
第n个元素的左子节点为 2 * n+1;
第n个元素的右子节点为 2 * n+2;
第n个元素的父节点为 (n-1)/2;
n 表示二叉树中的第几个元素(按0开始编号如上图所示);
需求
要求给定一个数组{1,2,3,4,5,6,7},要求以二叉树前序遍历的方式进行遍历,前序遍历的结果应当为1,2,4,5,3,6,7,
附加完成中序遍历和后序遍历。
代码案例
package com.xie.tree;
/**
* @author: xiexiaofei
* @date: 2020-02-09 20:04
* @description:
*/
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
System.out.println("顺序存储二叉树的前序遍历数组");
arrBinaryTree.preOrder(0);
System.out.println();
System.out.println("顺序存储二叉树的中序遍历数组");
arrBinaryTree.infixOrder(0);
System.out.println();
System.out.println("顺序存储二叉树的后序遍历数组");
arrBinaryTree.postOrder(0);
System.out.println();
/**
* 顺序存储二叉树的前序遍历数组
* 1 2 4 5 3 6 7
* 顺序存储二叉树的中序遍历数组
* 2 4 5 1 3 6 7
* 顺序存储二叉树的后序遍历数组
* 2 4 5 3 6 7 1
*/
}
}
//实现顺序存储二叉树遍历
class ArrBinaryTree {
private int[] arr;//存储数据节点的数组
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
/**
* 编写一个方法,完成顺序存储二叉树的前序遍历。
*
* @param index 数组的下标
*/
public void preOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树的前序遍历");
}
//输出当前的元素
System.out.print(arr[index] + " ");
//向左递归遍历
if ((2 * index + 1) < arr.length) {
preOrder(2 * index + 1);
}
//向右递归
if ((2 * index + 2) < arr.length) {
preOrder(2 * index + 2);
}
}
/**
* 编写一个方法,完成顺序存储二叉树的中序遍历。
*
* @param index
*/
public void infixOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树的前序遍历");
}
//向左递归遍历
if ((2 * index + 1) < arr.length) {
preOrder(2 * index + 1);
}
//输出当前的元素
System.out.print(arr[index] + " ");
//向右递归
if ((2 * index + 2) < arr.length) {
preOrder(2 * index + 2);
}
}
/**
* 编写一个方法,完成顺序存储二叉树的后序遍历。
*
* @param index
*/
public void postOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树的前序遍历");
}
//向左递归遍历
if ((2 * index + 1) < arr.length) {
preOrder(2 * index + 1);
}
//向右递归
if ((2 * index + 2) < arr.length) {
preOrder(2 * index + 2);
}
//输出当前的元素
System.out.print(arr[index] + " ");
}
}
我是小职,记得找我
✅ 解锁高薪工作
✅ 免费获取学习教程,开发工具,代码大全,参考书籍
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号