二叉树的层次遍历(递归实现) c
时间: 2023-10-24 18:29:52 浏览: 89
二叉树的层次遍历是按照从上到下、从左到右的顺序逐层访问二叉树中的节点。递归实现层次遍历的方法如下所示:
首先,我们需要定义一个队列数据结构用来存储待访问的节点。在层次遍历时,我们首先将根节点入队。
然后,进入一个循环,直到队列为空。在循环中,我们首先将队首节点出队,并访问该节点。接着,我们将该节点的左孩子和右孩子入队(如果存在的话)。
下面是递归实现层次遍历的示例代码:
```C
#include <stdio.h>
#include <stdlib.h>
// 二叉树的定义
typedef struct node {
char data;
struct node *left;
struct node *right;
} Node, *Tree;
// 层次遍历的递归函数
void levelOrderRec(Tree root, int level) {
if (root == NULL) {
return;
}
if (level == 1) {
printf(" %c - ", root->data);
} else if (level > 1) {
levelOrderRec(root->left, level - 1);
levelOrderRec(root->right, level - 1);
}
}
// 获取二叉树的高度
int getHeight(Tree root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 递归实现二叉树的层次遍历
void levelOrder(Tree root) {
int height = getHeight(root);
for (int i = 1; i <= height; i++) {
levelOrderRec(root, i);
}
}
// 测试代码
int main() {
printf("starting ------ \n");
Tree root = create_tree();
printf("递归层次遍历--- \n");
levelOrder(root);
printf("\n");
return 0;
}
```
请注意,这段代码是基于已有的二叉树结构和创建二叉树的代码进行的修改。在创建二叉树时,需要输入特定的字符序列来构建二叉树。具体的实现和输入方式,请参考代码中的注释部分。
以上是二叉树的层次遍历的递归实现方法。希望可以帮到您!<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [【数据结构】--- 二叉树的递归遍历和非递归遍历【C语言实现】](https://blog.csdn.net/qq_40587575/article/details/107410498)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [【数据结构】-----二叉树(递归、层次实现二叉树的遍历)](https://blog.csdn.net/m0_55752775/article/details/127393949)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]