java完全二叉树先序遍历
时间: 2025-01-08 16:04:03 浏览: 10
Java 实现完全二叉树先序遍历
在Java中实现完全二叉树的先序遍历时,可以采用递归方法或非递归方法。以下是两种不同的实现方式。
方法一:递归实现
递归实现较为直观简单,按照访问根节点、左子树再右子树的原则进行操作[^2]:
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int item) {
val = item;
left = right = null;
}
}
public class BinaryTree {
private void preOrderRecursive(TreeNode root, List<Integer> result) {
if (root != null) {
result.add(root.val);
preOrderRecursive(root.left, result);
preOrderRecursive(root.right, result);
}
}
public List<Integer> preorderTraversalRecursive(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
preOrderRecursive(root, resultList);
return resultList;
}
}
此代码片段展示了如何利用递归来完成先序遍历的任务。对于每一个被访问到的节点,程序会首先记录下它的值,接着尝试去探索其左侧分支,最后才转向右侧分支[^1]。
方法二:非递归实现(基于栈)
当不希望使用函数调用堆栈来进行递归时,可以选择手动管理一个显式的Stack
对象来辅助完成同样的工作流程[^3]:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTreeNonRecursive {
public List<Integer> preorderTraversalIterative(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val); // 访问当前节点
// 注意这里的顺序很重要,因为栈是LIFO(last-in-first-out),所以应该先压入右边再左边
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
}
return list;
}
}
这段代码通过维护自己的栈结构,在不需要额外依赖于语言层面的支持情况下完成了相同的功能。每次从栈顶取出元素并处理它之后,都会立即将它的孩子按特定顺序重新加入到栈里等待后续处理[^4]。