建网站 方法,喜来健cms系统,嘉兴简单建站,vs做网站各种控件的使用在 Java 中#xff0c;可以通过递归或使用栈来实现二叉树的前序遍历。下面分别给出这两种方法的实现示例#xff1a;
递归实现前序遍历#xff1a;
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;this.left null;this.right …在 Java 中可以通过递归或使用栈来实现二叉树的前序遍历。下面分别给出这两种方法的实现示例
递归实现前序遍历
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;this.left null;this.right null;}
}public class BinaryTreeTraversal {// 前序遍历递归函数public void preOrderTraversal(TreeNode root) {if (root null) {return;}System.out.print(root.val ); // 先访问根节点preOrderTraversal(root.left); // 递归遍历左子树preOrderTraversal(root.right); // 递归遍历右子树}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);// 创建 BinaryTreeTraversal 对象BinaryTreeTraversal traversal new BinaryTreeTraversal();// 调用前序遍历方法System.out.print(前序遍历结果: );traversal.preOrderTraversal(root);}
}
使用栈实现前序遍历
import java.util.Stack;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;this.left null;this.right null;}
}public class BinaryTreeTraversal {// 使用栈实现前序遍历public void preOrderTraversal(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);}}}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);// 创建 BinaryTreeTraversal 对象BinaryTreeTraversal traversal new BinaryTreeTraversal();// 调用前序遍历方法System.out.print(前序遍历结果: );traversal.preOrderTraversal(root);}
}
无论使用递归还是栈前序遍历都是先访问根节点再访问左子树最后访问右子树。以上两种方法都可以实现二叉树的前序遍历。
