Java代码实现创建一棵二叉链表表示的二叉树中,实现输入叶子结点操作,并分别采用先根、中根、后根、层次遍历算法
时间: 2024-01-12 10:04:31 浏览: 76
Java实现二叉树的层次遍历
好的,以下是 Java 代码实现:
首先,我们需要定义二叉树的节点类,包含节点的值、左子节点和右子节点:
```
class BinaryTreeNode {
int val;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
```
接下来,我们需要实现输入叶子节点的操作,即在二叉树中添加新的节点。我们可以通过递归的方式,在二叉树中找到一个空缺的位置,并添加新的节点:
```
public static void addLeaf(BinaryTreeNode root, int val) {
if (root == null) {
return;
}
if (root.left == null) {
root.left = new BinaryTreeNode(val);
return;
}
if (root.right == null) {
root.right = new BinaryTreeNode(val);
return;
}
addLeaf(root.left, val);
addLeaf(root.right, val);
}
```
这里我们传入的参数是二叉树的根节点和要添加的叶子节点的值。如果根节点为空,直接返回。如果根节点的左子节点为空,添加新的节点作为左子节点。如果根节点的右子节点为空,添加新的节点作为右子节点。否则,递归地在左子树和右子树中查找空缺的位置,并添加新的节点。
接下来,我们分别采用先根、中根、后根、层次遍历算法来遍历二叉树。
先根遍历算法:
```
public static void preOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
```
中根遍历算法:
```
public static void inOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
```
后根遍历算法:
```
public static void postOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
```
层次遍历算法:
```
public static void levelOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
Queue<BinaryTreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
BinaryTreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
```
下面是一个完整的示例代码:
```
import java.util.*;
public class BinaryTree {
public static void main(String[] args) {
BinaryTreeNode root = new BinaryTreeNode(1);
addLeaf(root, 2);
addLeaf(root, 3);
addLeaf(root, 4);
addLeaf(root, 5);
addLeaf(root, 6);
addLeaf(root, 7);
addLeaf(root, 8);
System.out.print("先根遍历:");
preOrder(root);
System.out.println();
System.out.print("中根遍历:");
inOrder(root);
System.out.println();
System.out.print("后根遍历:");
postOrder(root);
System.out.println();
System.out.print("层次遍历:");
levelOrder(root);
System.out.println();
}
public static void addLeaf(BinaryTreeNode root, int val) {
if (root == null) {
return;
}
if (root.left == null) {
root.left = new BinaryTreeNode(val);
return;
}
if (root.right == null) {
root.right = new BinaryTreeNode(val);
return;
}
addLeaf(root.left, val);
addLeaf(root.right, val);
}
public static void preOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
public static void inOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
public static void postOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
public static void levelOrder(BinaryTreeNode root) {
if (root == null) {
return;
}
Queue<BinaryTreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
BinaryTreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
static class BinaryTreeNode {
int val;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
}
```
在这个示例代码中,我们创建了一棵二叉树,并添加了8个叶子节点。然后分别采用先根、中根、后根、层次遍历算法遍历二叉树,输出遍历结果。你可以根据自己的需求修改节点的值和数量。
阅读全文