本文共 4353 字，大约阅读时间需要 14 分钟。

题目

用递归和非递归的方式，分别按照二叉树先序、中序和后序打印所有的节点。我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。

解答

用递归实现三种遍历是最基本的内容

先序遍历的递归实现

/**       * 二叉树先序递归遍历       */      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);      }

中序遍历的递归实现

/**       * 二叉树中序递归遍历       */      public class Node{            public int value;            public Node left;            public Node right;                        public Node(int data){                  this.value = data;            }      }      public void inOrderRecur(Node head){            if(head == null){                  return ;            }            inOrderRecur(head.left);            System.out.println(head.value+"");            inOrderRecur(head.right);      }

后遍历的递归实现

/**       * 二叉树后序递归遍历       */      public class Node{            public int value;            public Node left;            public Node right;                        public Node(int data){                  this.value = data;            }      }      public void posOrderRecur(Node head){            if(head == null){                  return ;            }            posOrderRecur(head.left);            posOrderRecur(head.right);            System.out.println(head.value+"");      }

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

非递归的方式实现二叉树的先序遍历，具体过程如下：

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

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

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

/**       * 非递归先序遍历       */      public void preOrderUnRecur(Node head){            if(head!=null){                  Stack
   
     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节点为头的整棵子树5来说，依次把左边界压入栈中，即不断地令cur=cur.left，然后重复步骤2。

3. 不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点，记做node。打印node的值，并且让cur=node.right，然后继续重复步骤2。

4. 当stack为空且cur为空时整个过程停止。

/**       * 非递归中序遍历       */      public void preOrderUnRecur(Node head){            if(head!=null){                  Stack
   
     stack = new Stack
    
     ();                  while(!stack.isEmpty()||head!=null){                        if(head!=null){                              stack.push(head);                              head=head.left;                        }else{                              head=stack.pop();                              System.out.println(head.value+"");                              head=head.right;                        }                  }            }            System.out.println("");      }
    
   

非递归的方式实现二叉树的后序遍历，具体过程如下：

1. 申请一个栈记做s1然后将头节点压入s1中。

2. 从s1中弹出的节点记做cur,然后依次将cur的左孩子和右孩子压入s1中。

3. 在整个过程中，每一个从s1中弹出的节点都放到s2中。

4. 不断重复步骤2和步骤3，直到s1为空，过程停止。

5. 从s2中弹出节点并打印。

/**       * 非递归后序遍历       */      public void preOrderUnRecur(Node head){            if(head!=null){                  Stack
   
     s1 = new Stack
    
     ();                  Stack
     
       s2 = new Stack
      
       ();                  s1.push(head);                  while(!s1.isEmpty()){                        head=s1.pop();                        s2.push(head);                        if(head.left!=null){                              s1.push(head.left);                        }                        if(head.right!=null){                              s1.push(head.right);                        }                  }                  while(!s2.isEmpty()){                        System.out.println(s2.pop().value+"");                  }            }            System.out.println("");      }
      
     
    
   

参考资料：《程序员面试代码指南》左程云 著