<?xml encoding="utf-8" ?><html><body><blockquote><p>广度优先遍历类似于二叉树的层次遍历。广度优先搜索是从根结点开始沿着树的宽度搜索遍历，也就是按层次的去遍历；从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。</p></blockquote><p><img src="https://img.php.cn/upload/article/202007/25/2020072513385635544.jpg"></p><p>广度优先搜索(Breadth First Search)(其实是二叉树的层次遍历),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历。</p><p>从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。</p><p><img src="https://img.php.cn/upload/image/709/973/625/1595655565872547.png" title="1595655565872547.png" alt="1.png"></p><p>上面二叉树的遍历顺序为：ABCDEFG. 可以利用队列实现广度优先搜索。</p><p><strong>广度优先搜索算法：</strong></p><p>保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。</p><p>广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。</p><p><strong>示例：</strong><br></p><p><img src="https://img.php.cn/upload/image/173/983/547/1595655771561598.png" title="1595655771561598.png" alt="2.png"></p><p>其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的 结果是：A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。</p><p>广度优先遍历各个节点，需要使用到队列（Queue）这种数据结构，queue的特点是先进先出，其实也可以使用双端队列，区别就是双端队列首位都可以插入和弹出节点。整个遍历过程如下：</p><blockquote><p>首先将A节点插入队列中，queue（A）;</p><p>将A节点弹出，同时将A的子节点B，C插入队列中，此时B在队列首，C在队列尾部，queue（B，C）；</p><p>将B节点弹出，同时将B的子节点D，E插入队列中，此时C在队列首，E在队列尾部，queue（C，D，E）;</p><p>将C节点弹出，同时将C的子节点F，G，H插入队列中，此时D在队列首，H在队列尾部，queue（D，E，F，G，H）；</p><p>将D节点弹出，D没有子节点，此时E在队列首，H在队列尾部，queue（E，F，G，H）；</p><p>...依次往下，最终遍历完成</p></blockquote><p>Java代码大概如下：</p><p>更多相关知识，请访问：PHP中文网！</p></body></html>
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/190919.html