Java代码实现构造一颗三叉链表表示的二叉树,实现采用先根、中根、后根、层次算法遍历二叉树,输出二叉树字符
时间: 2023-12-24 17:06:06 浏览: 19
好的,以下是 Java 代码实现:
```java
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode parent;
TreeNode(char x) { val = x; }
}
class TriLinkBinaryTree {
private TreeNode root;
public TriLinkBinaryTree(String str) {
root = buildTree(str.toCharArray(), 0, str.length() - 1, null);
}
private TreeNode buildTree(char[] arr, int start, int end, TreeNode parent) {
if (start > end) return null;
TreeNode node = new TreeNode(arr[start]);
node.parent = parent;
int index = start + 1;
while (index <= end && arr[index] <= arr[start]) {
index++;
}
node.left = buildTree(arr, start + 1, index - 1, node);
node.right = buildTree(arr, index, end, node);
return node;
}
public void preOrder() {
preOrder(root);
System.out.println();
}
private void preOrder(TreeNode node) {
if (node == null) return;
System.out.print(node.val + " ");
preOrder(node.left);
preOrder(node.right);
}
public void inOrder() {
inOrder(root);
System.out.println();
}
private void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
System.out.print(node.val + " ");
inOrder(node.right);
}
public void postOrder() {
postOrder(root);
System.out.println();
}
private void postOrder(TreeNode node) {
if (node == null) return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.val + " ");
}
public void levelOrder() {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
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);
}
}
System.out.println();
}
}
```
其中,TreeNode 类表示二叉树的节点,TriLinkBinaryTree 类表示三叉链表表示的二叉树。
使用示例:
```java
TriLinkBinaryTree tree = new TriLinkBinaryTree("DBACEGF");
tree.preOrder(); // D B A C E G F
tree.inOrder(); // A B C D E F G
tree.postOrder(); // A C B E G F D
tree.levelOrder(); // D B F A C E G
```
以上是使用先根、中根、后根、层次算法遍历二叉树,并输出二叉树字符的 Java 代码实现。