用java实现代码的编写:对于括号表示串”A(B(D(,G)),C(E,F))”,调用相关方法建立链式存储的二叉树,并调用相应方法输出其先序遍历序列、中序遍历序列、后序遍历序列。
时间: 2024-11-30 07:29:25 浏览: 26
在Java中,我们可以使用递归的方式来构建这样的二叉树结构,通常会定义一个`TreeNode`类来表示节点,包含一个字符值和两个指向左右子节点的引用。首先,我们需要创建一些辅助方法来处理括号的配对:
```java
public class TreeNode {
char val;
TreeNode left;
TreeNode right;
// 构造函数
public TreeNode(char val) {
this.val = val;
left = null;
right = null;
}
}
public class BinarySearchTree {
private TreeNode root;
// 插入方法,用于构建链式存储
public void insert(String s) {
insert(root, s, 0);
}
private TreeNode insert(TreeNode node, String str, int index) {
if (node == null || index >= str.length()) return null;
char val = str.charAt(index++);
if (str.charAt(index) == '(') {
node.left = insert(new TreeNode(val), str, index + 1);
} else if (str.charAt(index) == ')') {
node.right = insert(new TreeNode(val), str, index + 1);
} else {
node.val = val;
index--;
}
return node;
}
// 遍历方法
public List<String> traverse(String type) {
switch (type) {
case "preorder":
return preorderTraversal(root);
case "inorder":
return inorderTraversal(root);
case "postorder":
return postorderTraversal(root);
default:
throw new IllegalArgumentException("Invalid traversal type");
}
}
// 先序遍历
private List<String> preorderTraversal(TreeNode node) {
List<String> res = new ArrayList<>();
if (node != null) {
res.add(node.val + "");
res.addAll(preorderTraversal(node.left));
res.addAll(preorderTraversal(node.right));
}
return res;
}
// 中序遍历
private List<String> inorderTraversal(TreeNode node) {
List<String> res = new ArrayList<>();
if (node != null) {
res.addAll(inorderTraversal(node.left));
res.add(node.val + "");
res.addAll(inorderTraversal(node.right));
}
return res;
}
// 后序遍历
private List<String> postorderTraversal(TreeNode node) {
List<String> res = new ArrayList<>();
if (node != null) {
res.addAll(postorderTraversal(node.left));
res.addAll(postorderTraversal(node.right));
res.add(node.val + "");
}
return res;
}
}
```
然后你可以通过以下方式实例化并操作这个二叉树:
```java
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
String input = "A(B(D(,G)),C(E,F))";
bst.insert(input);
List<String> preorder = bst.traverse("preorder");
List<String> inorder = bst.traverse("inorder");
List<String> postorder = bst.traverse("postorder");
System.out.println("Preorder traversal: " + preorder);
System.out.println("Inorder traversal: " + inorder);
System.out.println("Postorder traversal: "
阅读全文