原题链接:蓝桥杯算法训练VIP-求先序排列
解题思路:
大体的思路,坐标法(自己瞎取的名字)
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | #include<stdio.h> #include<string.h> char ju[20][20] = { '\0' }; char xian[20] = { '\0' }; char zhong[20] = { '\0' }; char hou[20] = { '\0' }; int index = 0; //先序的下标 int root = 0; //总根 int len = 0; //长度 void left_tree( int i, int j) { int x, y; for (x = i + 1; x < len; x++) { for (y = 0; y < j; y++) { if (ju[x][y] == '1' ) { xian[index++] = zhong[y]; //根节点,先存进去 ju[x][y] = 0; left_tree(x, y); } } } return ; } void right_tree( int i, int j) { int x, y; for (x = i + 1; x < len; x++) { for (y = root+1; y < j; y++) //一直到当前根的左边 { if (ju[x][y] == '1' ) { xian[index++] = zhong[y]; //根节点,先存进去 ju[x][y] = 0; left_tree(x, y); } } } return ; } int main() { int f = 0; int i, j = 0; f = scanf ( "%s" , zhong); f = getchar (); f = scanf ( "%s" , hou); f = getchar (); int len_flag = strlen (zhong); len= strlen (zhong); //进行标记 while (len_flag) { int x = 0; //几行,就是后序的 int y = 0; //几列,中序的 for (i = len_flag - 1; i >= 0; i--) //后序//为了降低时间复杂度,把len变成len_flag { for (j = 0; j < len; j++) //中序 { if (hou[i] == zhong[j]) { ju[len-i-1][j] = '1' ; //标记一下 goto this_; } } } this_: len_flag--; } //检验ju数组的标记 /*for (i = 0; i < len; i++) { for (j = 0; j < len; j++) { printf("%c ", ju[i][j]); } printf("\n"); }*/ for (j = 0; j < len; j++) { if (ju[0][j] == '1' ) { root = j; //把根节点拿出来 } } int root_mid = 0; //存根节点 xian[index++] = zhong[root]; //先存根,再调用函数看左边一直循环 //下面就递归了 //根节点左边 for (i = 0; i < len; i++) { for (j = 0; j < root; j++) { if (ju[i][j] == '1' ) { xian[index++] = zhong[j]; ju[i][j] = 0; left_tree(i,j); //传进去,i,j就变成了新的根节点 //这个就是中序排列,第j个位置的结点名 } } } //根节点右边 for (i = 1; i < len; i++) { for (j = root+1; j < len; j++) { if (ju[i][j] == '1' ) { xian[index++] = zhong[j]; ju[i][j] = 0; right_tree(i, j); //传进去,i,j就变成了新的根节点 //这个就是中序排列,第j个位置的结点名 } } } puts (xian); return 0; } |
9.9 分
6 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复