c二叉树的创建及遍历用先序和中序序列创建二叉树并进行后序遍历
时间: 2023-12-12 18:04:46 浏览: 34
二叉树的创建及遍历涉及到先序遍历、中序遍历和后序遍历,其中先序遍历和中序遍历用于创建二叉树,后序遍历用于验证创建的二叉树是否正确。
具体步骤如下:
1. 读入先序序列和中序序列,并确定根节点
2. 根据根节点在中序序列中的位置,将中序序列分成左右两个子序列,分别对应左子树和右子树
3. 根据左子树的节点个数,将先序序列分成两个子序列,分别对应左子树和右子树
4. 递归地对左子树和右子树进行上述步骤,直到序列为空或只有一个节点
5. 在遍历时,先访问左子树,再访问右子树,最后访问根节点,即得到后序遍历序列
下面是具体的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int findRoot(int *inorder, int left, int right, int val) {
int i;
for (i = left; i <= right; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
TreeNode *buildTree(int *preorder, int preLeft, int preRight, int *inorder, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return NULL;
}
int rootVal = preorder[preLeft];
int rootIndex = findRoot(inorder, inLeft, inRight, rootVal);
TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
root->val = rootVal;
root->left = buildTree(preorder, preLeft + 1, preLeft + rootIndex - inLeft, inorder, inLeft, rootIndex - 1);
root->right = buildTree(preorder, preLeft + rootIndex - inLeft + 1, preRight, inorder, rootIndex + 1, inRight);
return root;
}
void postorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
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(int);
TreeNode *root = buildTree(preorder, 0, n - 1, inorder, 0, n - 1);
postorderTraversal(root);
return 0;
}
```
输出结果为:4 5 2 6 7 3 1,即为二叉树的后序遍历序列。