首页给出二叉树的自下而上，从右到左的层次遍历算法。C

给出二叉树的自下而上，从右到左的层次遍历算法。C

时间: 2024-11-22 17:38:28 AIGC 浏览: 59

在二叉树的自下而上、从右到左的层次遍历中，也称为"广度优先遍历"或"水平遍历"，我们通常使用队列数据结构来实现。以下是使用C语言的简单步骤： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点 typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 辅助函数，用于将当前层的所有节点压入队列 void layerPush(int val, Queue* queue) { Node* node = (Node*)malloc(sizeof(Node)); node->data = val; queue->size++; queue->queue[queue->tail++] = node; } // 层次遍历函数 void levelOrderTraversal(TreeNode* root) { if (root == NULL) return; // 如果根节点为空，直接返回 Queue* queue = createQueue(); // 创建一个空队列 layerPush(root->val, queue); // 将根节点值压入队列 while (!queue->isEmpty()) { // 当队列非空时 Node* temp = queue->front; // 取出队首元素 printf("%d ", temp->data); // 输出该节点值 free(temp); // 释放内存 // 将左子节点和右子节点依次压入队列 if (temp->left != NULL) layerPush(temp->left->val, queue); if (temp->right != NULL) layerPush(temp->right->val, queue); // 移除已处理的节点 queue->front = queue->next; if (queue->front == NULL) queue->tail = 0; queue->size--; } } // 其他辅助函数省略... int main() { // 初始化二叉树... TreeNode* tree = ...; levelOrderTraversal(tree); return 0; } ``` 在这个例子中，`createQueue()` 和 `freeQueue()` 函数是用来创建和销毁队列的，它们在这里没有列出。层次遍历会先访问根节点，然后逐层地访问其左右子节点，直到所有节点都被访问过。

阅读全文