【数据结构】二叉树的层序遍历~动画超详解

1 什么是层序遍历

• 我们从字面意思就明白,所谓层序,就是一层一层按顺序去遍历一个二叉树,这和我们之前了解的按前中后序遍历方式完全不同

比方说这颗二叉树:

前序遍历:

层序遍历:

2 二叉树层序遍历的基本思路

• 我们引入一个队列,入这棵树的根进队列,只要这个树的非叶子节点出队列了,立马让这个节点的子节点如队列,如此循环,我们直接看动画

3 二叉树层序遍历的实现

//层序遍历
void TreeLevelOrder(BTNode* proot)
{QU qu;   // 创建队列QInit(&qu);   // 队列初始化if (proot == NULL)  // 判空{return;}else{QPush(&qu, proot);  // 二叉树不是空就先把第一个值入队}while (!QEmpty(&qu))  //  只要队列不是空就一直循环，直到队列为空{QDataType tmp = QFront(&qu);  //  取队头QPop(&qu);   //  队头元素出队if (tmp->leftnode != NULL)  //  取队头的子节点入队（除非子节点为空）{QPush(&qu, tmp->leftnode);}if (tmp->rightnode != NULL){QPush(&qu, tmp->rightnode);}printf("%d ", tmp->val);  //  打印出队的节点的值（视情况加或不加）}QDestroy(&qu);  //  别忘了销毁堆列
}

---

佬!都看到这了,如果觉得有帮助的话一定要点赞啊佬 >v< !!!
放个卡密在这,感谢各位能看到这儿啦!