用Java编码二叉树的括号表示串创建, 利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证。
时间: 2024-01-23 19:15:06 浏览: 72
二叉树的括号表示法,二叉树的遍历,二叉树的树形打印输出(C++)
好的,下面是Java代码实现二叉树的括号表示串创建以及利用中序遍历验证的过程:
```java
import java.util.Scanner;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char x) {
val = x;
}
}
public class BinaryTreeSerialization {
int index = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
BinaryTreeSerialization bt = new BinaryTreeSerialization();
TreeNode root = bt.deserialize(s);
bt.inOrder(root);
}
private TreeNode deserialize(String s) {
if (index >= s.length()) {
return null;
}
char c = s.charAt(index);
if (c == '#') {
index++;
return null;
}
TreeNode node = new TreeNode(c);
index++;
node.left = deserialize(s);
node.right = deserialize(s);
return node;
}
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
```
代码中的TreeNode类表示二叉树的节点,BinaryTreeSerialization类实现二叉树的括号表示串创建以及中序遍历验证的过程。在deserialize方法中,先读取当前字符,如果是#,则表示当前节点为空,直接返回null;否则,创建一个节点,并递归构造左右子树。在inOrder方法中,按照左子树、根节点、右子树的顺序遍历二叉树,并输出每个节点的值。
输入的括号表示串例如:a(b(d,e),c(#,f(g,))),表示的二叉树如下:
```
a
/ \
b c
/ \ \
d e f
/
g
```
通过中序遍历,输出结果为:d b e a f g c。
阅读全文