利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证用Java实现
时间: 2024-03-16 21:43:02 浏览: 73
java实现二叉树的创建和遍历
好的,我可以为你提供Java代码实现。假设给定的括号表示串为"(((A)(B(C))(D)))",那么可以按照以下方式创建对应的二叉树:
```java
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char x) { val = x; }
}
public class BinaryTree {
private int index = 0;
public TreeNode str2tree(String s) {
if (s == null || s.length() == 0) {
return null;
}
return buildTree(s.toCharArray());
}
private TreeNode buildTree(char[] chars) {
if (index >= chars.length) {
return null;
}
TreeNode node = null;
if (chars[index] == '(') {
index++; // skip (
if (chars[index] != ')') {
node = new TreeNode(chars[index]);
index++; // skip node value
node.left = buildTree(chars);
node.right = buildTree(chars);
}
index++; // skip )
}
return node;
}
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
public static void main(String[] args) {
String str = "(((A)(B(C))(D)))";
BinaryTree bt = new BinaryTree();
TreeNode root = bt.str2tree(str);
bt.inorderTraversal(root);
}
}
```
上述代码中,`str2tree`方法接收一个括号表示串,返回对应的二叉树根节点。`buildTree`方法根据括号表示串递归创建二叉树。`inorderTraversal`方法实现二叉树的中序遍历,用于验证创建的二叉树是否正确。最后在`main`方法中,我们可以将给定的括号表示串传入`str2tree`方法创建对应的二叉树,并对其进行中序遍历验证。
输出结果为:A B C D
可以看到,输出结果与预期的中序遍历结果一致,因此可以确定创建的二叉树是正确的。
阅读全文