在按层序遍历二叉树的算法中，需要借助的数据结构是（ ）。
选A。
在按层次遍历二叉树的算法中，需要借助的辅助数据结构是队列。
具体实现如下,使用C++ STL库 queue 的函数：
void LevelOrder(BiTree p)
{
queue<BiTree>Q;//使用C++ STL库
Q.push(p);//根节点入队
while(!Q.empty())//队列不空循环
{
p=Q.front();//取对头
printf("%c",p->data);//左右孩子入队
if(p->lchild!=NULL)
{
Q.push(p->lchild);
}
if(p->rchild!=NULL)
{
Q.push(p->rchild);
}
Q.pop();//队头元素出队
}
printf("\n");
} 因此本题选A。 补充：
二叉树的先序、中序、后序遍历的非递归实现需要借助栈这一数据结构实现。
编辑于 2020-01-14 15:32:10
回复(0)
选A。
如下图所示，按层遍历为：ABCDEF
从根节点开始，逐层从左到右依次访问，即入队操作；而取出记录的节点是出队操作。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void traverse(bitree bt) { linkqueue q; bitree p; initqueue(q); //初始化一个空的队列 p=bt; enqueue(q,p); //入队 while(queueempty(q)!=1) { dequeue(q,p); //出队 if(p->lchild!=NULL) enqueue(q,p->lchild); //访问左子树 if(p->rchild!=NULL) enqueue(q,p->rchild); //访问右子树 } printf("\n"); } |
发表于 2020-07-03 17:18:25
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
void traverse(bitree bt) { linkqueue q; bitree p; initqueue(q); //初始化一个空的队列 p=bt; enqueue(q,p); //入队 while(queueempty(q)!=1) { dequeue(q,p); //出队 if(p->lchild!=NULL) enqueue(q,p->lchild); //访问左子树 if(p->rchild!=NULL) enqueue(q,p->rchild); //访问右子树 } printf("\n"); }