前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点,从而可以将中序遍历分为左右两个部分,左边部分为左子树的中序遍历,右边部分为右子树的中序遍历,进而也可以将前序遍历除第一个元素以外的剩余部分分为两个部分,第一个部分为左子树的前序遍历,第二个部分为右子树的前序遍历。
由上述分析结果,可以递归调用构建函数,根据左子树、右子树的前序、中序遍历的结果输出后序遍历的结果。
//根据前序遍历和中序遍历重建二叉树的Java实现
class Node {
Node left = null;
Node right = null;
char value;
}
public class BinaryTreeBuilder {
/**
* 根据前序遍历和中序遍历重建二叉树子树
* @param preOrder 前序遍历数组
* @param start 子树起始位置
* @param inOrder 中序遍历数组
* @param end 中序遍历结束位置
* @param length 节点数
* @return 树的根节点
*/
public static Node buildTree(char[] preOrder,int start, char[] inOrder,int end,int length){
//参数验证
if (preOrder == null || preOrder.length == 0 || inOrder == null
|| inOrder.length == 0 || length <= 0) {
return null;
}
//根据前序遍历的第一个元素建立树根节点
char value = preOrder[start];
Node root = new Node();
root.value = value;
//递归终止条件:子树只有一个节点
if (length == 1)
return root;
//根据前序遍历的第一个元素在中序遍历中的位置分拆树的左子树和右子树
int i = 0;
while (i < length) {
if (value == inOrder[end - i]) {
break;
}
i++;
}
//建立子树的左子树
root.left = buildTree(preOrder, start + 1, inOrder, end - i - 1, length - 1 - i);
//建立子树的右子树
root.right = buildTree(preOrder, start + length - i, inOrder, end, i );
return root;
}
// 后序遍历二叉树
private static void postOrder(Node root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value+" ");
}
public static void main(String[] args) {
//char[] preOrder = new char[] {'1', '2', '4', '5', '3', '6'};
char[] preOrder = new char[] {'A', 'B', 'D', 'E', 'G', 'H','J','C','F','I'};
//char[] inOrder = new char[] {'4', '2', '5', '1', '6', '3'};
char[] inOrder = new char[] {'D', 'B', 'G', 'E', 'H', 'J','A','C','I','F'};
Node root = buildTree(preOrder, 0, inOrder, inOrder.length - 1, inOrder.length);
postOrder(root);
}
}
运行结果:
D G J H E B I F C A
下载源码:
分享到:
相关推荐
常见的遍历方式有前序遍历、中序遍历和后序遍历。 3. 前序遍历:前序遍历是一种遍历方式,先访问当前节点,然后递归地访问左子节点和右子节点。其顺序是:当前节点 -> 左子节点 -> 右子节点。 4. 中序遍历:中序...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
本文将深入探讨四种常见的二叉树遍历方法:前序遍历、中序遍历、后序遍历以及层次遍历,并以C++编程语言为例,阐述如何实现这些遍历算法。 1. **前序遍历**(Preorder Traversal) 前序遍历的顺序是根节点 -> 左...
二叉树的遍历有多种方式,本文将介绍二叉树的递归遍历,中序遍历,先序遍历和后序遍历。 递归遍历是指使用递归函数来遍历二叉树的每个结点。递归遍历的优点是代码简洁易懂,但缺点是可能会导致堆栈溢出。在本文的...
一、实验目的 1、掌握二叉树的基本概念,链表描述方法;遍历方法。 二、实验内容 1、 创建二叉树类。二叉树的存储结构使用...4、 接收键盘录入的二叉树前序序列和中序序列(各元素各不相同),输出该二叉树的后序序列。
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
前序、中序和后序遍历是二叉树三种基本的遍历方式,每种方式都有其特定的访问顺序。这里我们将重点讨论如何在已知二叉树的前序和中序遍历的情况下,通过非递归算法实现后序遍历。 **前序遍历**:根节点 -> 左子树 -...
本篇将详细介绍二叉树的基本操作,包括前序遍历、中序遍历、后序遍历以及层序遍历。 **1. 二叉树的基本操作** 二叉树的基本操作主要包括创建、插入、删除节点以及遍历等。创建二叉树时,需要指定根节点,之后通过...
二叉树的建立以及二叉树的层次遍历、前序遍历、中序遍历、后序遍历
二叉树的遍历主要有三种经典方法:前序遍历、中序遍历和后序遍历。这些遍历方法是理解二叉树特性和操作的关键。 1. **前序遍历**(Preorder Traversal): - 遵循“根-左-右”的顺序访问节点。首先访问根节点,...
二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
主要有三种遍历方式:前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根)。以下是在Python中实现这三种遍历的方法: 1. 前序遍历: ```python def pre_order_traversal(node): if node is not ...
本文将深入探讨如何使用Java实现二叉树的前序、中序和后序建树,以及对应的遍历方法。 首先,我们需要定义一个二叉树节点类`TreeNode`,它包含两个属性:一个整型值`val`表示节点的值,以及两个指向子节点的引用`...
数据结构算法及应用 上机作业 谦虚中序遍历顺序&中序后续遍历顺序,还原二叉树并输出
在上述`BinaryTreeNode`类中,我们需要根据前序、中序、后序遍历的规则填充相应的方法,同时实现计算深度和叶节点数量的逻辑。这个类可以作为构建和操作二叉树的基础,方便我们进行各种操作和算法的实现。通过这样的...
本文将深入探讨二叉树的三种主要遍历方法:前序遍历、中序遍历和后序遍历。 **前序遍历(Preorder Traversal)** 前序遍历的顺序是:根节点 -> 左子树 -> 右子树。这意味着我们首先访问根节点,然后递归地遍历左...
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
在IT领域,二叉树是一种基础且...总之,二叉树遍历和二叉查找树的验证是数据结构和算法的基础内容,它们在编程竞赛、软件开发以及许多计算机科学问题中都有广泛应用。理解和熟练掌握这些概念对于提升IT技能至关重要。
二叉树的遍历,全部用递归实现,很有规律! 二叉树的遍历,全部用递归实现,很有规律