广度优先遍历类似于二叉树的什么遍历?-LMLPHP

广度优先搜索(Breadth First Search)(其实是二叉树的层次遍历),又叫宽度优先搜索或横向优先搜索,是从根结点开始沿着树的宽度搜索遍历。

从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。

广度优先遍历类似于二叉树的什么遍历?-LMLPHP

上面二叉树的遍历顺序为:ABCDEFG. 可以利用队列实现广度优先搜索。

广度优先搜索算法:

保留全部结点,占用空间大; 无回溯操作(即无入栈、出栈操作),运行速度快。

广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。

示例:

广度优先遍历类似于二叉树的什么遍历?-LMLPHP

其过程检验来说是对每一层节点依次访问,访问完一层进入下一层,而且每个节点只能访问一次。对于上面的例子来说,广度优先遍历的 结果是:A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。

广度优先遍历各个节点,需要使用到队列(Queue)这种数据结构,queue的特点是先进先出,其实也可以使用双端队列,区别就是双端队列首位都可以插入和弹出节点。整个遍历过程如下:

Java代码大概如下:

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ArrayList<Integer> wide(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            lists.add(node.val);
		}
        return lists;
    }
}
登录后复制

更多相关知识,请访问:Work网

以上就是广度优先遍历类似于二叉树的什么遍历?的详细内容,更多请关注Work网其它相关文章!

09-05 16:00