用C语言编写设计算法实现对于⼀颗⼆叉树,从根结点开始,按从上到下、从左到右的顺序访问每⼀个结点,而且每⼀个结点仅仅访问⼀次。的代码
时间: 2024-03-20 08:40:02 浏览: 60
以下是用C语言实现按层次遍历二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的定义
struct node {
int data;
struct node* left;
struct node* right;
};
// 创建新的二叉树结点
struct node* newNode(int data) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 按层次遍历二叉树
void levelOrder(struct node* root) {
if (root == NULL)
return;
// 创建一个队列
struct node** queue = (struct node**)malloc(sizeof(struct node*) * 1000);
int front = 0, rear = 0;
// 把根结点加入队列
queue[rear++] = root;
while (front < rear) {
// 取出队首的结点
struct node* node = queue[front++];
printf("%d ", node->data);
// 把左子结点加入队列
if (node->left != NULL)
queue[rear++] = node->left;
// 把右子结点加入队列
if (node->right != NULL)
queue[rear++] = node->right;
}
}
int main() {
// 创建二叉树
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// 按层次遍历二叉树
printf("按层次遍历二叉树:\n");
levelOrder(root);
return 0;
}
```
这个算法使用了队列来按层次遍历二叉树。我们从根结点开始,把它加入队列。然后每次取出队列的队首结点,访问它,并把它的左子结点和右子结点加入队列。重复这个过程直到队列为空。这样可以保证按层次遍历二叉树,而且每个结点只被访问一次。
阅读全文