0x0001.树的遍历 简介

1. 深度遍历的运行过程是先进后出(FILO)的，用的是栈和递归

   树的前序，中序，后序遍历

2. 广度遍历的运行过程是先进先出(FIFO)的，用的是队列

   树的层序遍历

补充：顺序（根据根）：根左右，中序左根右，后序左右根

​ 层序：按层级输出

0x0002. 树的遍历

递归和栈 （树的前序，中序，后序遍历）

1. 递归实现

   public class BST {
     ...
   	public static void preOrder(TreeNode treeNode){
           if (treeNode == null) return;
           System.out.print(treeNode.data + " ");
           preOrder(treeNode.left);
           preOrder(treeNode.right);
       }
   
       public static void inOrder(TreeNode treeNode){
           if (treeNode == null) return;
           inOrder(treeNode.left);
           System.out.print(treeNode.data + " ");
           inOrder(treeNode.right);
       }
   
       public static void postOrder(TreeNode treeNode){
           if (treeNode == null) return;
           postOrder(treeNode.left);
           postOrder(treeNode.right);
           System.out.print(treeNode.data + " ");
       }
   }
   

2. 栈实现

   public class BST {
     	...
       public static void stackPreOrder(TreeNode treeNode) {
           if (treeNode == null ) return;
           Stack<TreeNode> stack = new Stack<TreeNode>();
           stack.push(treeNode);
           TreeNode curNode = stack.pop();
           while (!stack.empty() || curNode != null){
               if (curNode != null) {
                   System.out.print(curNode.data + " ");
                   stack.push(curNode);
                   curNode = curNode.left;
               } else {
                   curNode = stack.pop();
                   curNode = curNode.right;
               }
           }
       }
     
     public static void stackInOrder(TreeNode treeNode) {
           if (treeNode == null ) return;
           Stack<TreeNode> stack = new Stack<TreeNode>();
           TreeNode curNode = treeNode;
           while (!stack.empty() || curNode != null){
               if (curNode!= null){
                 	// 入栈
                   stack.push(curNode);
                   curNode = curNode.left;
               } else {
                  // 回溯
                   curNode = stack.pop();
                   System.out.print(curNode.data + " ");
                   curNode = curNode.right;
               }
              
           }
       }
     
     public static void stackPostOrder(TreeNode treeNode) {
           if (treeNode == null ) return;
           Stack<TreeNode> stack = new Stack<TreeNode>();
           TreeNode curNode = treeNode;
           TreeNode last = null;
           while (!stack.empty() || curNode != null){
               if (curNode != null) {
                   stack.push(curNode);
                   curNode = curNode.left;
               } else {
                 	// 用 peek，而非 pop
                   TreeNode temp = stack.peek();
                   //是否变到右子树
                   if (temp.right != null && temp.right != last) {
                       curNode = temp.right;
                   } else {
                       System.out.print(temp.data + " ");
                       last = temp;
                       stack.pop();
                   }
               }
           }
       }
   }
   

队列（树的层序遍历）

1. 具体实现

   public class BST {
     	...	
   		public static void levelOrder(TreeNode treeNode) {
           if (treeNode == null) return;
           Queue<TreeNode> queue = new LinkedList<TreeNode>();
           queue.offer(treeNode);
           while(!queue.isEmpty()){
               TreeNode cur = queue.poll();
             	// 打印当前节点
               System.out.print(" " + cur.data);
   	          // 按顺序入队列即可
               if(cur.left != null) queue.offer(cur.left);
               if(cur.right != null) queue.offer(cur.right);
           }
       }
   }