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

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

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

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());}}
}

 

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

---