二叉树的前、中、后、层序遍历

小鱼儿 2023-03-01 13:28 34阅读 0赞

# 二叉树的遍历 #

遍历：把二叉树中所有节点都访问一遍且只访问一次。

二叉树有以下四种遍历方式：

*  前序遍历: 先访问父节点，再遍历左子树和右子树。
 *  中序遍历: 先遍历左子树，再访问父节点，再遍历右子树。
 *  后序遍历: 先遍历左子树，再遍历右子树，最后访问父节点。
 *  层序遍历：也叫层次遍历，从根节点开始往下一层一层的遍历节点。

小结: 看访问父节点的顺序，就能确定是前序，中序还是后序遍历。

## 前序遍历 ##

前序遍历的访问顺序为：父节点、前序遍历左子树、前序遍历右子树。

下面的二叉树前序遍历的结果为`7、4、2、1、3、5、9、8、11、10、12`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

前序遍历的代码实现：

/** * 前序遍历 */
        public void preorder() { 
            preorder(root);
        }
        
        private void preorder(Node<E> node) { 
    
            if(null == node) { 
                return;
            }
    
            System.out.println(node.value);
    
            if(null != node.left) { 
                preorder(node.left);
            }
    
            if(null != node.right) { 
                preorder(node.right);
            }
    
        }

前面的前序遍历只实现了对节点的打印，如果想要自定义对节点的操作以及访问到某个节点就终止遍历，怎么实现？

下面实现对前序遍历的增强：

增加遍历接口：

public static abstract class Vistor<E> { 
    
            protected boolean stop;
    
            /** * 遍历节点 * @param e * @return true-停止遍历，false-继续遍历 */
            public abstract boolean visit(E e);
    
        }

前序遍历增强方法：

/** * 前序遍历增强 */
        public void preorder(Vistor<E> vistor) { 
            if (null == root || null == vistor) { 
                return;
            }
            preorder(root, vistor);
        }
    
        private void preorder(Node<E> node, Vistor<E> vistor) { 
    
            // 每次遍历前先判断标志位stop是否为true
            if (null == node || vistor.stop) { 
                return;
            }
    
            // 将stop置为true，停止遍历
            vistor.stop = vistor.visit(node.value);
    
            if (null != node.left) { 
                preorder(node.left, vistor);
            }
    
            if (null != node.right) { 
                preorder(node.right, vistor);
            }
    
        }

中序遍历、后序遍历、层次遍历的增强与前序遍历增强类似。

## 中序遍历 ##

中序遍历的访问顺序：中序遍历左子树、父节点、中序遍历右子树。

下面的二叉树中序遍历的结果为`1、2、3、4、5、7、8、9、10、11、12`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]  
中序遍历的访问顺序也可以是：中序遍历右子树、根节点、中序遍历左子树。这样访问上面的结果为`12、11、10、9、8 、7、5、4、3、2、1`，可见二叉搜索树的中序遍历结果是升序或者降序的。

中序遍历的代码实现：

/** * 中序遍历 */
        public void inorder() { 
            inorder(root);
        }
    
        private void inorder(Node<E> node) { 
    
            if(null == node) { 
                return;
            }
    
            if(null != node.left) { 
                inorder(node.left);
            }
    
            System.out.println(node.value);
    
            if(null != node.right) { 
                inorder(node.right);
            }
    
        }

## 后序遍历 ##

后序遍历的访问顺序：后序遍历左子树、后序遍历右子树、父节点。

下面的二叉树后序遍历的结果为`1、3、2、5、4、8、10、12、11、9、7`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]  
后序遍历的代码实现：

/** * 后序遍历 */
        public void postorder() { 
            postorder(root);
        }
    
        private void postorder(Node<E> node) { 
    
            if(null == node) { 
                return;
            }
    
            if(null != node.left) { 
                postorder(node.left);
            }
            
            if(null != node.right) { 
                postorder(node.right);
            }
            
            System.out.println(node.value);
    
        }

## 层序遍历 ##

层序遍历的访问顺序：从上到下、从左到右依次访问每一个节点

下面的二叉树层序遍历的结果为`7、4、9、2、5、8、11、1、3、10、12`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]  
层序遍历的思路：使用队列

1.  将根节点入队
2.  循环执行以下操作，直到队列为空
    
    1.  将队头节点A出队，进行访问
    2.  将A的左子节点入队
    3.  将A的右子节点入队

层序遍历的代码实现：

/** * 层序遍历 */
        public void levelOrder() { 
            if (null == root) { 
                return;
            }
    
            Queue<Node<E>> queue = new LinkedList<>();
            queue.offer(root);
    
            while (!queue.isEmpty()) { 
    
                Node<E> node = queue.poll();
    
                System.out.println(node.value);
    
                if(null != node.left) { 
                    queue.offer(node.left);
                }
    
                if(null != node.right) { 
                    queue.offer(node.right);
                }
    
            }
    
        }

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: /images/20230208/442048b5d1ee435281a0c2a06f06d912.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: /images/20230208/ee3ae93b41884b9bbc6c993ec2157576.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: /images/20230208/7bc8c8a6dd0640238056c78d9aaced5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: /images/20230208/cf1438ff57b44b0e9e3e55ca1b7a04d5.png
[20200627175030665.jpg]: /images/20230208/4926834ddfbc4e189437f34768f2dda2.png