根据先序序列和中序序列构造二叉树进行层次遍历

2024-06-20 03:38

本文主要是介绍根据先序序列和中序序列构造二叉树进行层次遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

基于遍历先序序列的每个元素分割中序序列为左右子树进行递归操作。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;public class Tree {static int[] pretemp;private static int maxLevel = 0;public class BinarayTreeNode {public int m_Value;public BinarayTreeNode m_LeftTreeNode = null;public BinarayTreeNode m_RigtTreeNode = null;}public BinarayTreeNode Construct(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || inorder.length == 0 || preorder.length == 0) {return null;}int ptr = 0;int rootValue = preorder[0];BinarayTreeNode rootNode = new BinarayTreeNode();rootNode.m_Value = rootValue;while (ptr <= inorder.length && inorder[ptr] != rootValue) {ptr++;}pretemp = new int[preorder.length - 1];for (int i = 0; i < preorder.length; i++) {if (i == 0) {continue;}pretemp[i - 1] = preorder[i];}int[] inStart = new int[ptr];int[] inEnd = new int[inorder.length - ptr - 1];int ps = 0;for (int j = 0; j < inorder.length; j++) {if (j < ptr) {inStart[j] = inorder[j];}if (j > ptr) {inEnd[ps] = inorder[j];ps++;}}rootNode.m_LeftTreeNode = Construct(pretemp, inStart);rootNode.m_RigtTreeNode = Construct(pretemp, inEnd);return rootNode;}// print binarayTree as level modepublic static void PrintLevelTree(BinarayTreeNode pRoot) {Queue<BinarayTreeNode> nodeQueue = new LinkedList<BinarayTreeNode>();nodeQueue.add(pRoot);while (nodeQueue != null) {BinarayTreeNode node = nodeQueue.poll();if (node != null)System.out.print(node.m_Value);if (node != null && node.m_LeftTreeNode != null)nodeQueue.add(node.m_LeftTreeNode);if (node != null && node.m_RigtTreeNode != null)nodeQueue.add(node.m_RigtTreeNode);if (node == null) {System.out.println();break;}}}// get current binarayTree levelprivate static int getTreeLeverl(BinarayTreeNode pRoot, int level) {if (pRoot != null) {level++;}if( maxLevel < level ) maxLevel = level;if (pRoot.m_LeftTreeNode != null) {getTreeLeverl(pRoot.m_LeftTreeNode, level);} if (pRoot.m_RigtTreeNode != null) {getTreeLeverl(pRoot.m_RigtTreeNode, level);}return maxLevel ;}private static void printTreeLeverl(Map<Integer, String> printInfo, BinarayTreeNode pRoot, int level) {String value = printInfo.get(level);value = value == null ? "" : value;value = value + pRoot.m_Value +" " ;printInfo.put(level, value);level++;if (pRoot.m_LeftTreeNode != null) {printTreeLeverl(printInfo, pRoot.m_LeftTreeNode, level);}if (pRoot.m_RigtTreeNode != null) {printTreeLeverl(printInfo, pRoot.m_RigtTreeNode, level);}}public static void main(String[] args) {int preorder[] = { 1, 2, 4,9, 7, 0,8,3, 5, 6, 8 }; // 先序int inorder[] = { 9, 4, 7,8, 0,2, 1, 5, 3, 8, 6 }; // 中序//根据先序中序构造二叉树BinarayTreeNode root = new Tree().Construct(preorder, inorder);System.out.println("==========");int totollevel = getTreeLeverl(root, 0);System.out.println("二叉树的深度:"+totollevel);System.out.println("==========");System.out.print("二叉树的层次遍历:");PrintLevelTree(root);System.out.println("===========");System.out.println("二叉树的层次结构:");System.out.println("===========");Map<Integer, String> printInfo = new HashMap<Integer, String>();printTreeLeverl(printInfo, root, 1);for (Entry<Integer, String> map : printInfo.entrySet()) {System.out.println(map.getValue());}}
}

 

这篇关于根据先序序列和中序序列构造二叉树进行层次遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1077000

相关文章

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》:本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR