栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

尚硅谷数据结构与算法(Java)--学习小记23

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

尚硅谷数据结构与算法(Java)--学习小记23

目录

1:顺序存储二叉树的三种遍历

1.顺序存储二叉树的特点:

2.代码:

3.运行截图:


1:顺序存储二叉树的三种遍历

1.顺序存储二叉树的特点:
  • 1)顺序二叉树通常只考虑完全二叉树

  • 2)第n个元素的左子节点为  2*n+1
  • 3)第n个元素的右子节点为  2*n+2
  • 4)第n个元素的父节点为     (n-1)/2
  • 5)n:表示二叉树中的第几个元素(按0开始编号)

顺序存储二叉树的前序遍历 :1 2 4 5 3 6 7
顺序存储二叉树的中序遍历 :4 2 5 1 6 3 7
顺序存储二叉树的后序遍历 :4 5 2 6 7 3 1 

2.代码:
package com.atguigu.tree;

public class ArrBinaryTreeDome {

	public static void main(String[] args) {
		//
		int[] arr = {1,2,3,4,5,6,7};
		//创建ArrayBinaryTree
		ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
		System.out.print("前序遍历:");
		arrBinaryTree.preOrder();//1 2 4 5 3 6 7
		System.out.print("中序遍历:");
		arrBinaryTree.infixOrder();//4 2 5 1 6 3 7
		System.out.print("后序遍历:");
		arrBinaryTree.postOrder();//4 5 2 6 7 3 1
	}

}
//编写类ArrayBinaryTree,实现顺序存储二叉树遍历
class ArrBinaryTree{
	private int[] arr;//存储数据结点的数组

	public ArrBinaryTree(int[] arr) {
		this.arr = arr;
	}
	//重载preOrder
	public void preOrder() {
		this.preOrder(0);
	}
	//重载preOrder
	public void infixOrder() {
		this.infixOrder(0);
	}
	//重载preOrder
	public void postOrder() {
		this.postOrder(0);
	}
	
	//编写方法,完成顺序存储二叉树的前序遍历
	
	public void preOrder(int index) {
		//如果数组空,或者arr.length=0
		if(arr==null || arr.length==0) {
			System.out.println("数组空,不能按照二叉树前序遍历");
		}
		//输出当前元素
		System.out.print(arr[index]+" ");
		//向左递归遍历
		if((index*2+1) < arr.length) {
			preOrder(2*index+1);
		}
		//向右递归遍历
		if((index*2+2) < arr.length) {
			preOrder(index*2+2);
		}
	}
	//中序
	public void infixOrder(int index) {
		//如果数组空,或者arr.length=0
		if(arr==null || arr.length==0) {
			System.out.println("数组空,不能按照二叉树前序遍历");
		}
		//向左递归遍历
		if((index*2+1) < arr.length) {
			infixOrder(2*index+1);
		}
		//输出当前元素
		System.out.print(arr[index]+" ");
		//向右递归遍历
		if((index*2+2) < arr.length) {
			infixOrder(index*2+2);
		}
	}
	//后序
	public void postOrder(int index) {
		//如果数组空,或者arr.length=0
		if(arr==null || arr.length==0) {
			System.out.println("数组空,不能按照二叉树前序遍历");
		}
		//向左递归遍历
		if((index*2+1) < arr.length) {
			postOrder(2*index+1);
		}
		//向右递归遍历
		if((index*2+2) < arr.length) {
			postOrder(index*2+2);
		}
		//输出当前元素
		System.out.print(arr[index]+" ");
	}
}

3.运行截图:

 

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937306.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号