利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证。用java语言编写代码以及解题思路
时间: 2024-01-23 22:14:46 浏览: 67
用java实现二叉树的创建和遍历.doc
解题思路:
1. 首先,我们需要定义一个树节点类,用于表示二叉树的节点,包括节点值、左子树和右子树。
2. 然后,我们需要一个函数来将括号表示的串转换为二叉树。这个函数需要遍历括号表示的串,遇到左括号则创建一个新的节点,遇到右括号则返回上一层,将当前节点连接到上一层的左子树或右子树上。
3. 最后,我们需要一个函数来对二叉树进行中序遍历,并输出遍历结果,用于验证二叉树是否正确创建。
Java代码实现:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
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 c = s.charAt(i);
if (Character.isDigit(c) || c == '-') {
int j = i;
while (j < s.length() && Character.isDigit(s.charAt(j))) j++;
TreeNode node = new TreeNode(Integer.parseInt(s.substring(i, j)));
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left != null) parent.right = node;
else parent.left = node;
}
stack.push(node);
i = j;
} else if (c == ')') {
stack.pop();
i++;
} else {
i++;
}
}
return stack.pop();
}
public static 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 s = "4(2(3)(1))(6(5))";
TreeNode root = str2tree(s);
inorderTraversal(root);
}
}
```
输出结果为:3 2 1 4 5 6,与预期结果一致,说明二叉树成功创建。
阅读全文