首页 > 试题广场 >

在按层次遍历二叉树的算法中,需要借助的数据结构是( )。

[单选题]

在按层序遍历二叉树的算法中,需要借助的数据结构是(  )。

  • 队列
  • 线性表
  • 有序表
推荐
选A
如下图所示,按层遍历为:ABCDEF
从根节点开始,逐层从左到右依次访问,即入队操作;而取出记录的节点是出队操作。
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-01-21 16:23:57 回复(0)
A  记住队列先进先出这个特点,就很容易理解了。
发表于 2020-01-16 15:19:01 回复(0)
A、队列。层次遍历时,父节点先入队,出队时输出队首结点,让其子节点入队。
发表于 2020-01-16 19:48:03 回复(0)
A,因为我们得先遍历根节点,把它入队,再遍历它的子节点,将根节点出队......
发表于 2020-01-14 16:51:43 回复(0)
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)
队列
1.遍历二叉树时,总是先判断树是否为空;
2.树非空, 先将根节点入队;
3.进入循环体,获取队首元素,将队首元素的非空左右孩子入队,并将队首元素出队。
在这里需要注意的是, 一定要判断有无左右孩子,有才可以入队,否则访问到非法内存会造成段错误。
发表于 2020-01-17 15:14:13 回复(0)
为什么不是线性表和有序表呢?
发表于 2023-03-30 14:38:17 回复(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)
队列
发表于 2020-01-20 20:46:31 回复(0)
队列
发表于 2020-01-20 19:35:20 回复(0)
选A
发表于 2020-01-18 16:51:51 回复(0)
A,队列
发表于 2020-01-18 15:45:03 回复(0)
队列。当我们遍历一个结点时,让其出队,然后让非空子结点入队,那么这样就可以实现层次遍历了。
发表于 2020-01-14 14:47:02 回复(1)