ftp上传网站全教程,凡科做的网站为什么打不开,中国企业500强排行榜完整榜单,wordpress中文广告插件二叉树的遍历是二叉树操作中的一个基本且重要的概念#xff0c;它指的是按照一定的规则访问二叉树中的每个节点#xff0c;并且每个节点仅被访问一次。常见的二叉树遍历方式有四种#xff1a;前序遍历#xff08;Pre-order Traversal#xff09;、中序遍历#xff08;In-…二叉树的遍历是二叉树操作中的一个基本且重要的概念它指的是按照一定的规则访问二叉树中的每个节点并且每个节点仅被访问一次。常见的二叉树遍历方式有四种前序遍历Pre-order Traversal、中序遍历In-order Traversal、后序遍历Post-order Traversal和层序遍历Level-order Traversal。
1. 前序遍历Pre-order Traversal
前序遍历的顺序是根节点 - 左子树 - 右子树。对于每个节点都遵循这个顺序进行遍历。
递归实现 void preorderTraversal(TreeNode root) { if (root null) return; System.out.print(root.val ); // 访问根节点 preorderTraversal(root.left); // 遍历左子树 preorderTraversal(root.right); // 遍历右子树
} 非递归迭代实现使用栈 void preorderTraversalIterative(TreeNode root) { StackTreeNode stack new Stack(); if (root ! null) 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); }
} 2. 中序遍历In-order Traversal 中序遍历的顺序是左子树 - 根节点 - 右子树。这常用于二叉搜索树BST中因为这样可以得到一个有序的节点序列。 递归实现 void inorderTraversal(TreeNode root) { if (root null) return; inorderTraversal(root.left); // 遍历左子树 System.out.print(root.val ); // 访问根节点 inorderTraversal(root.right); // 遍历右子树
} 非递归迭代实现使用栈 void inorderTraversalIterative(TreeNode root) { StackTreeNode 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; // 转向右子树 }
} 3. 后序遍历Post-order Traversal 后序遍历的顺序是左子树 - 右子树 - 根节点。 递归实现 void postorderTraversal(TreeNode root) { if (root null) return; postorderTraversal(root.left); // 遍历左子树 postorderTraversal(root.right); // 遍历右子树 System.out.print(root.val ); // 访问根节点
} 非递归迭代实现使用栈 void postorderTraversalIterative(TreeNode root) { StackTreeNode stack new Stack(); TreeNode prev null; // 用于记录上一次访问的节点 while (root ! null || !stack.isEmpty()) { while (root ! null) { stack.push(root); root root.left; // 遍历到最左节点 } root stack.peek(); // 弹出栈顶元素但不移除 // 如果右子树为空或者右子树已经访问过则访问当前节点 if (root.right null || root.right prev) { stack.pop(); System.out.print(root.val ); // 访问节点 prev root; root null; // 回到上层循环检查是否有其他节点需要访问 } else { root root.right; // 否则转向右子树 } }
} 4. 层序遍历 非递归迭代实现使用队列 import java.util.LinkedList;
import java.util.Queue; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; }
} public class BinaryTreeLevelOrderTraversal { public void levelOrderTraversal(TreeNode root) { if (root null) return; QueueTreeNode queue new LinkedList(); queue.offer(root); // 将根节点加入队列 while (!queue.isEmpty()) { TreeNode currentNode queue.poll(); // 从队列中取出一个节点 System.out.print(currentNode.val ); // 访问该节点 // 如果左子节点不为空则将其加入队列 if (currentNode.left ! null) { queue.offer(currentNode.left); } // 如果右子节点不为空则将其加入队列 if (currentNode.right ! null) { queue.offer(currentNode.right); } } }
} 非递归迭代实现 实际上层序遍历不常使用递归实现因为递归本质上是栈的操作而层序遍历需要的是队列。但我们可以借助一些额外的数据结构如数组或链表来模拟层序遍历的效果但这通常不是推荐的做法因为它违背了层序遍历的本意。
