百度站长工具官网,购物网站排名2018,网络规划设计师属于什么职称,可以仿做网站吗二叉树遍历是指按照某种顺序访问二叉树的所有节点。常见的二叉树遍历方式包括前序遍历#xff08;Preorder Traversal#xff09;、中序遍历#xff08;Inorder Traversal#xff09;、后序遍历#xff08;Postorder Traversal#xff09;和层次遍历#xff08;Level-or…二叉树遍历是指按照某种顺序访问二叉树的所有节点。常见的二叉树遍历方式包括前序遍历Preorder Traversal、中序遍历Inorder Traversal、后序遍历Postorder Traversal和层次遍历Level-order Traversal。不同的遍历方式有不同的应用场景下面我们详细介绍这几种遍历方式及其实现。
1. 前序遍历Preorder Traversal
在前序遍历中按照“根节点 - 左子树 - 右子树”的顺序遍历二叉树的节点。即首先访问根节点然后递归地遍历左子树最后递归地遍历右子树。
前序遍历的顺序
当前节点 - 左子节点 - 右子节点前序遍历的递归实现
// 定义二叉树节点
class TreeNode {int val;TreeNode left, right;TreeNode(int val) {this.val val;this.left this.right null;}
}public class BinaryTreeTraversal {// 前序遍历 - 递归实现public void preorder(TreeNode root) {if (root null) {return;}System.out.print(root.val ); // 访问根节点preorder(root.left); // 递归遍历左子树preorder(root.right); // 递归遍历右子树}
}前序遍历的非递归实现
可以用栈模拟递归的过程先访问根节点然后将右子树和左子树依次压栈确保左子树先被遍历。
import java.util.Stack;public class BinaryTreeTraversal {// 前序遍历 - 非递归实现public void preorderIterative(TreeNode root) {if (root null) {return;}StackTreeNode 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); // 左子树入栈}}}
}2. 中序遍历Inorder Traversal
在中序遍历中按照“左子树 - 根节点 - 右子树”的顺序遍历二叉树的节点。即首先递归地遍历左子树然后访问根节点最后递归地遍历右子树。
中序遍历的顺序
左子节点 - 当前节点 - 右子节点中序遍历的递归实现
public class BinaryTreeTraversal {// 中序遍历 - 递归实现public void inorder(TreeNode root) {if (root null) {return;}inorder(root.left); // 递归遍历左子树System.out.print(root.val ); // 访问根节点inorder(root.right); // 递归遍历右子树}
}中序遍历的非递归实现
同样可以使用栈来实现先遍历到最左边的节点然后逐步回溯访问根节点最后遍历右子树。
import java.util.Stack;public class BinaryTreeTraversal {// 中序遍历 - 非递归实现public void inorderIterative(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. 后序遍历Postorder Traversal
在后序遍历中按照“左子树 - 右子树 - 根节点”的顺序遍历二叉树的节点。即首先递归地遍历左子树然后递归地遍历右子树最后访问根节点。
后序遍历的顺序
左子节点 - 右子节点 - 当前节点后序遍历的递归实现
public class BinaryTreeTraversal {// 后序遍历 - 递归实现public void postorder(TreeNode root) {if (root null) {return;}postorder(root.left); // 递归遍历左子树postorder(root.right); // 递归遍历右子树System.out.print(root.val ); // 访问根节点}
}后序遍历的非递归实现
后序遍历较复杂需要两个栈一个用于模拟递归另一个用于输出结果。
import java.util.Stack;public class BinaryTreeTraversal {// 后序遍历 - 非递归实现public void postorderIterative(TreeNode root) {if (root null) {return;}StackTreeNode stack new Stack();StackTreeNode output new Stack();stack.push(root);while (!stack.isEmpty()) {TreeNode node stack.pop();output.push(node);if (node.left ! null) {stack.push(node.left); // 左子树入栈}if (node.right ! null) {stack.push(node.right); // 右子树入栈}}while (!output.isEmpty()) {System.out.print(output.pop().val ); // 输出结果}}
}4. 层次遍历Level-order Traversal
层次遍历是按照每一层节点的顺序从上到下从左到右依次遍历二叉树的节点。可以通过队列实现每次从队列中取出一个节点然后将其左右子节点依次加入队列。
层次遍历的顺序
按照从上到下、从左到右的层次顺序遍历节点层次遍历的实现
import java.util.LinkedList;
import java.util.Queue;public class BinaryTreeTraversal {// 层次遍历 - 使用队列实现public void levelOrder(TreeNode root) {if (root null) {return;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {TreeNode node queue.poll();System.out.print(node.val ); // 访问当前节点if (node.left ! null) {queue.offer(node.left); // 左子节点入队}if (node.right ! null) {queue.offer(node.right); // 右子节点入队}}}
}四种遍历的总结
前序遍历Preorder Traversal根 - 左 - 右通常用于复制树。中序遍历Inorder Traversal左 - 根 - 右通常用于输出升序排序对二叉搜索树。后序遍历Postorder Traversal左 - 右 - 根通常用于删除树或者计算子树的大小。层次遍历Level-order Traversal按层次顺序遍历常用于广度优先搜索。
这些遍历方式各有特点应用于不同的场景。
