区块链技术博客
www.b2bchain.cn

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

这篇文章主要介绍了二叉树的前、中、后、层序遍历的讲解,通过具体代码讲解8023并且分析了二叉树的前、中、后、层序遍历的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了二叉树的前、中、后、层序遍历的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8023.html。具体如下:

二叉树的遍历

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

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

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

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

前序遍历

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

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

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

前序遍历的代码实现:

    /**      * 前序遍历      */     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

二叉树的前、中、后、层序遍历
中序遍历的访问顺序也可以是:中序遍历右子树、根节点、中序遍历左子树。这样访问上面的结果为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

二叉树的前、中、后、层序遍历
后序遍历的代码实现:

    /**      * 后序遍历      */     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

二叉树的前、中、后、层序遍历
层序遍历的思路:使用队列

  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);             }          }      } 

更多精彩内容关注本人本文地址https://www.b2bchain.cn/8023.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 二叉树的前、中、后、层序遍历的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们