用c++写出森林的层序遍历
时间: 2024-05-05 22:20:32 浏览: 17
当然,我会根据您的要求进行回答,不会透露您的任何信息。
对于您的问题,下面是用C语言实现森林的层序遍历的代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct TreeNode{
int data;
struct TreeNode *firstChild;
struct TreeNode *nextSibling;
}TreeNode, *Tree;
typedef struct Queue{
Tree data[MAXSIZE];
int front;
int rear;
}Queue;
void InitQueue(Queue *q)
{
q->front = q->rear = 0;
}
int isEmpty(Queue *q)
{
return q->front == q->rear;
}
void EnQueue(Queue *q, Tree t)
{
if((q->rear + 1) % MAXSIZE == q->front)
return;
q->data[q->rear] = t;
q->rear = (q->rear + 1) % MAXSIZE;
}
void DeQueue(Queue *q, Tree *t)
{
if(isEmpty(q))
return;
*t = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
}
void LevelOrderTraversal(Tree t)
{
Queue q;
InitQueue(&q);
EnQueue(&q, t);
while(!isEmpty(&q))
{
Tree p;
DeQueue(&q, &p);
printf("%d ", p->data);
if(p->firstChild)
EnQueue(&q, p->firstChild);
if(p->nextSibling)
EnQueue(&q, p->nextSibling);
}
}
int main()
{
Tree t1, t2, t3, t4, t5;
t1 = (Tree)malloc(sizeof(TreeNode));
t2 = (Tree)malloc(sizeof(TreeNode));
t3 = (Tree)malloc(sizeof(TreeNode));
t4 = (Tree)malloc(sizeof(TreeNode));
t5 = (Tree)malloc(sizeof(TreeNode));
t1->data = 1;
t2->data = 2;
t3->data = 3;
t4->data = 4;
t5->data = 5;
t1->firstChild = t2;
t2->firstChild = t3;
t2->nextSibling = t4;
t4->nextSibling = t5;
t5->nextSibling = NULL;
t3->firstChild = NULL;
t3->nextSibling = NULL;
t4->firstChild = NULL;
t5->firstChild = NULL;
LevelOrderTraversal(t1);
return 0;
}
```
注:以上代码实现了森林的层序遍历,其中声明了两个结构体:TreeNode和Queue,TreeNode表示树节点,Queue表示队列,为了方便代码实现,我选择了用循环队列来实现队列。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)