java实现二叉树的三种遍历
时间: 2023-11-06 11:03:16 浏览: 51
Java可以通过递归和迭代两种方式实现二叉树的三种遍历:前序遍历、中序遍历和后序遍历。
1. 前序遍历(Preorder Traversal):访问根节点,然后按照先左子树后右子树的顺序递归遍历左右子树。
递归实现:
```java
public void preOrderTraversal(Node root) {
if (root != null) {
System.out.print(root.data + " "); // 访问根节点
preOrderTraversal(root.left); // 递归遍历左子树
preOrderTraversal(root.right); // 递归遍历右子树
}
}
```
2. 中序遍历(Inorder Traversal):先递归遍历左子树,然后访问根节点,最后递归遍历右子树。
递归实现:
```java
public void inOrderTraversal(Node root) {
if (root != null) {
inOrderTraversal(root.left); // 递归遍历左子树
System.out.print(root.data + " "); // 访问根节点
inOrderTraversal(root.right); // 递归遍历右子树
}
}
```
3. 后序遍历(Postorder Traversal):先递归遍历左子树,然后递归遍历右子树,最后访问根节点。
递归实现:
```java
public void postOrderTraversal(Node root) {
if (root != null) {
postOrderTraversal(root.left); // 递归遍历左子树
postOrderTraversal(root.right); // 递归遍历右子树
System.out.print(root.data + " "); // 访问根节点
}
}
```
以上是递归实现方式,也可以使用迭代的方式实现二叉树的遍历,用栈来辅助实现。在遍历过程中,将节点放入栈中,然后按照一定顺序弹出节点进行操作,直到栈为空。