欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的层序遍历

程序员文章站 2024-03-19 21:18:28
...

二叉树的层序遍历:

所有的层序遍历,就是从根节点(第一层开始),依次向下,获取每一层所有结点的值,有二叉树入下:
二叉树的层序遍历
API设计:
public Queue layerErgodic():使用层序遍历,获取整个树中的所有键;
实现步骤:
1.创建队列,存储每一层的结点;
2.使用循环从队列中弹出一个结点:
2.1:获取当前结点的key;
2.2:如果当前结点的左子结点不为空,则把左子结点放入到队列中;
2.3:如果当前结点的右子结点不为空,则把右子结点放入到队列中;
图例:
二叉树的层序遍历

代码入下:
//注:队列代码链接:https://blog.csdn.net/qq_43751200/article/details/104759716

//使用层序遍历,获取整个树中所有的键
    public Queue<Key> layerErgodic(){
        //定义两个队列,分别存储树中的键和树中的结点
        Queue<Key> keys = new Queue<>();//存储键队列
        Queue<Node> nodes = new Queue<>();//存储结点队列

        //默认,往队列中放入根结点
        nodes.enQueue(root);

        while (!nodes.isEmpty()){
            //往队列中弹出一个结点,把key放入到keys中
            Node n = nodes.dequeue();
            keys.enQueue(n.key);
            //判断当前结点还有没有左子结点,如果有,则放入到nodes中
            if(n.left != null){
                nodes.enQueue(n.left);
            }
            //判断当前结点还有没有右子节点,如果有,则放入到nodes中
            if(n.right != null){
                nodes.enQueue(n.right);
            }
        }

        return keys;
    }
相关标签: 数据结构