首页 > 代码库 > 二叉树的层次遍历
二叉树的层次遍历
进行层次遍历时，对某一层的节点访问完后，再按照对它们的访问次序对各个节点的左右节点的左右孩子顺序访问。这样一层一层进行，先访问的节点其左右孩子也要先访问，与队列的操作原则较吻合。因此层次遍历算法采用一个环形队列来实现。
层次遍历的过程：
先将根节点进队，在队不为空时循环：从队列中出列一个节点*p，访问它；若它有左孩子节点，将左孩子节点进队；若它有右孩子节点，将右孩子进队。如此操作直到队为空。算法如下：
1 void LevelOrder(tree *root) 2 { 3 tree *p; 4 tree *que[fb];//定义环形队列，存放节点指针 5 int front,rear;//定义队头 6 front = rear = -1;//置队列为空队列 7 rear++; 8 que[rear] = root;//根节点指针进队 9 while(front!=rear){//队列不为空10 front =(front + 1) % fb;11 p = que[front];//队头出队列12 cout<<p->NodeNum<<" ";//13 if(p->left!=NULL){//有左孩子时进队14 rear = (rear + 1) % fb;15 que[rear] = p->left;16 }17 if(p->right != NULL){//有右孩子时进队18 rear = (rear + 1) % fb;19 que[rear] = p->right;20 }21 }22 }
二叉树的层次遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。