java treenode如何实现遍历
导读：在Java中，可以使用递归或迭代方法来遍历二叉树（TreeNode）。下面是两种遍历方法的示例： 递归方法： class TreeNode { int val; TreeNode left; TreeNode r...
在Java中，可以使用递归或迭代方法来遍历二叉树（TreeNode）。下面是两种遍历方法的示例：
- 递归方法：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class BinaryTreeTraversal {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println("前序遍历：");
preorderTraversal(root);
System.out.println("\n中序遍历：");
inorderTraversal(root);
System.out.println("\n后序遍历：");
postorderTraversal(root);
}
public static void preorderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
preorderTraversal(node.left);
preorderTraversal(node.right);
}
public static void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
System.out.print(node.val + " ");
inorderTraversal(node.right);
}
public static void postorderTraversal(TreeNode node) {
if (node == null) {
return;
}
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.print(node.val + " ");
}
}
- 迭代方法（使用栈）：
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class BinaryTreeTraversal {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println("前序遍历：");
preorderTraversal(root);
System.out.println("\n中序遍历：");
inorderTraversal(root);
System.out.println("\n后序遍历：");
postorderTraversal(root);
}
public static void preorderTraversal(TreeNode node) {
if (node == null) {
return;
}
Stack<
TreeNode>
stack = new Stack<
>
();
stack.push(node);
while (!stack.isEmpty()) {
TreeNode currentNode = stack.pop();
System.out.print(currentNode.val + " ");
if (currentNode.right != null) {
stack.push(currentNode.right);
}
if (currentNode.left != null) {
stack.push(currentNode.left);
}
}
}
public static void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
Stack<
TreeNode>
stack = new Stack<
>
();
TreeNode currentNode = node;
while (currentNode != null || !stack.isEmpty()) {
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
System.out.print(currentNode.val + " ");
currentNode = currentNode.right;
}
}
public static void postorderTraversal(TreeNode node) {
if (node == null) {
return;
}
Stack<
TreeNode>
stack1 = new Stack<
>
();
Stack<
TreeNode>
stack2 = new Stack<
>
();
stack1.push(node);
while (!stack1.isEmpty()) {
TreeNode currentNode = stack1.pop();
stack2.push(currentNode);
if (currentNode.left != null) {
stack1.push(currentNode.left);
}
if (currentNode.right != null) {
stack1.push(currentNode.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}
}
这两种方法分别实现了前序遍历、中序遍历和后序遍历。你可以根据需要选择合适的方法来遍历二叉树。
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： java treenode如何实现遍历
本文地址： https://pptw.com/jishu/709906.html