己知二叉树各节点的值不同,且已经知道其先序和中序遍历的序列,请生成该二叉树并输出其后序遍历序列,然后将其每一个节点的左右交换,最后输出交换后的二叉树的中序遍历序列,C语言实现
时间: 2023-06-11 22:05:33 浏览: 98
好的,你的问题是如何使用先序和中序遍历序列生成二叉树,并输出后序遍历序列,最后交换每个节点的左右子树,输出交换后的二叉树的中序遍历序列,对吧?
首先,我们可以将先序遍历序列第一个元素作为根节点,然后在中序遍历序列中找到该根节点,并且将中序遍历序列分成左子树和右子树两部分。由于二叉树的左子树和右子树也是二叉树,因此我们可以使用递归的方式生成它们。
以下是 C 语言代码实现:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct BTNode {
int data;
struct BTNode *left;
struct BTNode *right;
} BTNode;
/**
* 根据先序和中序遍历序列生成二叉树
*
* @param preorder 先序遍历序列
* @param inorder 中序遍历序列
* @param n 序列中的元素个数
* @param preStart 先序遍历序列的起始位置
* @param inStart 中序遍历序列的起始位置
*
* @return 生成的二叉树的根节点
*/
BTNode* buildBinaryTree(int *preorder, int *inorder, int n, int preStart, int inStart) {
if (n <= 0) {
return NULL;
}
// 先序遍历序列的第一个元素是根节点
int rootValue = preorder[preStart];
BTNode *root = (BTNode*)malloc(sizeof(BTNode));
root->data = rootValue;
// 在中序遍历序列中找到根节点
int i;
for (i = inStart; i < inStart + n; ++i) {
if (inorder[i] == rootValue) {
break;
}
}
// 左子树的元素个数为 i - inStart
int leftTreeSize = i - inStart;
// 递归生成左子树和右子树
root->left = buildBinaryTree(preorder, inorder, leftTreeSize, preStart + 1, inStart);
root->right = buildBinaryTree(preorder, inorder + leftTreeSize + 1, n - leftTreeSize - 1, preStart + leftTreeSize + 1, i + 1);
return root;
}
/**
* 后序遍历输出二叉树节点
*
* @param node 二叉树节点
*/
void printPostorder(BTNode *node) {
if (node != NULL) {
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
}
/**
* 交换二叉树的左右子树
*
* @param node 二叉树节点
*/
void swapChild(BTNode *node) {
if (node == NULL) {
return;
}
BTNode *tmp = node->left;
node->left = node->right;
node->right = tmp;
swapChild(node->left);
swapChild(node->right);
}
/**
* 中序遍历输出二叉树节点
*
* @param node 二叉树节点
*/
void printInorder(BTNode *node) {
if (node != NULL) {
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
}
int main() {
int preorder[] = {1, 2, 4, 5, 3, 6, 7};
int inorder[] = {4, 2, 5, 1, 6, 3, 7};
int n = sizeof(preorder) / sizeof(preorder[0]);
// 生成二叉树
BTNode *root = buildBinaryTree(preorder, inorder, n, 0, 0);
// 输出后序遍历序列
printf("The postorder of the original tree: ");
printPostorder(root);
printf("\n");
// 交换二叉树的左右子树
swapChild(root);
// 输出交换后的中序遍历序列
printf("The inorder of the swapped tree: ");
printInorder(root);
printf("\n");
return 0;
}
```
这里使用了一个简单的二叉树结构体 BTNode,包含了节点的值 data 以及左右子树指针 left 和 right。
首先我们定义了一个递归函数 buildBinaryTree,它根据先序和中序遍历序列,生成二叉树的过程和常规的类似。需要注意的是,在递归生成右子树的时候,中序遍历序列的起始位置需要加上左子树的元素个数和根节点的位置。
接着我们定义了一个输出后序遍历序列的函数 printPostorder,它使用递归的方式,先输出左子树的节点、右子树的节点,最后输出根节点的值。
然后我们定义了一个交换二叉树左右子树的函数 swapChild,它也是使用递归的方式,首先交换节点的左右子树,然后递归调用这个函数交换左子树和右子树。
最后我们定义了一个输出中序遍历序列的函数 printInorder,也是使用递归的方式,先输出左子树的节点,然后输出根节点的值,最后输出右子树的节点。
在 main 函数中,我们调用 buildBinaryTree 生成二叉树,然后调用 printPostorder 输出原二叉树的后序遍历序列。接着调用 swapChild 交换二叉树的左右子树,最后调用 printInorder 输出交换后的二叉树的中序遍历序列。
在执行的过程中,如果有任何问题,请随时与我交流。
阅读全文