前序遍历（VLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

若二叉树为空则结束返回，否则：

（1）访问根结点。

（2）前序遍历左子树。

（3）前序遍历右子树 。

需要注意的是：遍历左右子树时仍然采用前序遍历方法。

如图1所示二叉树

前序遍历结果：ABDECF

已知后序遍历和中序遍历，就能确定前序遍历。

当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。

在后缀（postfix）表达式中，每个操作符跟在操作数之后，操作数按从左到右的顺序出现。在前缀（prefix）表达式中，操作符位于操作数之前。在前缀和后缀表达式中不会存在歧义。

因此，在前缀和后缀表达式中都不必采用括号或优先级。从左到右或从右到左扫描表达式并采用操作数栈，可以很容易确定操作数和操作符的关系。若在扫描中遇到一个操作数，把它压入堆栈，若遇到一个操作符，则将其与栈顶的操作数相匹配。把这些操作数推出栈，由操作符执行相应的计算，并将所得结果作为操作数压入堆栈。

设二叉树中元素数目为n。这四种遍历算法的空间复杂性均为O (n)，时间复杂性为O(n)。

当t 的高度为n时(右斜二叉树的情况)，通过观察其前序、中序和后序遍历时所使用的递归栈空间即可得到上述结论。

树节点结构和算法：

调用时：

核心代码：

procedure first(i:longint);

begin

write(a[i]);

if a[i*2]0 then first(i*2）；

if a[i*2+1]0 then first(i*2+1）；

end;

二叉树定义

递归实现

非递归实现