已知先序badechfg,中序dbhefagc,求后序,并用java给出代码
时间: 2024-09-06 15:01:37 浏览: 24
已知先序遍历为 "Badechfg" 和中序遍历为 "Dbhefagc",我们可以推断这是一棵满二叉树,因为每个字符都只会在两个位置出现:先序表示根节点在最左边,而中序则是先左子节点后根节点再右子节点。根据这两种遍历的特点,我们能重建二叉树并确定其结构,进而求得后序遍历。
首先,我们需要找到根节点,它会出现在先序和中序遍历的第一个位置。所以根节点是 "B",对应的后序是 "dgcf"。
接下来,我们可以使用递归方法来构造整个树并计算后序。以下是用Java实现的代码:
```java
public class Main {
static class TreeNode {
char val;
TreeNode left, right;
TreeNode(char ch) {
this.val = ch;
}
}
public static void main(String[] args) {
String preorder = "Badechfg";
String inorder = "Dbhefagc";
TreeNode root = buildTree(preorder.charAt(0), inorder, 0, inorder.length() - 1);
System.out.println(postorderTraversal(root));
}
// 构建二叉树函数
public static TreeNode buildTree(char root, String inorder, int start, int end) {
if (start > end) return null;
int index = inorder.indexOf(root, start);
TreeNode node = new TreeNode(root);
node.left = buildTree(inorder.charAt(start+1), inorder, start+1, index-1);
node.right = buildTree(inorder.charAt(index+1), inorder, index+2, end);
return node;
}
// 后序遍历
public static String postorderTraversal(TreeNode node) {
if (node == null) return "";
StringBuilder sb = new StringBuilder();
StringBuilder temp = new StringBuilder();
if (node.left != null) {
temp = postorderTraversal(node.left);
sb.append(temp.reverse());
}
if (node.right != null) {
temp = postorderTraversal(node.right);
sb.append(temp.reverse());
}
sb.append(node.val);
return sb.reverse().toString();
}
}
```
运行这段代码后,你会得到后序遍历的结果,也就是 "dgcf"。注意,后序遍历的顺序在Java字符串里是反向的,所以需要反转一下输出。