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

用C语言编写给出二叉树自下而上，从右到左的层次遍历算法

时间: 2024-12-06 22:23:16 AIGC 浏览: 67

在C语言中，我们可以使用队列数据结构来实现二叉树的自下而上、从右到左的层次遍历，也称为“右视图”遍历。以下是简单的步骤： 1. 定义节点结构体，并包含指向左右子节点的指针。 ```c typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; ``` 2. 创建一个函数`levelOrderRightView`来进行遍历，其中包含一个队列用于存储每一层的节点。 ```c void levelOrderRightView(TreeNode* root, int** result, int* levels) { if (!root) return; // 初始化队列和结果数组 queue<TreeNode*> q = {root}; *result = (int*)malloc(sizeof(int) * (*levels = 1)); **result = 0; while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode* node = q.front(); // 取出队首元素 q.pop(); // 打印当前节点值 **result = node->val; (*result)++; // 将右子节点入队（如果存在） if (node->right) q.enqueue(node->right); // 如果还有未访问的左子节点，则将左子节点入队（因为我们要从右到左） if (node->left) q.enqueue(node->left); } } } ``` 3. 在遍历完成后，记得释放分配的内存。 ```c void freeResult(int* result, int levels) { free(result); *result = 0; } // 使用示例 TreeNode* root = ...; // 填充二叉树根节点 int* res = NULL; int levels; levelOrderRightView(root, &res, &levels); // 输出结果并处理 freeResult(res, levels); ```

阅读全文