Java实现利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证。
时间: 2024-01-23 08:17:05 浏览: 110
可以通过以下步骤实现:
1. 定义一个节点类,包含一个值和左右子节点指针的引用。
```java
class Node {
char val;
Node left;
Node right;
public Node(char val) {
this.val = val;
}
}
```
2. 创建一个函数,接收一个括号表示的字符串,返回创建的二叉树的根节点。
```java
public Node createTree(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 == '(') {
Node node = new Node(s.charAt(i + 1));
if (root == null) {
root = node;
}
if (!stack.isEmpty()) {
Node parent = stack.peek();
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.push(node);
i++;
} else if (c == ')') {
stack.pop();
}
}
return root;
}
```
3. 创建一个函数,接收一个二叉树的根节点,返回中序遍历的结果。
```java
public String inorderTraversal(Node root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
return "";
}
sb.append(inorderTraversal(root.left));
sb.append(root.val);
sb.append(inorderTraversal(root.right));
return sb.toString();
}
```
4. 测试函数。
```java
public static void main(String[] args) {
String s = "(A(B(C)(D))(E(F)))";
Node root = createTree(s);
String inorder = inorderTraversal(root);
System.out.println(inorder); // "CBDAFE"
}
```
这样就可以通过括号表示的串创建二叉树,并通过中序遍历结果进行验证了。
阅读全文