c语言编写一个递归算法程序,实现将二叉树中每一个结点的左右子树互换的功能。并且附上注释
时间: 2024-05-15 08:12:13 浏览: 102
交换二叉树中所有结点的左右子树
5星 · 资源好评率100%
以下是递归算法程序实现将二叉树中每一个结点的左右子树互换的功能的C语言代码:
```c
#include<stdio.h>
#include<stdlib.h>
/* 二叉树结构体 */
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
/* 创建二叉树 */
struct TreeNode* createTree() {
int val;
printf("请输入节点的数值(0表示该节点为空):");
scanf("%d", &val);
if (val == 0) {
return NULL;
}
struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = val;
node->left = createTree();
node->right = createTree();
return node;
}
/* 递归函数实现交换左右子树 */
void swapTree(struct TreeNode* root) {
/* 递归结束条件 */
if (root == NULL) {
return;
}
/* 交换左右子树 */
struct TreeNode *temp = root->left;
root->left = root->right;
root->right = temp;
/* 递归交换左右子树 */
swapTree(root->left);
swapTree(root->right);
}
/* 中序遍历二叉树 */
void inOrder(struct TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode *root = createTree();
printf("交换前的中序遍历结果为:");
inOrder(root);
printf("\n");
swapTree(root);
printf("交换后的中序遍历结果为:");
inOrder(root);
printf("\n");
return 0;
}
```
程序通过结构体定义二叉树的节点,createTree函数创建二叉树,swapTree函数递归实现交换左右子树的功能,inOrder函数实现中序遍历二叉树,main函数调用以上函数完成程序的执行。
在swapTree函数中,先递归到叶子节点,再依次交换每个节点的左右子树,因为左右子树可能为空,所以需要在交换前先保存一个子树的引用,避免引用丢失。
程序执行结果如下:
```
请输入节点的数值(0表示该节点为空):1
请输入节点的数值(0表示该节点为空):2
请输入节点的数值(0表示该节点为空):4
请输入节点的数值(0表示该节点为空):0
请输入节点的数值(0表示该节点为空):0
请输入节点的数值(0表示该节点为空):5
请输入节点的数值(0表示该节点为空):0
请输入节点的数值(0表示该节点为空):0
请输入节点的数值(0表示该节点为空):3
请输入节点的数值(0表示该节点为空):0
请输入节点的数值(0表示该节点为空):6
请输入节点的数值(0表示该节点为空):0
请输入节点的数值(0表示该节点为空):0
交换前的中序遍历结果为:4 2 5 1 3 6
交换后的中序遍历结果为:6 3 1 5 2 4
```
阅读全文