c语言实现通过二叉树的先序序列和中序序列构建二叉树,然后在main函数中输入二叉树的先序序列为ABDGCEF,中序遍历序列为DGBAECF,并通过后序遍历算法输出二叉树的后序序列GDBEFCA 并求出该二叉树的深度,在main函数中测试。
时间: 2024-01-23 20:41:54 浏览: 59
可以使用递归的方式实现二叉树的构建和遍历。具体实现过程如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点定义
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 通过先序序列和中序序列构建二叉树
TreeNode* buildTree(char* preorder, char* inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = preorder[preStart];
int rootIndex;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root->data) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
// 后序遍历二叉树
void postorder(TreeNode* root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
printf("%c", root->data);
}
// 求二叉树的深度
int depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
char preorder[] = "ABDGCEF";
char inorder[] = "DGBAECF";
TreeNode* root = buildTree(preorder, inorder, 0, 6, 0, 6);
printf("后序遍历结果:");
postorder(root);
printf("\n");
printf("二叉树深度为:%d\n", depth(root));
return 0;
}
```
输出结果为:
```
后序遍历结果:GDBEFCA
二叉树深度为:3
```
阅读全文