首页 > 代码库 > 华科机考:二叉树遍历
华科机考:二叉树遍历
时间限制:1秒 空间限制:32768K
题目描述
二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。
输入描述: 两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。
输出描述: 输入样例可能有多组,对于每组测试样例, 输出一行,为后序遍历的字符串。
输入例子: ABC
BAC
FDXEAG
XDEFAG
输出例子: BCA
XEDGAF
思路:1.通过前序序列找到根节点,然后以此节点为基础将中序序列分为两部分,大家平时这样的题也做过不少,现在是让用程序实现这一过程。
2.显然应该用递归实现这一过程,但实现递归,最重要的就是传参,这里我们设置4个参数,travel(char pre[],char inorder[],char post[],int length)
前三个分别对应前序,中序,后序序列,第四个则表示串长。
具体分析过程:
前序:FDXEAG
后序:XDEFAG
自己画了一下大致的过程:
大家可以看到以根节点为分界的点,无论是前序还是中序都分布在同一侧诶
具体实现的过程:
1. 先用一个for循环确定到根在中序序列中的位置,然后就可以对post数组进行赋值(将该值放置在post数组最后)
2.假设根的下标为i,则左串长度为i,pre数组的首地址为pre+1,inorder数组的首地址不需要移动,post数组的首地址不需要移动
即:travel(pre+1,inorder,post,i);
3.右串的长度为length-1-i,pre数组的首地址为pre+i+1,inorder数组的首地址位inorder+i+1,post数组的首地址为post+i;
4.当length<=0时,为递归出口
代码:
#include <iostream> #include <string.h> using namespace std; void travel(char pre[],char inorder[],char post[],int length){ if(length<=0) return; int i; for(i=0;i<length;i++) if(inorder[i]==pre[0]) break; post[length-1]=pre[0]; travel(pre+1,inorder,post,i); travel(pre+i+1,inorder+i+1,post+i,length-1-i); } int main(){ char pre[30],inorder[30],post[30]; while(cin>>pre){ cin>>inorder; travel(pre,inorder,post,strlen(pre)); //post[strlen(pre)]=‘\0‘; for(int i=0;i<strlen(pre);i++) cout<<post[i]; cout<<endl; } return 0; }
这里需要强调一下,这题如果要用cout或者printf()输出的话,需要在数组最后面加上‘\0‘,因为这题需要输入多组数组诶,当后来的串比前面要短时,就可能会发生错误。
华科机考:二叉树遍历