cloned

 

一道笔试题——输入二叉树的前序和中序遍历序列,输出后序遍历序列

算法:
1  如果输入序列长度小于等于0,结束
2  输入的前序序列的第一个节点是后序遍历的最后一个节点,将这个节点保存到output变量中
3  把输入的两个序列拆成4部分,output节点的左子树的前序和中序序列,output节点右子树的前序和中序序列
4  用3中的结果先左后右递归调用该算法
5  输出output

代码如下
1 void LastTree::ShowLast(const char *po, const char *mo, int n) 2 { 3 //递归结束条件 4 if(n <= 0) 5 { 6 return; 7 } 8 9 //输出值 10 char output = *po; 11 12 //output节点的左子树中序序列 13 int i = 0; 14 char *lmct = (char*)malloc(n*sizeof(char)); 15 memset(lmct, 0, n); 16 while(*(mo + i) != output) 17 *(lmct + i) = *(mo + i++); 18 int lnum = i; 19 i++; 20 21 //output节点的右子树中序序列 22 int j = 0; 23 char *rmct = (char*)malloc(n*sizeof(char)); 24 memset(rmct, 0, n); 25 while(*(mo + i) != NULL) 26 { 27 *(rmct + j++) = *(mo + i++); 28 } 29 30 //output节点的左子树前序序列 31 char *lpct = (char*)malloc(n*sizeof(char)); 32 memset(lpct, 0, n); 33 int k = 0; 34 35 for(int a = 0; *(po + a); a++) 36 { 37 for(int b = 0; *(lmct + b); b++) 38 { 39 if(*(po + a) == *(lmct + b)) 40 { 41 *(lpct + k++) = *(po + a); 42 break; 43 } 44 45 } 46 } 47 48 //output节点的右子树前序序列 49 char *rpct = (char*)malloc(n*sizeof(char)); 50 memset(rpct, 0, n); 51 k = 0; 52 53 for(int a = 0; *(po + a); a++) 54 { 55 for(int b = 0; *(rmct + b); b++) 56 { 57 if(*(po + a) == *(rmct + b)) 58 { 59 *(rpct + k++) = *(po + a); 60 break; 61 } 62 63 } 64 } 65 66 //先左后右递归 67 ShowLast(lpct, lmct, lnum); 68 ShowLast(rpct, rmct, n - lnum - 1); 69 70 //输出当前节点 71 std::cout<<output; 72 73 free(lmct); 74 free(rmct); 75 free(lpct); 76 free(rpct); 77 lpct = NULL; 78 rpct = NULL; 79 lmct = NULL; 80 rmct = NULL; 81 return; 82 }

测试用例:

1 void main() 2 { 3 LastTree lt; 4 const char *po = "ABCDEFG"; 5 const char *mo = "CBDAEGF"; 6 7 lt.ShowLast(po, mo, 7); 8 9 _getch(); 10 }
输出结果为:CDBGFEA

posted on 2010-12-02 18:49 Cloned 阅读(1236) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜