本文主要是介绍九度OJ 1078:二叉树遍历 (二叉树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 题目描述:
-
二叉树的前序、中序、后序遍历的定义:
前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。
- 输入:
-
两个字符串,其长度n均小于等于26。
第一行为前序遍历,第二行为中序遍历。
二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。
- 输出:
-
输入样例可能有多组,对于每组测试样例,
输出一行,为后序遍历的字符串。
- 样例输入:
-
ABC BAC FDXEAG XDEFAG
- 样例输出:
-
BCA XEDGAF
- 来源:
- 2006年清华大学计算机研究生机试真题
思路:
并不需要还原树,直接由前序和中序求就行。
主要是弄清楚三种遍历的定义。
代码:
#include <stdio.h>
#include <string.h>//void print(char *s, int len)
//{
// for (int i=0; i<len; i++)
// printf("%c", s[i]);
// printf("\n");
//}void getAfter(char *b, char *m, char *a, int len)
{if (len == 1){a[0] = b[0];return;}int root = b[0];int i;for (i=0; i<len; i++){if (m[i] == root)break;}a[len-1] = root;//print(b, len);//print(m, len);//print(a, len);if (i > 0)getAfter(b+1, m, a, i);if (len-1-i > 0)getAfter(b+1+i, m+1+i, a+i, len-1-i);
}
int main(void)
{char b[30], m[30], a[30];int len;while (scanf("%s", b) != EOF){scanf("%s", m);len = strlen(b);//for (int i=0; i<len; i++)// a[i] = '0';getAfter(b, m, a, len);a[len] = '\0';printf("%s\n", a);}return 0;
}
/**************************************************************Problem: 1078User: liangrx06Language: CResult: AcceptedTime:0 msMemory:912 kb
****************************************************************/
这篇关于九度OJ 1078:二叉树遍历 (二叉树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!