递归算法实现二叉树先序遍历
时间: 2025-01-13 09:33:24 浏览: 8
递归实现二叉树先序遍历
定义节点类
为了构建二叉树并对其进行操作,定义一个简单的 TreeNode
类用于表示二叉树中的节点。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
this.val = x;
this.left = null;
this.right = null;
}
}
实现先序遍历方法
先序遍历遵循访问根节点 -> 访问左子树 -> 访问右子树的原则。下面展示了如何利用递归来完成这一过程[^1]:
public class BinaryTreePreorderTraversal {
// 先序遍历函数
public void preorder(TreeNode root) {
if (root == null) return; // 如果当前节点为空,则直接返回
System.out.print(root.val + " "); // 输出当前节点值
preorder(root.left); // 对左子树执行相同的操作
preorder(root.right); // 对右子树执行相同的操作
}
}
此代码片段实现了对给定二叉树的先序遍历,并打印出各个节点的数据。当遇到空节点时停止进一步深入;否则依次处理三个部分——首先是当前节点本身,接着是其左侧分支最后才是右侧分支[^3]。