给定二叉树前序遍历,求中序遍历,用c语言实现
时间: 2023-04-04 12:01:29 浏览: 55
好的,这个问题可以回答。以下是一个用 C 语言实现的函数,可以根据给定的前序遍历数组和节点数量,计算出对应的中序遍历数组。
```c
void preorder_to_inorder(int* preorder, int* inorder, int n) {
if (n == ) {
return;
}
int root = preorder[];
int i;
for (i = ; i < n; i++) {
if (inorder[i] == root) {
break;
}
}
preorder_to_inorder(preorder + 1, inorder, i);
preorder_to_inorder(preorder + i + 1, inorder + i + 1, n - i - 1);
printf("%d ", root);
}
```
这个函数的基本思路是,首先找到前序遍历的第一个节点,即根节点。然后在中序遍历中找到这个节点的位置,这个位置左边的节点都是左子树的节点,右边的节点都是右子树的节点。然后递归处理左子树和右子树,直到处理完所有节点。在递归的过程中,我们可以通过打印根节点的方式,输出中序遍历的结果。
希望这个回答能够帮到你!
相关问题
使用C语言实现给定二叉树前序遍历,求中序遍历
可以使用递归的方式实现二叉树的前序遍历和中序遍历。具体实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createTree(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
// 创建二叉树
TreeNode* root = createTree(1);
root->left = createTree(2);
root->right = createTree(3);
root->left->left = createTree(4);
root->left->right = createTree(5);
// 前序遍历
printf("前序遍历结果:");
preorderTraversal(root);
printf("\n");
// 中序遍历
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
return ;
}
```
输出结果为:
```
前序遍历结果:1 2 4 5 3
中序遍历结果:4 2 5 1 3
```
请用c语言写代码:给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历
#include<stdio.h>
#include<stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if(preorderSize == 0 || inorderSize == 0) return NULL;//递归终止条件
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));//新建根节点
root->val = preorder[0];
int i;
for(i = 0; i < inorderSize; i++) {//寻找根节点在中序遍历中的位置
if(inorder[i] == preorder[0]) {
break;
}
}
root->left = buildTree(preorder + 1, i, inorder, i);//建立左子树
root->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);//建立右子树
return root;
}
void postorderTraversal(struct TreeNode* root) {//后序遍历
if(root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
int main() {
int preorder[6] = {1, 2, 4, 5, 3, 6};
int inorder[6] = {4, 2, 5, 1, 3, 6};
struct TreeNode* root = buildTree(preorder, 6, inorder, 6);
postorderTraversal(root);
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)