二叉树的层序遍历
程序员文章站
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;
}
上一篇: 计算机视觉与深度学习(10)