编写一个可以求己知二叉树各节点的值不同,且已经知道其先序和中序遍历的序列,请生成该二叉树并输出其后序遍历序列,然后将其每一个节点的左右交换,最后输出交换后的二叉树的中序遍历序列的c语言代码
时间: 2023-06-10 21:03:18 浏览: 126
二叉树已知前序和中序遍历,求后序遍历的C++代码实现
4星 · 用户满意度95%
以下是求解该问题的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct Node {
int val; // 节点值
struct Node *left; // 左子节点
struct Node *right; // 右子节点
} Node;
// 根据先序和中序遍历序列生成二叉树
Node* buildTree(int* preorder, int* inorder, int pre_start, int pre_end, int in_start, int in_end) {
if(pre_start > pre_end) { // 先序遍历序列已经遍历完
return NULL;
}
int root_val = preorder[pre_start]; // 根节点值为先序遍历序列的第一个元素
int root_index = -1; // 根节点在中序遍历序列中的位置
for(int i = in_start; i <= in_end; i++) {
if(inorder[i] == root_val) {
root_index = i;
break;
}
}
int left_size = root_index - in_start; // 左子树的节点个数
Node *root = (Node*)malloc(sizeof(Node)); // 构建根节点
root->val = root_val;
root->left = buildTree(preorder, inorder, pre_start+1, pre_start+left_size, in_start, root_index-1); // 构建左子树
root->right = buildTree(preorder, inorder, pre_start+left_size+1, pre_end, root_index+1, in_end); // 构建右子树
return root;
}
// 后序遍历二叉树
void postorderTraversal(Node* root) {
if(root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
// 交换左右子树
Node* swapTree(Node* root) {
if(root == NULL) {
return NULL;
}
Node *left = swapTree(root->left); // 递归交换左子树
Node *right = swapTree(root->right); // 递归交换右子树
root->left = right; // 将原来的左子树赋值给右子树
root->right = left; // 将原来的右子树赋值给左子树
return root;
}
// 中序遍历二叉树
void inorderTraversal(Node* root) {
if(root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
int preorder[] = {1,2,3,4,5,6,7};
int inorder[] = {3,2,4,1,6,5,7};
Node* root = buildTree(preorder, inorder, 0, 6, 0, 6); // 已知先序和中序遍历序列生成二叉树
printf("Original postorder traversal: ");
postorderTraversal(root); // 输出原始二叉树的后序遍历序列
printf("\n");
Node* newRoot = swapTree(root); // 交换左右子树
printf("Swapped inorder traversal: ");
inorderTraversal(newRoot); // 输出交换后的二叉树的中序遍历序列
return 0;
}
```
阅读全文