java代码实现创建一棵二叉链表表示的二叉树中,实现以广义表表示构造二叉树,并采用先根、中根、后根、层次算法输出二叉树字符
时间: 2023-12-24 13:05:45 浏览: 53
广义表的二叉链式存储表示及其算法设计
可以参考以下 Java 代码实现:
```java
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char x) {
val = x;
}
}
public class BinaryTree {
public static void main(String[] args) {
String str = "A(B(D,E(G,)),C(,F))"; // 广义表表示的二叉树
TreeNode root = createBinaryTree(str);
System.out.println("先根遍历:");
preOrder(root);
System.out.println();
System.out.println("中根遍历:");
inOrder(root);
System.out.println();
System.out.println("后根遍历:");
postOrder(root);
System.out.println();
System.out.println("层次遍历:");
levelOrder(root);
}
// 创建二叉树
public static TreeNode createBinaryTree(String str) {
if (str == null || str.length() == 0) {
return null;
}
TreeNode root = null;
int i = 0;
int len = str.length();
char[] chars = str.toCharArray();
Queue<TreeNode> queue = new LinkedList<>();
while (i < len) {
char ch = chars[i];
if (ch == '(') {
queue.offer(root);
} else if (ch == ')') {
queue.poll();
} else {
TreeNode node = new TreeNode(ch);
if (root == null) {
root = node;
} else {
TreeNode parent = queue.peek();
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
queue.offer(node);
}
i++;
}
return root;
}
// 先根遍历
public static void preOrder(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// 中根遍历
public static void inOrder(TreeNode root) {
if (root != null) {
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
// 后根遍历
public static void postOrder(TreeNode root) {
if (root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
}
// 层次遍历
public static void levelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
```
其中,`createBinaryTree` 方法使用队列实现广义表表示的二叉树的构造,`preOrder`、`inOrder`、`postOrder` 和 `levelOrder` 分别实现了先根、中根、后根和层次遍历算法,可以根据需要调用。
阅读全文