用c语言完整代码并且用例子测试代码写出采用二叉链表存储结构,交换二叉树中每个结点的左孩子和右孩子。
时间: 2023-06-20 11:07:07 浏览: 96
下面是使用二叉链表存储结构的完整C语言代码,实现交换二叉树中每个节点的左孩子和右孩子:
```c
#include<stdio.h>
#include<stdlib.h>
// 二叉树结点的结构体
typedef struct TreeNode{
char data;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode, *pTreeNode;
// 创建二叉树
pTreeNode createTree(){
pTreeNode node = NULL;
char ch;
scanf("%c", &ch);
if(ch != '#'){
node = (pTreeNode)malloc(sizeof(TreeNode));
node->data = ch;
node->left = createTree();
node->right = createTree();
}
return node;
}
// 交换每个节点的左孩子和右孩子
void swapChild(pTreeNode root){
if(root == NULL) return;
pTreeNode temp = root->left;
root->left = root->right;
root->right = temp;
swapChild(root->left);
swapChild(root->right);
}
// 中序遍历二叉树
void inorderTraversal(pTreeNode root){
if(root != NULL){
inorderTraversal(root->left);
printf("%c ", root->data);
inorderTraversal(root->right);
}
}
int main(){
pTreeNode root = NULL;
printf("请输入二叉树的先序遍历序列:\n");
root = createTree();
printf("中序遍历二叉树:\n");
inorderTraversal(root);
printf("\n");
printf("交换二叉树中每个结点的左孩子和右孩子后,中序遍历二叉树:\n");
swapChild(root);
inorderTraversal(root);
printf("\n");
return 0;
}
```
上述代码中,我们首先定义了一个二叉树结点的结构体,包括数据域和左右孩子指针域。然后,我们通过递归方式来创建二叉树,输入的时候使用`#`表示空节点。接着,我们定义了一个`swapChild()`函数,用于交换二叉树中每个节点的左孩子和右孩子,并且在递归过程中对每个节点都进行了交换。最后,我们通过中序遍历函数对交换后的二叉树进行验证。
下面是一个使用例子,假设我们要创建的二叉树的先序遍历序列为`ABD##E##CF###`,则程序运行结果如下:
```
请输入二叉树的先序遍历序列:
ABD##E##CF###
中序遍历二叉树:
D B E A F C
交换二叉树中每个结点的左孩子和右孩子后,中序遍历二叉树:
E D A B C F
```
阅读全文