c语言反转一棵二叉树

在C语言中，反转一棵二叉树通常涉及到递归算法。这里是一个简单的思路：

首先，我们需要定义一个结构体表示二叉树节点：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

然后，我们可以创建一个函数`invertTree`来进行递归操作：

TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) {
        return NULL; // 如果当前节点为空，返回空指针
    }

    // 交换左右子节点
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;

    // 对左子树和右子树进行递归反转
    root->left = invertTree(root->left);
    root->right = invertTree(root->right);

    return root;
}

这个函数会改变给定二叉树的结构，使得每个节点的左孩子变成它的原右孩子，右孩子变成原左孩子。

相关问题

c语言二叉树反转代码

在C语言中，二叉树的反转通常涉及到层次遍历（即先序、中序或后序遍历）的技巧。这里提供一种基于递归的后序遍历方法来反转二叉树：

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 后序遍历并反转节点顺序
void invertTree(TreeNode** root) {
    if (*root != NULL) {
        // 先翻转左右子树
        invertTree(&(*root)->left);
        invertTree(&(*root)->right);

        // 然后交换当前节点与其父节点的位置
        TreeNode* temp = (*root)->left;
        (*root)->left = (*root)->right;
        (*root)->right = temp;
    }
}

// 构建一个简单的例子展示如何使用这个函数
void buildExample() {
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;

    // ...添加更多节点

    // 调用invertTree反转二叉树
    invertTree(&root);

    // 打印反转后的树（这里省略了打印部分）
}

用类c语言实现后序遍历二叉树的非递归算法

非递归后序遍历二叉树的实现需要借助栈来实现。具体步骤如下：

1. 定义一个栈，初始化为空。
2. 将根节点入栈。
3. 循环执行以下步骤，直到栈为空：
1. 取出栈顶节点，将其值保存到结果数组中。
2. 如果该节点有左子节点，则将左子节点入栈。
3. 如果该节点有右子节点，则将右子节点入栈。
4. 将结果数组反转，得到后序遍历序列。

下面是使用类c语言实现的代码：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void postorderTraversal(TreeNode* root, int* returnSize, int* ret) {
    if (root == NULL) {
        *returnSize = 0;
        return;
    }
    
    int len = 0;  // 结果数组的长度
    int* res = (int*)malloc(sizeof(int) * 100);  // 初始化结果数组
    
    TreeNode** stack = (TreeNode**)malloc(sizeof(TreeNode*) * 100);  // 定义栈
    int top = -1;  // 栈顶指针
    
    stack[++top] = root;  // 根节点入栈
    
    while (top >= 0) {
        TreeNode* node = stack[top--];  // 取出栈顶节点
        
        res[len++] = node->val;  // 将节点的值保存到结果数组中
        
        if (node->left != NULL) {
            stack[++top] = node->left;  // 如果该节点有左子节点，则将左子节点入栈
        }
        if (node->right != NULL) {
            stack[++top] = node->right;  // 如果该节点有右子节点，则将右子节点入栈
        }
    }
    
    // 反转结果数组
    int i = 0, j = len - 1;
    while (i < j) {
        int temp = res[i];
        res[i++] = res[j];
        res[j--] = temp;
    }
    
    // 将结果数组返回
    *returnSize = len;
    for (i = 0; i < len; i++) {
        ret[i] = res[i];
    }
}

其中，`root` 表示二叉树的根节点，`returnSize` 表示结果数组的长度，`ret` 表示结果数组。在函数中，先判断根节点是否为空，如果是，则直接返回空数组；否则，初始化结果数组和栈，并将根节点入栈。接着，循环取出栈顶节点，并将其值保存到结果数组中。如果该节点有左子节点，则将左子节点入栈；如果该节点有右子节点，则将右子节点入栈。循环结束后，反转结果数组，并将其返回。