二叉树的广度优先遍历(按层遍历)
(1)层序遍历,输出到一行;使用队列,先进先出
示例:【输出】1 2 3 4 5 6 7
void levelOrder(TreeNode* head){
queue<TreeNode*> que;
if(head != NULL){
que.push(head);
}
while(!que.empty()){
TreeNode* cur = que.front();
cout << cur->value << " ";
que.pop();
if(cur->left != NULL){
que.push(cur->left);
}
if(cur->right != NULL){
que.push(cur->right);
}
}
cout << endl;
}
(2)层序遍历,按层输出
示例:
【输出】
第一层:1
第二层:2 3
第三层:4 5 6 7
此处主要是一个换行问题,利用两个指针来解决,last表示正在打印的当前行的最右节点,nlast表示下一行的最右节点。假设每一层都做从左到右的宽度优先遍历,当发现遍历到的节点cur等于last时说明应该换行,换行之后令last=nlast,就可以进行下一行的打印。nlast则一直跟踪记录宽度优先遍历队列中的最先加入的节点即可。
void printByLevel(TreeNode* head){
if(head == NULL){
return ;
}
queue<TreeNode*> que;
int level = 1;
TreeNode* last = head,*nlast = NULL,*cur = head;
que.push(cur);
cout << "Level " << level++ << " :";
while(!que.empty()){
cur = que.front();
cout << cur->value << " ";
que.pop();
if(cur->left != NULL){
que.push(cur->left);
nlast = cur->left;
}
if(cur->right != NULL){
que.push(cur->right);
nlast = cur->right;
}
if(cur == last && !que.empty()){
cout << "\nLevel " << level++ << " :" ;
last = nlast;
}
}
cout << endl;
}