这道题的大部分程序已经完成,题目中的二叉树是根据后序遍历和中序遍历序列建立的,主函数也已经给出,你只需要在适当的位置添加先序遍历二叉树的函数 PreOrder( ) 即可。 #include<stdio.h> #include<stdlib.h> typedef char DataType; typedef struct Node { DataType data; struct Node *lchild, *rchild; }BiTNode, *BinTree; void CreateBinTree_Post_In(BiTNode * &t, DataType post[], DataType in[], int s1, int t1, int s2, int t2) { int i; if (s1 <= t1) { t = (BiTNode*)malloc(sizeof(BiTNode)); t->data = post[t1]; t->lchild = NULL; t->rchild = NULL; for (i = s2; i <= t2; i++) if (in[i] == post[t1]) break; CreateBinTree_Post_In(t->rchild, post, in, s1 + i-s2, t1-1, i+1, t2); CreateBinTree_Post_In(t->lchild, post, in, s1, s1+i-s2-1, s2, i-1); } } /*你的代码段将放在这个位置*/ int main() { char *post, *in; int n; BiTNode *t; while (scanf("%d", &n) != EOF) { post = (char*)malloc(n * sizeof(char)); in = (char*)malloc(n * sizeof(char)); scanf("%s", post); scanf("%s", in);
时间: 2024-04-21 20:30:31 浏览: 18
void PreOrder(BinTree t) {
if (t != NULL) {
printf("%c ", t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}
int main() {
char *post, *in;
int n;
BiTNode *t;
while (scanf("%d", &n) != EOF) {
post = (char*)malloc(n * sizeof(char));
in = (char*)malloc(n * sizeof(char));
scanf("%s", post);
scanf("%s", in);
CreateBinTree_Post_In(t, post, in, 0, n-1, 0, n-1);
printf("PreOrder: ");
PreOrder(t);
printf("\n");
free(post);
free(in);
}
return 0;
}
相关问题
通过 哪些 序列可以确定唯一的二叉树 前序遍历和后序遍历 前序遍历和中序遍历 后序遍历和中序遍历 后序遍历
和中序遍历可以确定唯一的二叉树。
#### 引用[.reference_title]
- *1* *2* *3* [二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解](https://blog.csdn.net/u013834525/article/details/80421684)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}} ] [.reference_item]
[ .reference_list ]
pta二叉树采用二叉链表存储,要求根据给定的后序遍历序列和中序遍历序列建立二叉树
要建立一个使用二叉链表存储的 PTA 二叉树,需要根据给定的后序遍历和中序遍历序列来构建。首先,我们知道二叉树的后序遍历是左子树、右子树、根节点的顺序,而中序遍历是左子树、根节点、右子树的顺序。
为了建立二叉树,我们可以从后序遍历序列中找到根节点,然后在中序遍历序列中找到对应的位置,这样就可以确定左子树和右子树的范围。接下来,我们可以递归地建立左子树和右子树。
具体步骤如下:
1. 从后序遍历序列中找到根节点,假设为 root。
2. 在中序遍历序列中找到 root 的位置,确定左子树和右子树的范围,分别为 [inStart, index - 1] 和 [index + 1, inEnd]。
3. 根据左子树的范围,从后序遍历序列中确定左子树的根节点 leftRoot。
4. 递归地建立左子树,即 buildTree(inorder, postorder, inStart, index - 1)。
5. 根据右子树的范围,从后序遍历序列中确定右子树的根节点 rightRoot。
6. 递归地建立右子树,即 buildTree(inorder, postorder, index + 1, inEnd)。
通过以上步骤,我们可以根据给定的后序遍历和中序遍历序列成功建立二叉树。建立完成后,我们就可以对这棵二叉树进行各种操作,比如遍历、查找等。