实验目的:掌握二叉树的构建及遍历操作。 实验内容:按先序遍历的顺序构建的二叉树实现先序、中序和后序遍历,并输出对应的遍历序列,节点要用字母表示。 实验要求: 1、构建一个二叉链表存储结构的二叉树。 2、基于上述构建的二叉树进行先序、中序和后序遍历操作。用Java实现

时间: 2023-11-22 11:54:22 浏览: 54
以下是Java实现的代码: ```java class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char val) { this.val = val; this.left = null; this.right = null; } } public class BinaryTree { private TreeNode root; public BinaryTree(char[] arr) { root = buildTree(arr, 0); } private TreeNode buildTree(char[] arr, int i) { if (i >= arr.length || arr[i] == '#') { return null; } TreeNode node = new TreeNode(arr[i]); node.left = buildTree(arr, 2 * i + 1); node.right = buildTree(arr, 2 * i + 2); return node; } public void preOrderTraversal() { preOrderTraversal(root); System.out.println(); } private void preOrderTraversal(TreeNode node) { if (node == null) { return; } System.out.print(node.val + " "); preOrderTraversal(node.left); preOrderTraversal(node.right); } public void inOrderTraversal() { inOrderTraversal(root); System.out.println(); } private void inOrderTraversal(TreeNode node) { if (node == null) { return; } inOrderTraversal(node.left); System.out.print(node.val + " "); inOrderTraversal(node.right); } public void postOrderTraversal() { postOrderTraversal(root); System.out.println(); } private void postOrderTraversal(TreeNode node) { if (node == null) { return; } postOrderTraversal(node.left); postOrderTraversal(node.right); System.out.print(node.val + " "); } public static void main(String[] args) { char[] arr = {'A', 'B', 'C', 'D', 'E', '#', 'F', '#', '#', 'G', 'H'}; BinaryTree tree = new BinaryTree(arr); System.out.println("Pre-order traversal: "); tree.preOrderTraversal(); System.out.println("In-order traversal: "); tree.inOrderTraversal(); System.out.println("Post-order traversal: "); tree.postOrderTraversal(); } } ``` 在这个例子中,我们首先定义了一个 `TreeNode` 类来表示二叉树的节点。节点具有一个值和两个子节点(左节点和右节点)。 然后,我们定义了 `BinaryTree` 类来表示整个二叉树。我们使用先序遍历的方式来构造二叉树,即从根节点开始,先访问根节点,然后递归构建左子树和右子树。 在 `BinaryTree` 类中,我们实现了三种不同的遍历方式:先序遍历、中序遍历和后序遍历。我们使用递归的方式来遍历整个二叉树,并将遍历结果输出到控制台上。在 `main` 方法中,我们创建了一个二叉树,并使用三种不同的遍历方式来输出遍历结果。 以上就是二叉树的构建及遍历操作的Java实现。

相关推荐

最新推荐

recommend-type

通过先序遍历和中序遍历后的序列还原二叉树(实现方法)

下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
recommend-type

二叉树的先序中序后序层次遍历,高度

从键盘输入二叉树的各结点... 2 )分别实现先序、中序、后序递归遍历二叉树  3 )输出二叉树的高度  4 )输出二叉树的按层次遍历序列  5 )输出二叉树的先序非递归遍历下的结点访问次序 6 )以菜单方式运行
recommend-type

【LeetCode】【树】106. 从中序与后序遍历序列构造二叉树

从中序与后序遍历序列构造二叉树 1 题目地址 https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你...
recommend-type

数据结构实验 二叉树的遍历方法

(3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,后序遍历; (4)实现递归到非递归方法的转变; 三、实验内容: 建立一棵用二叉树链表方式存储的二叉树,并对其进行遍历(先序遍历,中序遍历,后序遍历),...
recommend-type

建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数

[问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

list根据id查询pid 然后依次获取到所有的子节点数据

可以使用递归的方式来实现根据id查询pid并获取所有子节点数据。具体实现可以参考以下代码: ``` def get_children_nodes(nodes, parent_id): children = [] for node in nodes: if node['pid'] == parent_id: node['children'] = get_children_nodes(nodes, node['id']) children.append(node) return children # 测试数
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。