设计一个C语言算法,交换二叉树每个节点的左孩子和右孩子。
时间: 2023-06-17 22:09:08 浏览: 54
交换二叉树每个节点的左孩子和右孩子,可以使用递归的方法实现。具体的算法如下:
1. 如果当前节点为空,返回空。
2. 如果当前节点不为空,交换当前节点的左孩子和右孩子。
3. 递归处理当前节点的左子树和右子树,分别交换左子树和右子树的左孩子和右孩子。
下面是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void swap(TreeNode* root) {
if (root == NULL) return;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
swap(root->left);
swap(root->right);
}
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
int main() {
// 构建二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
node1->val = 2;
TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
node2->val = 3;
TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
node3->val = 4;
TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
node4->val = 5;
root->left = node1;
root->right = node2;
node1->left = node3;
node1->right = node4;
printf("原始二叉树:");
inorder(root);
// 交换二叉树每个节点的左孩子和右孩子
swap(root);
printf("\n交换后的二叉树:");
inorder(root);
return 0;
}
```
输出结果如下:
```
原始二叉树:4 2 5 1 3
交换后的二叉树:3 1 2 5 4
```