什么是前序遍历介绍

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

前序遍历简介

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

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

（1）访问根结点。

（2）前序遍历左子树。

（3）前序遍历右子树 。

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

如图1所示二叉树

前序遍历结果：ABDECF

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

前序遍历数学表达式形式

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

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

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

前序遍历复杂性

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

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

前序遍历程序实现

前序遍历C语言

树节点结构和算法：

typedef struct TreeNode{    int data;    TreeNode * left;    TreeNode * right;    TreeNode * parent;}TreeNode;void pre_order(TreeNode * Node){    if(Node != NULL)    {        printf(\"%d \", Node->data);        pre_order(Node->left);        pre_order(Node->right);    }}

调用时：

pre_order(Root); //Root为树的根

前序遍历Pascal版本

核心代码：

procedure first(i:longint);

begin

write(a);

if a0 then first(i*2）；

if a0 then first(i*2+1）；

end;

前序遍历Java版本

二叉树定义

publicclassTreeNode{    intval;    TreeNodeleft;    TreeNoderight;    TreeNode(intx){        val=x;    }}

递归实现

publicvoidpreOrder(TreeNodebiTree){    System.out.printf(biTree.val+\"\");    TreeNodeleftTree=biTree.left;    if(leftTree!=null){        preOrder(leftTree);    }    TreeNoderightTree=biTree.right;    if(rightTree!=null){        preOrder(rightTree);    }}

非递归实现

publicvoidpreOrder(TreeNodebiTree){    Stackstack=newStack();    while(biTree!=null||!stack.isEmpty()){        while(node!=null){            System.out.print(biTree.value+\",\");            stack.push(biTree);            biTree=biTree.left;        }        if(!stack.isEmpty()){            biTree=stack.pop();            biTree=biTree.right;        }    }}