首页输出二叉树后序遍历序列的逆序，方法是先访问根结点，再遍历根的右子树，最后遍历根的左子树，c语言

输出二叉树后序遍历序列的逆序，方法是先访问根结点，再遍历根的右子树，最后遍历根的左子树，c语言

时间: 2025-01-01 10:37:53 浏览: 43

在C语言中，要输出二叉树的后序遍历序列的逆序，即先根节点后左右子树，可以采用递归的方式实现。首先，我们需要定义一个结构体表示二叉树的节点： ```c typedef struct TreeNode { int val; // 节点值 struct TreeNode *left; // 左子节点 struct TreeNode *right; // 右子节点 } TreeNode; ``` 然后，编写一个函数`reversePostorderTraversal`来实现逆序后序遍历： ```c void reversePostorderTraversal(TreeNode* root, int result[]) { if (root == NULL) return; // 如果节点为空，返回 reversePostorderTraversal(root->right, result); // 先右子树 reversePostorderTraversal(root->left, result); // 再左子树 result[0] = root->val; // 最后记录根节点值，因为数组下标从0开始 result++; } ``` 为了获取逆序后的序列，你需要预先分配一个足够大的数组存储结果，并调用上述函数，例如： ```c int main() { TreeNode* root = ... // 初始化你的二叉树 int size = 1; // 初始数组大小，用于动态扩容 int* result = malloc(size * sizeof(int)); // 动态内存分配 while (result[size - 1] != 0) { // 遍历直到遇到空节点 reversePostorderTraversal(root, result); size++; // 扩容数组 } for (int i = size - 1; i >= 0; i--) { // 因为逆序，所以从最后一个元素开始打印 printf("%d ", result[i]); } free(result); // 释放内存 return 0; } ```

阅读全文