Java 利用键盘输入结点与二叉树的先序遍历序列和中序遍历序列,试着找出它的后序遍历序列。
时间: 2023-12-30 07:02:52 浏览: 28
可以使用递归的思想来实现二叉树的遍历,其中包括先序遍历、中序遍历和后序遍历。对于一个二叉树,先序遍历的顺序是先访问根节点,然后按照先序遍历的顺序递归访问左子树和右子树;中序遍历的顺序是先递归访问左子树,然后访问根节点,最后递归访问右子树;后序遍历的顺序是先递归访问左子树和右子树,最后访问根节点。
通过先序遍历序列和中序遍历序列可以构建出二叉树,然后再进行后序遍历即可得到后序遍历序列。具体实现步骤如下:
1. 首先根据先序遍历序列确定根节点的值,然后在中序遍历序列中找到根节点的位置,将其分为左子树和右子树两个部分;
2. 对于左子树和右子树,分别递归进行上述步骤,得到左子树的后序遍历序列和右子树的后序遍历序列;
3. 将左子树的后序遍历序列和右子树的后序遍历序列合并,然后再将根节点的值添加到序列末尾,即得到二叉树的后序遍历序列。
下面是 Java 代码实现:
```
import java.util.Scanner;
public class BinaryTreeTraversal {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入先序遍历序列和中序遍历序列
System.out.print("请输入二叉树的先序遍历序列:");
String preOrder = scanner.nextLine();
System.out.print("请输入二叉树的中序遍历序列:");
String inOrder = scanner.nextLine();
// 构建二叉树并输出后序遍历序列
String postOrder = getPostOrder(preOrder, inOrder);
System.out.println("二叉树的后序遍历序列为:" + postOrder);
}
// 根据先序遍历序列和中序遍历序列获取后序遍历序列
private static String getPostOrder(String preOrder, String inOrder) {
if (preOrder.isEmpty() || inOrder.isEmpty()) {
return "";
}
// 获取根节点的值
char rootValue = preOrder.charAt(0);
// 在中序遍历序列中找到根节点的位置
int rootIndex = inOrder.indexOf(rootValue);
// 获取左子树的先序遍历序列和中序遍历序列
String leftPreOrder = preOrder.substring(1, rootIndex + 1);
String leftInOrder = inOrder.substring(0, rootIndex);
// 获取右子树的先序遍历序列和中序遍历序列
String rightPreOrder = preOrder.substring(rootIndex + 1);
String rightInOrder = inOrder.substring(rootIndex + 1);
// 递归获取左子树和右子树的后序遍历序列,并将根节点的值添加到序列末尾
String leftPostOrder = getPostOrder(leftPreOrder, leftInOrder);
String rightPostOrder = getPostOrder(rightPreOrder, rightInOrder);
return leftPostOrder + rightPostOrder + rootValue;
}
}
```
注意,这里假设输入的先序遍历序列和中序遍历序列都是合法的,即能够根据它们构建出一棵二叉树。如果输入的序列不合法,可能会导致程序抛出异常。