|
题目：用递归和非递归两种方式，分别按照二叉树先序、中序和后序打印所有的节点。我们约定先遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历为左、右、根。
解答：用递归方式实现是基本的解题方法，此处直接给出代码
先序：
其实在遍历二叉树的时候有三次遍历， 比如前序遍历：A->B->D->D(D左子节点并返回到D)->D(D右子节点并返回到D)->B->E->E(左)->E(右)->->B->A->C->F->F(左)->F(右)->C->C(右)，所以可以用栈结构，把遍历到的节点压进栈，没子节点时再出栈。也可以用递归的方式，递归的输出当前节点，然后递归的输出左子节点，最后递归的输出右子节点。直接看代码更能理解：
public static void preOrderRe(TreeNode biTree)
{//递归实现
System.out.println(biTree.value);
TreeNode leftTree = biTree.left;
if(leftTree != null)
{
preOrderRe(leftTree);
}
TreeNode rightTree = biTree.right;
if(rightTree != null)
{
preOrderRe(rightTree);
}
}
中序：
public static void midOrderRe(TreeNode biTree)
{//中序遍历递归实现
if(biTree == null)
return;
else
{
midOrderRe(biTree.left);
System.out.println(biTree.value);
midOrderRe(biTree.right);
}
}
后序：
public static void postOrderRe(TreeNode biTree)
{//后序遍历递归实现
if(biTree == null)
return;
else
{
postOrderRe(biTree.left);
postOrderRe(biTree.right);
System.out.println(biTree.value);
}
}
用递归方法解决的问题都能用非递归实现，这是因为递归方法无非就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。
用非递归的方式实现二叉树的先序遍历，具体过程如下：
1.申请一个新的栈，记为stack。然后将头节点head压入栈中。
2.从stack中弹出栈顶节点，记为cur,然后打印cur节点的值，再将节点cur的右孩子（不为空的话）先压入栈中，最后将cur的左孩子（不为空的话）压入stack中。
3.不断的重复2，直到stack为空，全部过程结束。
public void preOrderUnRecur(Node head){
System.out.println("pre-Order");
if(head != null){
Stack<Node> stack = new Stack<>();
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();
}
用非递归的方式实现二叉树的中序遍历，具体过程如下：
1.申请一个新的栈，记为stack.初始时，令变量为cur = head.
2.先把cur节点压入栈中，对以cur节点为头的整颗子树来说，依次把左边界压入栈中，，即不停的令cur=cur.left，然后重复步骤2.
3.不断重复步骤2，直到发现cur为空，此时从stack中，弹出一个节点，记为node。打印node的值，并且让cur=node.right，然后继续重复步骤2.
4.当stack为空时，整个过程停止。
public void inOrderUnRecur(Node head){
System.out.println("in-order");
if(head != null){
Stack<Node> stack = new Stack<>();
while(!stack.isEmpty() || head != null){
if(head != null){
stack.push(head);
head= head.left;
}else{
head = stack.pop();
System.out.print(head.value+" ");
head = head.right;
}
}
}
System.out.println();
}
用非递归的方式实现二叉树的后序遍历。
1.申请一个栈，记为s1，然后将头节点head压入s1中。
2.从s1中弹出的节点记为cur，然后依次将cur的左孩子和右孩子压入栈中。
3.在整个过程中，每一个s1中弹出的节点都放入s2中。
4.不断的重复步骤2和步骤3，直到s1为空，过程停止。
5.从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。
public void posOrderUnRecur(Node head){
System.out.println("pos-Order");
if(head != null){
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(head);
while(!s1.isEmpty()){
head= s1.pop();
s2.push(head);
if(head.left !=null){
s1.push(head.left);
}
if(head.right !=null){
s2.push(head.right);
}
}
while(!s2.isEmpty()){
System.out.print(head.value+" ");
}
}
System.out.println();
}
| 
转播
