当前位置：首页 > news >正文

网站开发公司的职责贵州seo推广

news 2026/4/7 19:48:11

网站开发公司的职责,贵州seo推广,做这种灰色的网站犯法,陕西省住房和建设厅官方网站二叉树的遍历是二叉树操作中的一个基本且重要的概念，它指的是按照一定的规则访问二叉树中的每个节点，并且每个节点仅被访问一次。常见的二叉树遍历方式有四种：前序遍历（Pre-order Traversal）、中序遍历（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) {  Stack<TreeNode> 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) {  Stack<TreeNode> 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) {  Stack<TreeNode> 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;  Queue<TreeNode> 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);  }  }  }  
}