java代码实现创建一棵二叉链表表示的二叉树中,实现以广义表表示构造二叉树
时间: 2024-01-23 20:14:14 浏览: 174
基于链表实现二叉树(java算法源码)
以下是Java代码实现创建一棵二叉链表表示的二叉树,其中使用广义表作为输入参数:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTree {
private int index = 0;
public TreeNode buildTree(String s) {
if (s == null || s.length() == 0) {
return null;
}
return buildTreeHelper(s.toCharArray());
}
private TreeNode buildTreeHelper(char[] chars) {
TreeNode root = null;
int num = 0;
boolean negative = false;
while (index < chars.length) {
if (chars[index] >= '0' && chars[index] <= '9') {
num = num * 10 + (chars[index] - '0');
} else if (chars[index] == '-') {
negative = true;
} else if (chars[index] == '(') {
index++;
if (root == null) {
root = new TreeNode(negative ? -num : num);
root.left = buildTreeHelper(chars);
} else {
root.right = buildTreeHelper(chars);
}
num = 0;
negative = false;
} else if (chars[index] == ')') {
return root;
}
index++;
}
return root;
}
}
```
广义表表示的二叉树构造规则如下:
1. 如果当前字符是数字,则读取连续的数字字符,构造一个节点,并将该节点作为当前节点的左子节点。
2. 如果当前字符是'-',则说明该节点的值为负数。
3. 如果当前字符是'(',则当前节点的左子节点已经构造完毕,开始构造右子节点。
4. 如果当前字符是')',则当前子树构造完毕,返回当前节点。
5. 重复以上步骤直到整个广义表被处理完毕。
阅读全文