[科普中国]-前序遍历

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

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

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

（1）访问根结点。

（2）前序遍历左子树**。**

（3）前序遍历右子树 。

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

如右图所示二叉树

前序遍历结果：ABDECF

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

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

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

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

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

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

程序实现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[i]);

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

if a[i*2+1]0 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; } }}本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学