Java

Java二叉树的四种遍历方式详解

小云
106
2023-08-15 14:37:38
栏目: 编程语言

Java二叉树的四种遍历方式分别为:前序遍历、中序遍历、后序遍历和层序遍历。下面对每种遍历方式进行详细介绍:

  1. 前序遍历(Preorder Traversal):

前序遍历的顺序是先访问根节点,然后是左子树,最后是右子树。具体实现方式如下:

public void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
  1. 中序遍历(Inorder Traversal):

中序遍历的顺序是先访问左子树,然后是根节点,最后是右子树。具体实现方式如下:

public void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
  1. 后序遍历(Postorder Traversal):

后序遍历的顺序是先访问左子树,然后是右子树,最后是根节点。具体实现方式如下:

public void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.val + " ");
}
  1. 层序遍历(Level Order Traversal):

层序遍历按照从上到下、从左到右的顺序逐层访问二叉树的节点。具体实现方式如下:

public void levelOrderTraversal(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);
}
}
}

以上是Java二叉树的四种遍历方式的详细介绍和实现代码。这些遍历方式在处理二叉树问题时非常常见,熟练掌握它们可以帮助我们更好地理解和解决相关问题。

0
看了该问题的人还看了