浅谈数据结构之树的基础算法（二）

小鱼儿 2021-11-23 08:10 279阅读 0赞

[上一篇][Link 1]

### 浅谈数据结构之树的基础算法（二） ###

*   *  二叉树遍历
     *  二叉树非递归遍历算法
     *  二叉树递归遍历算法

## 二叉树遍历 ##

**前序遍历：** 先访问根节点，然后遍历左子树，最后遍历右子树  
**中序遍历：** 先遍历左子树，然后遍历根节点，最后遍历右子树  
**后续遍历：** 先遍历左子树，然后遍历右子树，最后便利根节点  
**层次遍历：** 从上到下逐层遍历，在同一层中，按从左到右的顺序遍历  
![在这里插入图片描述][20191122105305389.png]  
**前序遍历**  
![在这里插入图片描述][20191122105453776.png]  
**中序遍历**  
![在这里插入图片描述][20191122105538799.png]  
**后续遍历**  
![在这里插入图片描述][2019112210564183.png]  
**层序遍历**

## 二叉树非递归遍历算法 ##

**数据结构类TreeNode定义**

public class TreeNode { 
    
       public String value;
    
       public TreeNode left;
    
       public TreeNode right;
    
       public TreeNode(String value) { 
           this.value = value;
       }
    }

**四种遍历算法实战**

public class Traverse { 
    
       /** * 非递归实现前序遍历 * 先访问根节点，然后遍历左子树，最后遍历右子树 * @param head */
       public static void preOrder(TreeNode head) { 
           if (null != head) { 
               // 采用栈来存储遍历过程，利用栈的先进后数据结构
               Stack<TreeNode> stack = new Stack();
               // 先把根节点压栈，然后开始遍历
               stack.push(head);
               while (!stack.isEmpty()) { 
                   TreeNode pop = stack.pop();
                   System.out.print(pop.value + " ");
                   // 必须先判断右节点，在判断左节点，右节点先入站，则后出栈，刚好满足先遍历左节点，在遍历右节点
                   if (pop.right != null) { 
                       stack.push(pop.right);
                   }
                   if (pop.left != null) { 
                       stack.push(pop.left);
                   }
               }
           }
       }
    
       /** * 非递归实现中序遍历 * 先遍历左子树，然后遍历根节点，最后遍历右子树 * @param head */
       public static void inOrder(TreeNode head) { 
           if(head != null) { 
               Stack<TreeNode> stack = new Stack();
               while (!stack.isEmpty() || head != null) { 
                   if (head != null) { 
                       //先把根节点入栈，然后再把左子树全部压栈，直到叶子节点，然后执行else弹出
                       stack.push(head);
                       head = head.left;
                   } else { 
                       head = stack.pop();
                       System.out.print(head.value + " ");
                       head = head.right;
                   }
               }
           }
       }
    
       /** * 非递归实现后续遍历 * 先遍历左子树，然后遍历右子树，最后便利根节点 * @param head */
       public static void postOrder(TreeNode head) { 
           if (null != head) { 
               Stack<TreeNode> stack1 = new Stack();
               Stack<TreeNode> stack2 = new Stack();
               stack1.push(head);
               while (!stack1.isEmpty()) { 
                   TreeNode pop = stack1.pop();
                   stack2.push(pop);
                   if (pop.left != null) { 
                       stack1.push(pop.left);
                   }
                   if (pop.right != null) { 
                       stack1.push(pop.right);
                   }
               }
               while (!stack2.isEmpty()) { 
                   System.out.print(stack2.pop().value + " ");
               }
           }
       }
    
       /** * 非递归实现层次遍历 * 从上到下逐层遍历，在同一层中，按从左到右的顺序遍历 * @param head */
       public static void levelOrder(TreeNode head) { 
           if (head != null) { 
           // 采用队列的数据结构特点实现遍历
               Queue<TreeNode> queue = new ArrayDeque<>();
               queue.offer(head);
               while (!queue.isEmpty()) { 
                   int levelNum = queue.size();
                   for (int i = 0; i < levelNum; i++) { 
                       TreeNode poll = queue.poll();
                       System.out.print(poll.value + " ");
                       if (poll.left != null) { 
                           queue.offer(poll.left);
                       }
                       if (poll.right != null) { 
                           queue.offer(poll.right);
                       }
                   }
               }
           }
       }
       
       public static void main(String[] args) { 
           TreeNode A = new TreeNode("A");
           TreeNode B = new TreeNode("B");
           TreeNode C = new TreeNode("C");
           TreeNode D = new TreeNode("D");
           TreeNode E = new TreeNode("E");
           TreeNode F = new TreeNode("F");
           TreeNode G = new TreeNode("G");
           TreeNode H = new TreeNode("H");
           TreeNode I = new TreeNode("I");
           TreeNode J = new TreeNode("J");
           TreeNode K = new TreeNode("K");
    
           A.left = B;
           A.right = C;
           B.left = D;
           B.right = E;
           D.left = H;
           D.right = I;
           E.right = J;
           C.left = F;
           C.right = G;
           F.right = K;
    
           System.out.print("前序遍历：");
           preOrder(A);
           System.out.println();
           System.out.print("中序遍历：");
           inOrder(A);
           System.out.println();
           System.out.print("后序遍历：");
           postOrder(A);
           System.out.println();
           System.out.print("层次遍历：");
           levelOrder(A);
       }

前序遍历：A B D H I E J C F K G 
    中序遍历：H D I B E J A F K C G 
    后序遍历：H I D J E B K F G C A 
    层次遍历：A B C D E F G H I J K

## 二叉树递归遍历算法 ##

**层次递归遍历由于控制结束条件比较复杂，因此不在此讨论，实现上多以队列的数据结构辅助遍历**

public class Traverse { 
        /** * 递归实现前序遍历 * 先访问根节点，然后遍历左子树，最后遍历右子树 * @param head */
        public static void recursionPreOrder(TreeNode head) { 
            // 终止条件
            if (null == head) { return;}
    
            System.out.print(head.value + " ");
            recursionPreOrder(head.left);
            recursionPreOrder(head.right);
        }
    
        /** * 递归实现中序遍历 * 先遍历左子树，然后遍历根节点，最后遍历右子树 * @param head */
        public static void recursionInOrder(TreeNode head) { 
            // 终止条件
            if(null == head) { return;}
    
            recursionInOrder(head.left);
            System.out.print(head.value + " ");
            recursionInOrder(head.right);
        }
    
        /** * 递归实现后续遍历 * 先遍历左子树，然后遍历右子树，最后便利根节点 * @param head */
        public static void recursionPostOrder(TreeNode head) { 
            // 终止条件
            if (null == head) { return;}
    
            recursionPostOrder(head.left);
            recursionPostOrder(head.right);
            System.out.print(head.value + " ");
        }
    
    
        public static void main(String[] args) { 
            TreeNode A = new TreeNode("A");
            TreeNode B = new TreeNode("B");
            TreeNode C = new TreeNode("C");
            TreeNode D = new TreeNode("D");
            TreeNode E = new TreeNode("E");
            TreeNode F = new TreeNode("F");
            TreeNode G = new TreeNode("G");
            TreeNode H = new TreeNode("H");
            TreeNode I = new TreeNode("I");
            TreeNode J = new TreeNode("J");
            TreeNode K = new TreeNode("K");
    
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            D.left = H;
            D.right = I;
            E.right = J;
            C.left = F;
            C.right = G;
            F.right = K;
            
            System.out.print("前序遍历：");
            recursionPreOrder(A);
            System.out.println();
            System.out.print("中序遍历：");
            recursionInOrder(A);
            System.out.println();
            System.out.print("后序遍历：");
            recursionPostOrder(A);
        }
    }

前序遍历：A B D H I E J C F K G 
    中序遍历：H D I B E J A F K C G 
    后序遍历：H I D J E B K F G C A

[Link 1]: https://blog.csdn.net/cuixhao110/article/details/97262266
[20191122105305389.png]: /images/20211122/36a7c01f918c405fa0503af346ab7c80.png
[20191122105453776.png]: /images/20211122/64d1857793a748539b77be6374cf8228.png
[20191122105538799.png]: /images/20211122/eacad579f7c846bc9e36ec42591a019e.png
[2019112210564183.png]: /images/20211122/996b190bdffc43a092e6f79162dc91b2.png