二叉树知道前序和中序怎么求后序把求出来的序列带入先序遍历二叉树的递归算法中用c语言,把二叉树按层序输出c语言
时间: 2024-01-23 12:44:19 浏览: 89
好的,我是CSDN开发的ChitGPT,可以帮你回答关于计算机和编程的问题。
关于你的第一个问题,如果已知二叉树的前序遍历和中序遍历序列,可以通过递归算法求出其后序遍历序列,具体步骤如下:
1. 如果前序遍历序列的长度为0,则返回空序列。
2. 取前序遍历序列的第一个元素作为根节点。
3. 在中序遍历序列中找到根节点的位置,其左边为左子树的中序遍历序列,右边为右子树的中序遍历序列。
4. 分别求出左子树的前序遍历序列和右子树的前序遍历序列。
5. 递归求解左子树的后序遍历序列和右子树的后序遍历序列。
6. 将左子树的后序遍历序列和右子树的后序遍历序列依次加入到结果序列中,并将根节点的值加入到结果序列中。
7. 返回结果序列。
以下是一个C语言的实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 递归求解二叉树的后序遍历序列
int* postorderTraversal(TreeNode* root, int* returnSize) {
if (root == NULL) {
*returnSize = 0;
return NULL;
}
int* leftSize = (int*)malloc(sizeof(int));
int* rightSize = (int*)malloc(sizeof(int));
int* leftRes = postorderTraversal(root->left, leftSize);
int* rightRes = postorderTraversal(root->right, rightSize);
int size = *leftSize + *rightSize + 1;
int* res = (int*)malloc(sizeof(int) * size);
int index = 0;
for (int i = 0; i < *leftSize; i++) {
res[index++] = leftRes[i];
}
for (int i = 0; i < *rightSize; i++) {
res[index++] = rightRes[i];
}
res[index++] = root->val;
*returnSize = size;
free(leftSize);
free(rightSize);
return res;
}
// 根据前序遍历序列和中序遍历序列构建二叉树(递归)
TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if (preorderSize == 0) {
return NULL;
}
// 取前序遍历序列的第一个元素作为根节点
int val = preorder[0];
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
// 在中序遍历序列中找到根节点位置
int midIndex = 0;
for (int i = 0; i < inorderSize; i++) {
if (inorder[i] == val) {
midIndex = i;
break;
}
}
// 分别构建左子树和右子树
root->left = buildTree(preorder + 1, midIndex, inorder, midIndex);
root->right = buildTree(preorder + 1 + midIndex, preorderSize - midIndex - 1, inorder + midIndex + 1, inorderSize - midIndex - 1);
return root;
}
// 层序遍历二叉树
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
printf("null");
return;
}
TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * 1000);
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
TreeNode* node = queue[head++];
printf("%d ", node->val);
if (node->left != NULL) {
queue[tail++] = node->left;
}
if (node->right != NULL) {
queue[tail++] = node->right;
}
}
}
int main() {
// 二叉树的前序遍历序列和中序遍历序列
int preorder[] = {1, 2, 4, 5, 3, 6};
int inorder[] = {4, 2, 5, 1, 3, 6};
int size = sizeof(preorder) / sizeof(int);
// 构建二叉树
TreeNode* root = buildTree(preorder, size, inorder, size);
// 求解二叉树的后序遍历序列
int* postorder = postorderTraversal(root, &size);
// 将后序遍历序列带入递归算法中获取原二叉树
root = buildTree(postorder, size, inorder, size);
// 层序遍历二叉树
levelOrderTraversal(root);
free(postorder);
return 0;
}
```
希望对你有所帮助。如果还有其他问题,可以继续问我哦。
阅读全文