二叉搜索树+前序遍历 -> 后序遍历

2019-11-10 20:08:49

字体：大中小

来源：转载

供稿：网友

sdut原题链接

迷失の搜索树 Time Limit: 1000MS Memory Limit: 65536KB

PRoblem Description 小璐在机缘巧合之下获得了一个二叉搜索树，这个二叉搜索树恰好有n个节点，每个节点有一个权值，每个节点的权值都在[1,n]这个区间内，并且两两不相同，真是优美的性质啊但是命运的不公又让她失去了这个二叉搜索树幸运的是，她还记得自己丢失的二叉搜索树的前序遍历序列。在丢了二叉搜索树之后，小璐无比想念她的这个树的后序遍历那么问题来了，聪明的你在知道这个二叉搜索树的前序遍历的序列的情况下，能帮她找到这个二叉搜索树的后序遍历嘛?

Input 多组输入，以文件结尾每组数据第一行为一个整数n，代表这个二叉搜索树的节点个数(1<=n<=100) 接下来一行n个整数，代表这个二叉搜索树的前序遍历序列

Output 输出n个整数表示这个二叉树的后序遍历序列

Example Input 5 4 2 1 3 5

Example Output 1 3 2 5 4

Hint 二叉查找树是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树 Author 2016暑假集训结训赛 by QAQ

以下为accepted代码

#include <stdio.h>#include <stdlib.h>typedef struct node{ int date; struct node *left; struct node *right;}BinTree;BinTree *root;int num[140], flag;BinTree * Insert(BinTree *rt, int x)//二分查找树的插入算法{ if(!rt){ rt = (BinTree *)malloc(sizeof(BinTree)); rt->date = x; rt->left = rt->right = 0; } else { if(x < rt->date) rt->left = Insert(rt->left, x); else rt->right = Insert(rt->right, x); } return rt;}void last_put(BinTree *rt)//中序遍历{ if(rt) { last_put(rt->left); last_put(rt->right); num[flag++] = rt->date; }}int main(){ int n, i, x; while(scanf("%d", &n) != EOF) { flag = 0;///注意初始化 root = NULL;///注意初始化 for(i = 0; i < n; i++) { scanf("%d", &x); root = Insert(root, x);//调用二分查找树的插入函数 } last_put(root);//调用中序遍历函数 for(i = 0; i < n; i++) { printf("%d%c", num[i], i == n-1? '/n': ' '); } } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 8msTake Memory: 584KBSubmit time: 2017-02-08 18:26:18****************************************************/

以下为runtime error代码

#include <stdio.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;} BinTree;BinTree *rt;int num[140];int flag;BinTree * get_build(int len, char *st1, char *st2){ if(len == 0) return NULL; int i; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0]; for(i = 0; i < len; i++) { if(st2[i] == root->date) break; } root->left = get_build(i, st1+1, st2); root->right = get_build(len-i-1, st1+i+1, st2+i+1); num[flag++] = root->date - '0'; return root;}int cmp(const void *a, const void *b){ return ((*(char *)a)-(*(char *)b));}int main(){ int n, i, x; char st1[140], st2[140]; while(scanf("%d", &n) != EOF) { for(i = 0; i < n; i++) { scanf("%d", &x); st1[i] = x + '0'; st2[i] = st1[i]; } qsort(&st2[0], n, sizeof(st2[0]), cmp); ///printf("%s/n", st2); rt = get_build(n, st1, st2); for(i = 0; i < n; i++) { printf("%d%c", num[i], i == n-1? '/n': ' '); } } return 0;}/***************************************************User name: jk160630Result: Runtime ErrorTake time: 0msTake Memory: 0KBSubmit time: 2017-02-08 17:54:56****************************************************/

上一篇：R 笔记

下一篇：使用flex和bison实现的sql引擎解析