preOrder在java中
时间: 2023-12-03 15:42:42 浏览: 31
preOrder是二叉树的一种遍历方式,其遍历顺序为:根节点 -> 左子树 -> 右子树。在Java中,可以使用递归实现preOrder遍历,代码示例如下:
```java
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
```
其中,TreeNode是二叉树的节点类,包含val、left和right三个属性,分别表示当前节点的值、左子节点和右子节点。在遍历过程中,先输出当前节点的值,再递归遍历左子树和右子树。
调用preOrder方法时,传入二叉树的根节点即可实现preOrder遍历。
相关问题
java 实现 二叉树
Java可以通过数组来实现顺序存储二叉树。在这种实现方式中,使用一个一维数组来存储二叉树中的节点数据,在数组中的位置按照特定规则与二叉树中的节点位置建立对应关系。通过这种方式,可以实现二叉树的前序遍历、中序遍历和后序遍历。
下面是一个Java的示例代码,演示了如何使用数组实现顺序存储二叉树的前序遍历:
```java
public class ArrayBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
arrayBinaryTree.preOrder(); // 输出结果:1, 2, 4, 5, 3, 6, 7
}
}
class ArrayBinaryTree {
private int[] arr; // 存储数据节点的数组
public ArrayBinaryTree(int[] arr) {
this.arr = arr;
}
// 前序遍历
public void preOrder() {
preOrder(0);
}
private void preOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树的前序遍历");
return;
}
System.out.println(arr[index]); // 输出当前节点
// 遍历左子树
if ((index * 2 + 1) < arr.length) {
preOrder(index * 2 + 1);
}
// 遍历右子树
if ((index * 2 + 2) < arr.length) {
preOrder(index * 2 + 2);
}
}
}
```
以上代码实现了二叉树的前序遍历。你可以根据需要扩展它来实现中序遍历和后序遍历。
POJ 3784 java
根据提供的引用内容,这是一个关于二叉树遍历的问题。具体来说,给定二叉树的前序遍历和中序遍历,需要求出二叉树的后序遍历。
以下是一个Java实现的例子:
```java
import java.util.Scanner;
class Node {
char value;
Node left;
Node right;
public Node(char value) {
this.value = value;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t-- > 0) {
int n = scanner.nextInt();
String preOrder = scanner.next();
String inOrder = scanner.next();
Node root = buildTree(preOrder, inOrder);
postOrder(root);
System.out.println();
}
scanner.close();
}
private static Node buildTree(String preOrder, String inOrder) {
if (preOrder.length() == 0) {
return null;
}
char rootValue = preOrder.charAt(0);
int rootIndex = inOrder.indexOf(rootValue);
Node root = new Node(rootValue);
root.left = buildTree(preOrder.substring(1, rootIndex + 1), inOrder.substring(0, rootIndex));
root.right = buildTree(preOrder.substring(rootIndex + 1), inOrder.substring(rootIndex + 1));
return root;
}
private static void postOrder(Node root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value);
}
}
```
这段代码首先读取输入的测试用例数量t,然后依次读取每个测试用例的节点数量n、前序遍历和中序遍历的字符串。接下来,通过递归构建二叉树,并使用后序遍历输出结果。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)