使用Java将输入的字符串转化为树并输出
时间: 2023-12-29 12:01:47 浏览: 28
这是一个比较复杂的问题,需要涉及到树的数据结构和字符串的解析。下面给出一个简单的示例代码,仅供参考:
```
import java.util.*;
class TreeNode {
public String val;
public TreeNode left;
public TreeNode right;
public TreeNode(String val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class StringToTree {
public static TreeNode str2tree(String s) {
if (s == null || s.length() == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
int i = 0;
while (i < s.length()) {
char ch = s.charAt(i);
if (ch == '(') {
i++;
} else if (ch == ')') {
stack.pop();
i++;
} else {
int j = i;
while (j < s.length() && s.charAt(j) != '(' && s.charAt(j) != ')') {
j++;
}
String val = s.substring(i, j);
TreeNode node = new TreeNode(val);
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.push(node);
i = j;
}
}
return stack.isEmpty() ? null : stack.peek();
}
public static void printTree(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
printTree(root.left);
printTree(root.right);
}
public static void main(String[] args) {
String s = "4(2(3)(1))(6(5))";
TreeNode root = str2tree(s);
printTree(root); // output: 4 2 3 1 6 5
}
}
```
这个代码中,我们首先定义了一个`TreeNode`类表示树节点,其中包括节点的值(字符串类型)以及左右子节点。然后我们定义了一个`str2tree`方法,输入一个字符串表示一棵树,输出树的根节点。这个方法的实现过程如下:
1. 我们使用一个栈来辅助构建树,初始时栈为空。
2. 从字符串的第一个字符开始遍历,如果遇到左括号则跳过,如果遇到右括号则弹出栈顶元素,否则说明当前字符是一个节点的值,我们在字符串中找到该节点的值,并创建一个`TreeNode`对象表示该节点。
3. 如果栈不为空,则当前节点应该是栈顶元素的左或右子节点,我们将其插入到树中,并将其压入栈中。
4. 遍历完整个字符串后,栈顶元素就是树的根节点,返回即可。
最后我们定义了一个`printTree`方法,用于打印树的前序遍历结果,方便我们验证代码的正确性。在`main`方法中我们给出了一个示例字符串,并将其转化为树并输出。