如何用递归和非递归两种方式实现二叉树的先序遍历？

本文共计505个文字，预计阅读时间需要3分钟。

一、分析前序遍历（Pre-order Traversal）是一种树遍历方法，其遍历顺序为：根节点 -> 左子树 -> 右子树。在递归实现中，首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

二、代码实现javapublic class Node { public int value; public Node left; public Node right;

public Node(int data) { this.value=data; }

public void preOrderRecu() { System.out.print(this.value + ); if (this.left !=null) { this.left.preOrderRecu(); } if (this.right !=null) { this.right.preOrderRecu(); } }}

一、分析

先序遍历（前序遍历）遍历顺序为：根、左、右。

二、递归实现

public class Node{ public int value; public Node left; public Node right; public Node(int data){ this.value = data; } } public void preOrderRecur(Node head){ if(head == null){ return; } System.out.println(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right); }

三、非递归实现

3.1 问题分析

用递归方法解决的问题都能用非递归方法实现，这是因为递归方法无非就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。

用递归方式实现二叉树的前序遍历过程如下：

1、申请一个新的栈，记为stack。然后将头节点head压入stack中。

2、从stack中弹出栈顶节点，记为cur，然后打印cur节点的值，再将cur的右子节点（不为空的话）压入栈中，最后将cur的左子节点（不为空的话）压入stack中。

3、不断重复步骤2，直到stack为空，全部过程结束。

代码如下：

public class Node{ public int value; public Node left; public Node right; public Node(int data){ this.value = data; } } public void preOrderunRecur(Node head){ if(head != null){ System.out.println(head.value + " "); Stack<Node> stack = new Stack<Node>; stack.add(head); while(!stack.isEmpty()){ head = stack.pop(); System.out.println(head.value + " "); if(head.right != null){ stack.push(head.right); } if(head.left != null){ stack.push(head.left); } } } System.out.println(); }