使用Java的官方库来实现二叉树
时间: 2023-05-31 10:06:44 浏览: 43
以下是使用Java官方库实现二叉树的代码示例:
```java
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTree {
private TreeNode root;
public void insert(int val) {
if (root == null) {
root = new TreeNode(val);
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll();
if (curr.left == null) {
curr.left = new TreeNode(val);
return;
} else if (curr.right == null) {
curr.right = new TreeNode(val);
return;
} else {
queue.offer(curr.left);
queue.offer(curr.right);
}
}
}
public void inorder() {
inorderHelper(root);
System.out.println();
}
private void inorderHelper(TreeNode node) {
if (node == null) {
return;
}
inorderHelper(node.left);
System.out.print(node.val + " ");
inorderHelper(node.right);
}
public void preorder() {
preorderHelper(root);
System.out.println();
}
private void preorderHelper(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
preorderHelper(node.left);
preorderHelper(node.right);
}
public void postorder() {
postorderHelper(root);
System.out.println();
}
private void postorderHelper(TreeNode node) {
if (node == null) {
return;
}
postorderHelper(node.left);
postorderHelper(node.right);
System.out.print(node.val + " ");
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
System.out.print("Inorder traversal: ");
tree.inorder();
System.out.print("Preorder traversal: ");
tree.preorder();
System.out.print("Postorder traversal: ");
tree.postorder();
}
}
```
在这个实现中,我们使用了Java的Queue接口来实现树的广度优先搜索,当需要插入一个新节点时,我们从根节点开始遍历树,找到第一个有空子节点的节点,将新节点插入到该节点的空子节点中。
我们还实现了三种遍历二叉树的方法(中序遍历、前序遍历和后序遍历),它们都是递归的实现方式。我们可以在main方法中创建一个BinaryTree对象,并使用insert方法向树中插入节点。最后,我们使用inorder、preorder和postorder方法来遍历树。