利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证。java
时间: 2024-01-23 12:16:15 浏览: 18
可以通过递归的方式,根据括号表示串创建二叉树,并通过中序遍历来验证二叉树是否正确。
以下是实现代码:
```java
public class BinaryTree {
private static class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char val) {
this.val = val;
}
}
public static TreeNode createTree(String s) {
if (s == null || s.length() == 0) {
return null;
}
TreeNode root = new TreeNode(s.charAt(0));
int len = s.length();
int i = 1;
while (i < len) {
int count = 0;
int j = i;
while (j < len) {
if (s.charAt(j) == '(') {
count++;
} else if (s.charAt(j) == ')') {
count--;
}
if (count == 0) {
break;
}
j++;
}
String sub = s.substring(i + 1, j);
if (i + 1 < len && s.charAt(i + 1) == '(') {
root.left = createTree(sub);
} else {
root.right = createTree(sub);
}
i = j + 1;
}
return root;
}
public static void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
public static void main(String[] args) {
String s = "A(B(C)(D))(E)";
TreeNode root = createTree(s);
inOrder(root);
}
}
```
运行结果为:C B D A E
其中,括号表示串 "A(B(C)(D))(E)" 表示的二叉树为:
```
A
/ \
B E
/ \
C D
```
通过验证中序遍历结果,可以看出二叉树创建和遍历的正确性。