递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。
二叉树图
定义
-
前序遍历（Preorder Traversal）： 前序遍历的顺序是先访问根节点，然后按照先左后右的顺序访问子节点。对于上面的二叉树，前序遍历的结果是：4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7。
-
中序遍历（Inorder Traversal）： 中序遍历的顺序是按照先左后根再右的顺序访问子节点。对于上面的二叉树，中序遍历的结果是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
-
后序遍历（Postorder Traversal）： 后序遍历的顺序是按照先左后右再根的顺序访问子节点。对于上面的二叉树，后序遍历的结果是：1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4。
通俗易懂
如果上面的定义看着有点晕，看这里，如上图，在这三个节点中，观察根节点2的遍历位置
前序遍历：213
中序遍历：123
后序遍历：132
总结：不管哪个遍历方式，左右相比，都是左先，1在前，3在后，根节点2依次是前、中、后，递归时把子树看成整体，逻辑同理。
代码
public class BinaryTree {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7};
TreeNode root = TreeNode.buildTree(nums);
System.out.print("前序遍历（递归）：");
preorderTraversal(root);
System.out.println();
System.out.print("中序遍历（递归）：");
inorderTraversal(root);
System.out.println();
System.out.print("后序遍历（递归）：");
postorderTraversal(root);
System.out.println();
System.out.print("前序遍历（栈）：");
preorderTraversal1(root);
System.out.println();
System.out.print("中序遍历（栈）：");
inorderTraversal1(root);
System.out.println();
System.out.print("后序遍历（栈）：");
postorderTraversal1(root);
System.out.println();
}
//前序遍历(递归)
public static void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " "); // 访问根节点
preorderTraversal(root.left); // 访问左子树
preorderTraversal(root.right); // 访问右子树
}
// 中序遍历(递归)
public static void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left); // 访问左子树
System.out.print(root.val + " "); // 访问根节点
inorderTraversal(root.right); // 访问右子树
}
// 后序遍历(递归)
public static void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
postorderTraversal(root.left); // 访问左子树
postorderTraversal(root.right); // 访问右子树
System.out.print(root.val + " "); // 访问根节点
}
// 前序遍历(栈)
public static void preorderTraversal1(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> 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 static void inorderTraversal1(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left; // 先将左子节点入栈
}
node = stack.pop();
System.out.print(node.val + " "); // 打印当前节点的值
node = node.right; // 再处理右子节点
}
}
// 后序遍历(栈)
public static void postorderTraversal1(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
if (node.left != null) {
stack1.push(node.left); // 先将左子节点入栈
}
if (node.right != null) {
stack1.push(node.right); // 再将右子节点入栈
}
stack2.push(node); // 将当前节点入栈（用于后序遍历）
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " "); // 打印栈中的节点值（即后序遍历结果）
}
}
}TreeNode
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
// 构建二叉树
public static TreeNode buildTree(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return buildTree(nums, 0, nums.length - 1);
}
private static TreeNode buildTree(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, left, mid - 1);
root.right = buildTree(nums, mid + 1, right);
return root;
}
}文章来源：https://www.toymoban.com/news/detail-626073.html
运行结果
前序遍历（递归）：4 2 1 3 6 5 7
中序遍历（递归）：1 2 3 4 5 6 7
后序遍历（递归）：1 3 2 5 7 6 4
前序遍历（栈）：4 2 1 3 6 5 7
中序遍历（栈）：1 2 3 4 5 6 7
后序遍历（栈）：1 3 2 5 7 6 4 文章来源地址https://www.toymoban.com/news/detail-626073.html
到了这里，关于【数据结构|二叉树遍历】递归与非递归实现前序遍历、中序遍历、后序遍历的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
