用c语言完成下题,假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二叉树,并写出其先序序列和后序序列。
时间: 2023-08-10 18:33:53 浏览: 87
利用中序和前(后)序画出二叉树
根据中序序列的性质,我们可以知道根节点一定是中间的节点,即C。然后我们可以根据C将前面的序列和后面的序列分成两个子树的序列,前面的为DBGEHJ,后面的为IF。对于前面的序列,我们可以再次使用中序序列的性质,发现E是其根节点,然后将前面的和后面的序列分开,得到DBG和HJ。以此类推,可以得出如下的二叉树:
```
C
/ \
/ \
/ \
B F
/ \ / \
D G I J
\
E
```
根据先序遍历的定义,我们可以得到先序序列为CBGDHEFJIJ,后序遍历的定义则是先遍历左子树,再遍历右子树,最后遍历根节点,因此后序序列为DGEBJHIFCA。
以下是使用C语言实现该二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 根据中序序列和前序序列构造二叉树
TreeNode* buildTree(char* inorder, char* preorder, int inorderStart, int inorderEnd, int preorderStart, int preorderEnd) {
if (inorderStart > inorderEnd || preorderStart > preorderEnd) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[preorderStart];
int inorderIndex = inorderStart;
while (inorderIndex <= inorderEnd && inorder[inorderIndex] != root->val) {
inorderIndex++;
}
int leftSize = inorderIndex - inorderStart;
root->left = buildTree(inorder, preorder, inorderStart, inorderIndex - 1, preorderStart + 1, preorderStart + leftSize);
root->right = buildTree(inorder, preorder, inorderIndex + 1, inorderEnd, preorderStart + leftSize + 1, preorderEnd);
return root;
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
int main() {
char* inorder = "DBGEHJACIF";
char* preorder = "CBGDHEFJIJ";
TreeNode* root = buildTree(inorder, preorder, 0, 8, 0, 8);
printf("先序遍历:");
preorderTraversal(root);
printf("\n");
printf("后序遍历:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
输出结果为:
```
先序遍历:CBGDHEFJIJ
后序遍历:DGEBJHIFCA
```
阅读全文