java线索二叉树遍历怎么实现

在Java中，可以使用递归或迭代的方式实现二叉树的遍历。下面分别介绍这两种方法。

1. 递归遍历：

递归遍历二叉树的过程非常简单，可以按照先序、中序和后序的顺序递归遍历二叉树。

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 先序遍历
public void preorderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}
// 中序遍历
public void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
}
// 后序遍历
public void postorderTraversal(TreeNode root) {
if (root != null) {
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.val + " ");
}
}

2. 迭代遍历：

迭代遍历二叉树使用栈来记录遍历的节点。具体步骤如下：

import java.util.Stack;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 先序遍历
public void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
// 中序遍历
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
System.out.print(curr.val + " ");
curr = curr.right;
}
}
// 后序遍历
public void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}

以上就是Java实现二叉树遍历的方法，根据不同的需求选择递归或迭代的方式来遍历二叉树。