根据后序和中序遍历输出先序遍历c语言
时间: 2023-04-28 08:04:02 浏览: 81
这道题需要用到递归的思想,具体步骤如下:
1. 根据后序遍历找到根节点,即最后一个元素。
2. 在中序遍历中找到根节点的位置,将中序遍历分为左子树和右子树。
3. 根据左子树和右子树的元素个数,将后序遍历也分为左子树和右子树。
4. 递归处理左子树和右子树,直到只剩下一个元素。
5. 输出当前节点的值,即为先序遍历。
下面是c语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int findRoot(int* inorder, int inStart, int inEnd, int rootVal) {
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
return i;
}
}
return -1;
}
TreeNode* buildTree(int* inorder, int inStart, int inEnd, int* postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return NULL;
}
int rootVal = postorder[postEnd];
int rootIndex = findRoot(inorder, inStart, inEnd, rootVal);
int leftSize = rootIndex - inStart;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = rootVal;
root->left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
root->right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
return root;
}
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
int inorder[] = { 4, 2, 5, 1, 6, 3 };
int postorder[] = { 4, 5, 2, 6, 3, 1 };
int n = sizeof(inorder) / sizeof(int);
TreeNode* root = buildTree(inorder, 0, n - 1, postorder, 0, n - 1);
printf("先序遍历结果为:");
preorderTraversal(root);
return 0;
}
```
输出结果为:先序遍历结果为:1 2 4 5 3 6
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)