利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证用Java实现
时间: 2024-03-16 12:42:32 浏览: 80
好的,我会尽力回答您的问题。首先,利用括号表示串创建二叉树是一种常见的方法,我们可以通过递归的方式来实现。具体步骤如下:
1. 读入括号表示串,例如:"(A(B(C)(D))(E))"。
2. 如果当前字符是左括号,那么就创建一个新的节点,并将其作为当前节点的左子节点。
3. 如果当前字符是字母,那么就创建一个新的节点,并将其作为当前节点的右子节点。同时,将当前节点指向其父节点。
4. 如果当前字符是右括号,那么就将当前节点指向其父节点。
下面是实现代码:
```java
public class BinaryTree {
private static class Node {
Node left;
Node right;
char val;
Node(char val) {
this.val = val;
}
}
public static Node buildTree(String s) {
Stack<Node> stack = new Stack<>();
Node root = null;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
if (!stack.isEmpty()) {
Node parent = stack.peek();
Node node = new Node(s.charAt(++i));
parent.left = node;
stack.push(node);
} else {
root = new Node(s.charAt(++i));
stack.push(root);
}
} else if (c == ')') {
stack.pop();
} else {
Node parent = stack.peek();
Node node = new Node(c);
parent.right = node;
stack.push(node);
}
}
return root;
}
public static void inorderTraversal(Node root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
public static void main(String[] args) {
String s = "(A(B(C)(D))(E))";
Node root = buildTree(s);
inorderTraversal(root); // 输出 C B D A E
}
}
```
在上面的代码中,我们首先定义了一个内部类 `Node`,表示二叉树的节点。然后,我们实现了 `buildTree` 方法,用于构建二叉树。最后,我们实现了 `inorderTraversal` 方法,用于验证二叉树的中序遍历结果是否正确。
希望这个回答能够帮助到您!
阅读全文