Java现在利用键盘输入结点与一颗二叉树的先序遍历序列和中序遍历序列,试着找出它的后序遍历序列。
时间: 2023-12-30 18:02:41 浏览: 30
可以通过递归来实现根据先序遍历序列和中序遍历序列构造出二叉树,并在构造完成后进行后序遍历输出。
具体实现步骤如下:
1. 读取键盘输入的先序遍历序列和中序遍历序列,并保存到对应的数组中。
2. 构造二叉树:
(1)找到先序遍历序列中的根节点,即第一个元素。
(2)在中序遍历序列中找到根节点的位置,其左边的部分为左子树的中序遍历序列,右边的部分为右子树的中序遍历序列。
(3)根据左子树的中序遍历序列和左子树的元素个数,在先序遍历序列中找到左子树的先序遍历序列和右子树的先序遍历序列。
(4)递归构造左子树和右子树。
3. 后序遍历输出二叉树。
具体实现代码如下:
```java
import java.util.Scanner;
public class BinaryTree {
private static int[] preOrder; // 先序遍历序列
private static int[] inOrder; // 中序遍历序列
private static int[] postOrder; // 后序遍历序列
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入先序遍历序列:");
String preOrderStr = scanner.nextLine();
preOrder = parseInput(preOrderStr);
System.out.print("请输入中序遍历序列:");
String inOrderStr = scanner.nextLine();
inOrder = parseInput(inOrderStr);
// 构造二叉树
TreeNode root = buildTree(0, 0, preOrder.length - 1);
// 后序遍历输出二叉树
postOrder = new int[preOrder.length];
int index = 0;
postOrderTraversal(root, index);
System.out.println("后序遍历序列为:" + arrayToString(postOrder));
}
// 根据输入字符串解析出数组
private static int[] parseInput(String input) {
String[] arr = input.split(" ");
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = Integer.parseInt(arr[i]);
}
return res;
}
// 构造二叉树
private static TreeNode buildTree(int preStart, int inStart, int inEnd) {
if (preStart > preOrder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preOrder[preStart]);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inOrder[i] == root.val) {
inIndex = i;
}
}
root.left = buildTree(preStart + 1, inStart, inIndex - 1);
root.right = buildTree(preStart + inIndex - inStart + 1, inIndex + 1, inEnd);
return root;
}
// 后序遍历输出二叉树
private static void postOrderTraversal(TreeNode root, int index) {
if (root == null) {
return;
}
postOrderTraversal(root.left, index);
postOrderTraversal(root.right, index);
postOrder[index++] = root.val;
}
// 将数组转换为字符串
private static String arrayToString(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]);
if (i != arr.length - 1) {
sb.append(" ");
}
}
return sb.toString();
}
// 树节点定义
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
}
```
输入示例:
```
请输入先序遍历序列:1 2 4 5 3 6 7
请输入中序遍历序列:4 2 5 1 6 3 7
```
输出示例:
```
后序遍历序列为:4 5 2 6 7 3 1
```