Algorithms_二叉树的层次遍历(广度优先)

举报
小工匠 发表于 2021/09/11 00:52:03 2021/09/11
【摘要】 文章目录 使用树理解深度优先和广度优先层次遍历分析Code 使用树理解深度优先和广度优先 我们上篇博文中 Algorithms_二叉树的前序遍历、中序遍历、后续遍历(深度优先) ...


在这里插入图片描述


使用树理解深度优先和广度优先

我们上篇博文中 Algorithms_二叉树的前序遍历、中序遍历、后续遍历(深度优先) ,本质上是深度优先。 为什么这么说呢? 我们来看下


            5     
          /   \   
         3     6   
        / \      \ 
       2   4      8
       

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

前序遍历: 5 、3、2、4、6、8

中序遍历: 2、3、4、5、6、8

后序遍历 : 2、4、3、8、6、5

不管是前序、中序还是后序都会先把左子树遍历到没有元素,然后再遍历右子树到没有元素, 都是先顺着一个枝杈往最深的地方走。

而层次遍历呢? (广度优先)


            5         先遍历第0层的数据
            
--------------------------------------- 
          /   \   
         3     6      然后遍历第1层的数据
         
---------------------------------------
 
        / \      \ 
       2   4      8   再遍历第2层的数据
       
---------------------------------------

       

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

层次遍历的输出如下: 5、3、6、2、4、8

我们遍历的数据使用逐层遍历的方式,本质上是一种广度优先的遍历。


层次遍历分析

层次遍历的方式,通常使用的不是递归的方式来实现的,一般都会借用队列。 从根节点开始排着队的进入到队列中


            5         先遍历第0层的数据
            
--------------------------------------- 
          /   \   
         3     6      然后遍历第1层的数据
         
---------------------------------------
 
        / \      \ 
       2   4      8   再遍历第2层的数据
       
---------------------------------------

       

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

我们逐步来分析一下

  1. 根节点不为空的话,将根节点5入队
  2. 访问根节点5 ,然后将 5 的 左右孩子 3 和 6 入队 --------> 5
  3. 访问左孩子3 ,这个时候判断下 3是否有左右孩子,有的话将2和4 入队 ------>5 3
  4. 这个时候队列中有 6 、2、4 ,访问6 ------> 5 3 6
  5. 看下6的左右孩子,有的话入队,这个时候队列中有 2 、4 、8
  6. 访问 2 ,看下2还有没有左右孩子,没有 ------> 5 3 6 2
  7. 访问 4 看下4 还有没有左右孩子,没有 ------> 5 3 6 2 4
  8. 访问 8 看下8 还有没有左右孩子,没有 ------> 5 3 6 2 4 8
  9. 整个队列为空,广度优先遍历结束。

Code

/**
	 * 
	 * 
	 * @Title: levelScan
	 * 
	 * @Description: 二分搜索树的层序遍历
	 * 
	 * 
	 * @return: void
	 */
	public void levelScan() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);// 把root入队
		while (!queue.isEmpty()) {
			Node currentNode = queue.remove();// 移除并返回
			System.out.println(currentNode.e);

			if (currentNode.left != null) {
				queue.add(currentNode.left);
			}

			if (currentNode.right != null) {
				queue.add(currentNode.right);
			}
		}

	}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

测试下

public static void main(String[] args) {
		BinarySearchTree<Integer> bst = new BinarySearchTree<>();

		int[] nums = { 5, 3, 6, 8, 4, 2 };
		for (int num : nums) {
			bst.add(num);
		}

		// bst.preOrder();
		// System.out.println("============================");
		// bst.preOrderNR();
		// System.out.println("============================");

		bst.levelScan();

	}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述

文章来源: artisan.blog.csdn.net,作者:小小工匠,版权归原作者所有,如需转载,请联系作者。

原文链接:artisan.blog.csdn.net/article/details/104231834

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。