1.概念

二叉树先序遍历（也叫前序遍历）算法分为递归遍历和非递归遍历2种实现方式。

递归遍历容易理解，但可能会占用较大的栈空间，需防止出现栈溢出。

2.代码

以下以Java语言代码作为示例。

二叉树的节点的数据结构如下：

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
    }
}

1）递归遍历

public void preorderTraversalRecursive(TreeNode root) {
		// 若root节点为空，则子遍历已完成
        if (root == null) {
            return;
        }
		// 输出遍历到的节点的值
        System.out.print(root.value + " "); 
		// 遍历左子树
        preorderTraversalRecursive(root.left);  
		// 遍历右子树
        preorderTraversalRecursive(root.right);    
    }

2)非递归遍历

public void preorderTraversalNonRecursive(TreeNode root)
{
	// 此栈存储需要以后处理的节点
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    //节点不为空或者栈不为空时需要继续处理
    while(node != null || !stack.empty())
    {
        while(node != null)
        {
			// 1. 输出遍历到的节点的值
            System.out.println(node.value+" ");
			// 2. 保存根节点（方便之后处理右节点）
            stack.push(node);
			// 3. 找到最左节点
            node = node.left;
        }
 
        
        if(!stack.empty())
        {
			//找到右节点，并回到外层循环继续处理
            node = stack.pop();
            node = node.right;
        }
    }
}

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。