求二叉树的先序遍历

2019-11-08 20:01:04

字体：大中小

来源：转载

供稿：网友

PRoblem Description

已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历 Input

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。 Output

输出二叉树的先序遍历序列 Example Input

2 dbgeafc dgebfca lnixu linux Example Output

abdegcf xnliu Hint

Author

GYX

#include<stdio.h>#include<stdlib.h>#include<string.h>struct node{ int data; struct node *l, *r;};struct node *creat(int n, char *a, char *b){ int i; struct node *root; if(n == 0) return NULL;//第二次忘了空节点。。。 root = (struct node *) malloc(sizeof(struct node));//要给root分配空间，第一次忘了。。。 root -> data = b[n-1]; for(i = 0; i < n; i++) { if(a[i] == b[n-1]) break; } printf("%c", root -> data); root -> l = creat(i, a, b); root -> r = creat(n - i - 1, a + i + 1, b + i); return root;};int main(){ int t; scanf("%d", &t); char a[55], b[55]; while(t--) { scanf("%s%s", a, b); int n = strlen(a); creat(n, a, b); printf("/n"); } return 0;}

先序中序后序知道两个可以求另外一个了，就是有的判断别忘了，感觉有点灵性了。

上一篇：头文件iomanip用法

下一篇：线段树洛谷P2894 [USACO08FEB]酒店Hotel