用c语言编写一个程序,实现由先序遍历序列以及由中序遍历序列构造一棵 二叉树的功 能。 并 用 后 序 遍 历 验 证
时间: 2023-07-16 10:15:02 浏览: 98
二叉树的前序,中序,后序排列C语言程序
以下是用C语言实现的程序,可以实现由先序遍历序列以及由中序遍历序列构造一棵二叉树的功能,并用后序遍历验证:
```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] == root->val) {
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[] = {1, 2, 4, 5, 3, 6};
int inorder[] = {4, 2, 5, 1, 3, 6};
int n = sizeof(preorder) / sizeof(preorder[0]);
struct TreeNode* root = buildTree(preorder, n, inorder, n);
printf("后序遍历结果:");
postorderTraversal(root);
return 0;
}
```
这个程序的主要思路是根据先序遍历和中序遍历构建二叉树,然后用后序遍历验证。在构建二叉树时,我们首先根据先序遍历序列确定根节点,然后在中序遍历序列中定位根节点的位置,将序列分为左子树和右子树两部分,然后递归地构建左子树和右子树。最后,我们用后序遍历验证二叉树是否正确构建。
在本程序中,我们使用了一个结构体`TreeNode`来定义二叉树节点,并实现了两个函数:`buildTree`和`postorderTraversal`。`buildTree`函数用于构建二叉树,它接受先序遍历序列和中序遍历序列两个参数,返回二叉树的根节点。`postorderTraversal`函数用于后序遍历二叉树,并将遍历结果输出到控制台。
在主函数中,我们先定义了先序遍历序列和中序遍历序列,并计算序列长度。然后,我们调用`buildTree`函数构建二叉树,并调用`postorderTraversal`函数输出后序遍历结果。最后,程序将返回0,表示正常退出。
阅读全文