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

• 中文名称 前序遍历
• 外文名称 Preorder Traversal (DLR)
• 应用学科 计算机科学
• 别称 先根遍历、先序遍历、前序周游
• 时间复杂性 O (n) 

简介

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

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

　　(1)访问根结点。

　　(2)前序遍历左子树。

　　(3)前序遍历右子树 。

前序遍历

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

　　如右图所示二叉树

　　前序遍历结果:ABDECF

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

数学表达式形式

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

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

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

复杂性

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

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

程序实现

C语言

　　树节点结构和算法:

　　调用时:

Pascal版本

　　核心代码:

　　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;

Java版本

　　二叉树定义

　　递归实现

　　非递归实现