欢迎访问 生活随笔!

生活随笔

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

二叉树遍历(已知先序和中序)

发布时间:2024/9/3 编程问答 9 豆豆
生活随笔 收集整理的这篇文章主要介绍了 二叉树遍历(已知先序和中序) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

4931: 二叉树遍历
Time Limit: 1 Sec Memory Limit: 32 MB
Description
二叉树的前序、中序、后序遍历的定义:
前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。
Input

两个字符串,其长度n均小于等于26。
第一行为前序遍历,第二行为中序遍历。
二叉树中的结点名称以大写字母表示:A,B,C…最多26个结点。
Output

输入样例可能有多组,对于每组测试样例,
输出一行,为后序遍历的字符串。
Sample Input

ABC CBA ABCDEFG DCBAEFG

Sample Output

CBA DCBGFEA

HINT
Source
数据结构高分笔记
代码~:

#include <stdio.h>#include <string.h>char a[30],b[30];int root;void Find(int x,int y){int k = root,j;if(x < y){for( j = x; j <= y; j++)if(b[j] == a[root]) break;root++;Find(x,j-1);Find(j+1,y);printf("%c",a[k]);}if(x == y){printf("%c",a[root]);root++;}}int main(){memset(a,'\0',sizeof(a));memset(b,'\0',sizeof(b));while(~scanf("%s%s",a,b)){int lenth =strlen(a);root = 0;Find(0,lenth-1);printf("\n");memset(a,'\0',sizeof(a));memset(b,'\0',sizeof(b));}return 0;}

总结

以上是生活随笔为你收集整理的二叉树遍历(已知先序和中序)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错,欢迎将生活随笔推荐给好友。