用c++写一个森林的层序遍历
时间: 2023-12-04 14:03:36 浏览: 24
可以使用队列来实现森林的层序遍历。具体步骤如下:
1. 将根节点放入队列中。
2. 循环执行以下步骤,直到队列为空:
a. 弹出队列中的第一个节点,输出该节点的值。
b. 将该节点的所有子节点依次放入队列中。
下面是用 C 语言实现森林的层序遍历的代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* firstChild;
struct TreeNode* nextSibling;
} TreeNode;
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
printf("%d ", node->val);
TreeNode* child = node->firstChild;
while (child != NULL) {
queue[rear++] = child;
child = child->nextSibling;
}
}
}
int main() {
// 构造一颗森林
TreeNode* root1 = (TreeNode*)malloc(sizeof(TreeNode));
root1->val = 1;
root1->firstChild = (TreeNode*)malloc(sizeof(TreeNode));
root1->firstChild->val = 2;
root1->firstChild->firstChild = NULL;
root1->firstChild->nextSibling = (TreeNode*)malloc(sizeof(TreeNode));
root1->firstChild->nextSibling->val = 3;
root1->firstChild->nextSibling->firstChild = (TreeNode*)malloc(sizeof(TreeNode));
root1->firstChild->nextSibling->firstChild->val = 4;
root1->firstChild->nextSibling->firstChild->firstChild = NULL;
root1->firstChild->nextSibling->firstChild->nextSibling = NULL;
root1->firstChild->nextSibling->nextSibling = NULL;
TreeNode* root2 = (TreeNode*)malloc(sizeof(TreeNode));
root2->val = 5;
root2->firstChild = NULL;
root2->nextSibling = (TreeNode*)malloc(sizeof(TreeNode));
root2->nextSibling->val = 6;
root2->nextSibling->firstChild = NULL;
root2->nextSibling->nextSibling = NULL;
TreeNode* root3 = (TreeNode*)malloc(sizeof(TreeNode));
root3->val = 7;
root3->firstChild = NULL;
root3->nextSibling = (TreeNode*)malloc(sizeof(TreeNode));
root3->nextSibling->val = 8;
root3->nextSibling->firstChild = NULL;
root3->nextSibling->nextSibling = (TreeNode*)malloc(sizeof(TreeNode));
root3->nextSibling->nextSibling->val = 9;
root3->nextSibling->nextSibling->firstChild = NULL;
root3->nextSibling->nextSibling->nextSibling = NULL;
// 将森林的根节点放入数组中
TreeNode* forest[3] = {root1, root2, root3};
// 对每棵树分别进行层序遍历
for (int i = 0; i < 3; i++) {
printf("Tree %d level order: ", i + 1);
levelOrder(forest[i]);
printf("\n");
}
return 0;
}
```
输出结果为:
```
Tree 1 level order: 1 2 3 4
Tree 2 level order: 5 6
Tree 3 level order: 7 8 9
```