寒假训练--树与二叉树--数据结构实验之求二叉树后序遍历和层次遍历

发布时间:2016-12-7 0:05:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"寒假训练--树与二叉树--数据结构实验之求二叉树后序遍历和层次遍历",主要涉及到寒假训练--树与二叉树--数据结构实验之求二叉树后序遍历和层次遍历方面的内容,对于寒假训练--树与二叉树--数据结构实验之求二叉树后序遍历和层次遍历感兴趣的同学可以参考一下。

数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述  已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历。 输入  输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的先序遍历序列,第二个字符串表示二叉树的中序遍历序列。 输出 每组第一行输出二叉树的后序遍历序列,第二行输出二叉树的层次遍历序列 示例输入 2 abdegcf dbgeafc xnliu lnixu 示例输出 dgebfca abcdefg linux xnuli 提示   来源 ma6174 示例程序  #include <stdio.h> #include <string.h> typedef struct node{ int data ; node *lchild , *rchild ; }*tree; int getk(char ch,char ino[],int is,int n) { for(int i = is ; i <= is + n -1 ; i++) if(ino[i]==ch)return i; } void gettree(tree &t,char pre[],char ino[],int ps,int is,int n) { if(n==0) t = NULL; else { t = new node; t->data = pre[ps]; int k = getk(pre[ps],ino,is,n); if(k == is) t->lchild = NULL; else gettree(t->lchild,pre,ino,ps+1,is,k-is); if(k == is+n-1) t->rchild = NULL; else gettree(t->rchild,pre,ino,ps+1+(k-is),k+1,n-1-(k-is)); } } void pritree1(tree t) { if(t){ pritree1(t->lchild); pritree1(t->rchild); printf("%c", t->data); } } void pritree2(tree t){ int low = 0 , top = 0 ; tree p[100] ; p[top++] = t ; while(low < top) { if(p[low]->lchild) p[top++] = p[low]->lchild; if(p[low]->rchild) p[top++] = p[low]->rchild; printf("%c", p[low++]->data); } } int main() { int i , n ; char pre[100] , ino[100] ; tree head; scanf("%d", &n); for(i = 1 ; i <= n ; i++) { memset(pre,0,sizeof(pre)); memset(ino,0,sizeof(ino)); scanf("%s%s", pre,ino); gettree(head,pre,ino,0,0,strlen(pre)); pritree1(head); printf("\n"); pritree2(head); printf("\n"); } }

上一篇:距离和相似度度量
下一篇:POJ1083 解题报告

相关文章

相关评论