用JAVAweb编写输入结点数,先序遍历序列和中序遍历序列和输出后序遍历序列。
时间: 2024-05-12 10:14:53 浏览: 53
这个问题需要用到树的知识,具体地,需要根据先序遍历和中序遍历构建出二叉树,然后再进行后序遍历。
以下是一个基于Java的实现代码:
```java
import java.util.*;
public class BinaryTree {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("输入节点数:");
int n = sc.nextInt();
System.out.print("输入先序遍历序列:");
int[] preOrder = new int[n];
for (int i = 0; i < n; i++) {
preOrder[i] = sc.nextInt();
}
System.out.print("输入中序遍历序列:");
int[] inOrder = new int[n];
for (int i = 0; i < n; i++) {
inOrder[i] = sc.nextInt();
}
// 构建二叉树
TreeNode root = buildTree(preOrder, inOrder);
// 后序遍历二叉树
List<Integer> postOrder = new ArrayList<>();
postOrderTraversal(root, postOrder);
// 输出结果
System.out.print("后序遍历序列为:");
for (int i = 0; i < n; i++) {
System.out.print(postOrder.get(i) + " ");
}
}
// 根据先序遍历和中序遍历构建二叉树
public static TreeNode buildTree(int[] preOrder, int[] inOrder) {
if (preOrder == null || inOrder == null || preOrder.length == 0 || inOrder.length == 0) {
return null;
}
return buildTreeHelper(preOrder, inOrder, 0, preOrder.length - 1, 0, inOrder.length - 1);
}
private static TreeNode buildTreeHelper(int[] preOrder, int[] inOrder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preOrder[preStart];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inOrder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
root.left = buildTreeHelper(preOrder, inOrder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root.right = buildTreeHelper(preOrder, inOrder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
// 后序遍历二叉树
public static void postOrderTraversal(TreeNode root, List<Integer> postOrder) {
if (root == null) {
return;
}
postOrderTraversal(root.left, postOrder);
postOrderTraversal(root.right, postOrder);
postOrder.add(root.val);
}
// 定义树节点
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
}
```
这个程序中,首先从输入中读取节点数、先序遍历序列和中序遍历序列。然后,调用 `buildTree()` 方法根据先序遍历和中序遍历构建出二叉树。最后,调用 `postOrderTraversal()` 方法后序遍历二叉树,将结果存入一个列表中,并输出后序遍历序列。
需要注意的是,这个程序中的实现是基于递归的。在实际应用中,如果树的高度较大,递归可能会导致栈溢出。因此,需要采用迭代等其他方式实现。
阅读全文