算法之二叉树遍历

二叉树遍历可以使用深度优先周游二叉树和广度优先周游二叉树，深度优先又可以分为前序、中序、后序三种方式遍历，每种方式都可以通过递归和非递归方法实现。

1.深度优先递归遍历：

前序递归遍历算法：访问根结点→递归遍历根结点的左子树→递归遍历根结点的右子树

中序递归遍历算法：递归遍历根结点的左子树→访问根结点→递归遍历根结点的右子树

后序递归遍历算法：递归遍历根结点的左子树 →递归遍历根结点的右子树→访问根结点

题目：通过代码实现上述二叉树的前序、中序、后序遍历

首先分析一下，二叉树的每个结点都有三个属性：

结点值、左结点、右结点

下面我们定义结点类：TreeNode,代码如下

public class TreeNode<T>{
    private T data;
    private TreeNode<T> left;
    private TreeNode<T> right;
  
  public TreeNode(T data,TreeNode<T> left,TreeNode<T> right){
      this.data = data;
      this.left = left;
      this.right = right;
  }
}

下面在定义一个BinaryTreeManager 管理类，通过这个类实现前序、中序、后序递归遍历。代码如下

public class BinaryTreeManager<T>{
    private List<T> list = new ArrayList<T>();
    //前序遍历
    public List<T> preTreeNode(TreeNode<T> node){
      list.add(node.data);
      if(node.left  != null){
         preTreeNode(node.left);
      }
      if(node.right != null){
         preTreeNode(node.right);
      }
      return list;
  }
    //中序遍历
    public List<T> inTreeNode(TreeNode<T> node){
      if(node.left  != null){
         preTreeNode(node.left);
      }
     list.add(node.data);
      if(node.right != null){
         preTreeNode(node.right);
      }
      return list;
    }
    //后序遍历
    public List<T> lastTreeNode(TreeNode<T> node){
      if(node.left  != null){
         preTreeNode(node.left);
      }
      if(node.right != null){
         preTreeNode(node.right);
      }
      list.add(node.data);
      return list;
    }
}

最后创建一个测试类，代码如下：

  public class Test{
      public static void main(String[] args){
        TreeNode<Integer> node31 = new TreeNode<>(1,null,null);
        TreeNode<Integer> node32 = new TreeNode<>(4,null,null);
        TreeNode<Integer> node33 = new TreeNode<>(6,null,null);
        TreeNode<Integer> node34 = new TreeNode<>(9,null,null);
        TreeNode<Integer> node21 = new TreeNode<>(3,node31,node32);
        TreeNode<Integer> node22 = new TreeNode<>(7,node33,node34);
        TreeNode<Integer> nodeRoot= new TreeNode<>(5,node21,node22);
        BinaryTreeManager manager = new BinaryTreeManager();
        //前序遍历
        List<Integer> list1 = manager.preTreeNode(nodeRoot);
        //中序遍历
        List<Integer> list2 = manager.inTreeNode(nodeRoot);
        //后序遍历
        List<Integer> list3 = manager.lastTreeNode(nodeRoot);
        System.out.println("前序：" + list1);
        System.out.println("中序：" + list2);
        System.out.println("后序：" + list3);
    }
}

打印结果如下：

前序：[5,3,1,4,7,6,9]
中序：[1,3,4,5,6,7,9]
后序：[1,4,3,6,9,7,5]

这三个方法是递归遍历二叉树的实现，也可以说成是深度优先周游二叉树，深度优先的意思是尽可能地沿分支结点向深度方向进行周游。对于二叉树来说深度优先周游即先沿着分支结点向左下降，当遇到左子树为空时，返回到上面最近的且其右子树尚未访问到的分支结点，转向该分支结点的右子结点，然后再尽可能地沿着左链前进。重复执行上述过程，直到周游完所有的结点为止。

2.深度优先非递归遍历:

如果要求不能使用递归，又该怎么做呢？

非递归前序周游算法的主要思想是：每遇到一个结点，先访问该结点，并把该结点的非空右子结点推入栈中，然后周游其左子树；左子树周游不下去的时候，从栈中弹出栈顶的结点，继续周游。算法执行过程中，只有非空结点入栈。为了算法简洁，在开始时压入一个空指针作为监视哨，当这个空指针被弹出来的时候则周游结束。

以下是非递归前序周游二叉树代码，二叉树的结点仍使用本文最开始定义的那个 TreeNode 类。

public List<T> PreTreeNodeWIthoutRecursion(NodeTree<T> node){
    List<T> list = new ArrayList();
    Stack<NodeTree<T>> stack = new Stack();
    NodeTreee<T> pointer = node;
    //添加栈底监视哨
    stack.push(NULL);
    //用 while 循环进行周游二叉树，其实 while 循环类似递归方法
    while(pointer){
      list.add(pointer.data);
      if(pointer.right !=null ){
        stack.push(pointer.right);
      }
      if(pointer.left != null){
           pointer = pointer.left;
      }else{
        pointer = stack.top();
        stack.pop();
      }
  }
}

非递归中序周游二叉树的思路和上边类似，只不过是每遇到一个结点就直接入栈，然后周游其左子树，此时再取出栈顶位置的结点，然后获得其值加入到 list 数组里，最后在周游此结点的右子树。

非递归后序周游二叉树的思路也是使用一个栈存放当前周游的结点，只不过是每遇到一个结点就直接入栈，然后周游其左子树，然后周游此结点的右子树，最后再取出栈顶位置的结点，然后获得其值加入到 list 数组里。

除了深度优先周游二叉树外，还有广度优先周游二叉树，也就是从上到下。从左到右按层次进行。主要思路是使用 queue 队列存储当前结点，然后将此结点放入队列，每次从队列中取出队头元素进行处理，每处理一个结点时按照从左到右的顺序把它的所有子结点放入队列。这样上层结点总是排在下层结点的前面，从而实现了二叉树的广度优先周游。

广度优先周游二叉树 代码如下：

public List<T> LevelOrderTreeNode(NodeTree<T> node){
    List<T> list = new ArrayList();
    Queue<NodeTree<T>> queue= new LinkedList();
    NodeTreee<T> pointer = node;
    if(pointer){
      queue.offer(pointer);
      while(queue.peek()!=null){
       //获得队列的首结点并出队列
      pointer = queue.pool();
      //将当前结点加入到 list
      list.add(pointer.data);
      if(pointer.left !=null){
          queue.offer(pointer.left);
      }
      if(pointer.right != null){
         queue.offer(pointer.right);
      }
    }