HAPPY_2018 Summer_Week03
7-1 是否同一棵二叉搜索树(25 分) 7-2 还原二叉树(25 分) 7-3 树的同构(25 分) 7-4 朋友圈(25 分)20/25 7-6 是否完全二叉搜索树(30 分)
7-1 是否同一棵二叉搜索树(25 分) 给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L,分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列。最后L行,每行给出N个插入的元素,属于L个需要检查的序列。
简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。
输出格式:
对每一组需要检查的序列,如果其生成的二叉搜索树跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes
No
No
我在网上查了发现有三种思路,我自己的思路是最朴素最暴力的一种,就是两个序列分别建树,然后对比是否相同.有一点需要注意的是这个树可能是一棵斜向的搜索树,也就是给定的序列是递增的,所以说在检索时,检索的长度时给定的序列长度n的四倍.
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 #include <stdio.h> #include <stdlib.h> #include <string.h> int BST1[1000000 ];int BST2[1000000 ];long long n;void Build (int k,int data,int * BST) { if (data >= BST1[k]) { if (BST[2 * k + 1 ] == -1 ) { BST[2 * k + 1 ] = data; } else { Build(k * 2 + 1 , data,BST); } } else { if (BST[2 * k] == -1 ) { BST[2 * k] = data; } else { Build(2 * k, data,BST); } } } int main (int argc, const char * argv[]) { long long L; while (scanf ("%lld" ,&n) != EOF && n) { memset (BST1,-1 ,sizeof (BST1)); int x; scanf ("%lld" ,&L); scanf ("%d" ,BST1 + 1 ); for (int i = 2 ; i <= n; i++) { scanf ("%d" ,&x); Build(1 , x, BST1); } while (L--) { memset (BST2,-1 ,sizeof (BST2)); scanf ("%d" ,BST2 + 1 ); for (int i = 2 ; i <= n; i++) { scanf ("%d" ,&x); Build(1 , x, BST2); } int i; for (i = 1 ; i <= 4 * n; i++) { if (BST1[i] != BST2[i]) { break ; } } if (i == 4 * n + 1 ) { puts ("Yes" ); } else { puts ("No" ); } } } return 0 ; }
第二种思路是根据根节点把序列分为左右两个字树
例如 3 1 2 4 和 3 4 1 2
这里分别划成了 {1, 2} 3 {4} 和 {1, 2} 3 {4}
如果是 3 1 2 4 和 3 2 4 1
则是划成了 {1, 2} 3 {4} 和 {2 , 1} 3 {4}
如此便可以判断是否是同一棵树
第三种是建树然后比较两个树的节点是否一样.
7-2 还原二叉树(25 分) 给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。
输入格式:
输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。
输出格式:
输出为一个整数,即该二叉树的高度。
输入样例:
9
ABDFGHIEC
FDHGIBEAC
输出样例:
5
这个是上课讲的原题,就是根据先序序列确定树根,然后在中序序列中找到树根的位置就能将中序序列划分为左右子树,然后递归这个过程就能还原这棵树.
确定这棵树的高度就是找左右子树最大高度加1 因为有个树根,因此也是个递归.
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 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> char pre[10000 ];char in[10000 ];int n;typedef struct BST * Tree ;struct BST { char data; Tree left; Tree right; }; int max (int x,int y) { return x > y ? x : y; } Tree Insert (char * _pre,char * _in,int n) { Tree t; if (n <= 0 ) { t = NULL ; } else { t = (Tree)malloc (sizeof (struct BST)); t -> data = *_pre; char *p = _in; while (*p != *_pre && p){ p++; } int len = p - _in; t -> left = Insert(_pre + 1 , _in, len); t -> right = Insert(_pre + len + 1 , p + 1 , n - len - 1 ); } return t; } int getHeight (Tree t) { int l = 0 ,r = 0 ; if (t) { l = getHeight(t -> left); r = getHeight(t -> right); return max(l, r) + 1 ; } else { return 0 ; } } int main (int argc, const char * argv[]) { Tree t; scanf ("%d" ,&n); getchar(); scanf ("%s %s" ,pre,in); t = Insert(pre, in, n); printf ("%d" ,getHeight(t)); return 0 ; }
7-3 树的同构(25 分) 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。
图1 图2
现给定两棵树,请你判断它们是否是同构的。
输入格式:
输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N−1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。
输出格式:
如果两棵树是同构的,输出“Yes”,否则输出“No”。
输入样例1(对应图1):
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
输出样例1:
Yes
输入样例2(对应图2):
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
输出样例2:
No
建树的过程需要两个临时char类型变量接收左右子树的地址,如果左右子树存在(不是’-‘)那么就在数组中标记出来,因为给定的是连续的一串序列,所以没有被标记的就是根节点.
然后是判断同构 这里分为几种情况:
两棵树都是空树
两棵树一棵为空树 一棵不为空树
两棵树都不是空树
针对最后一种情况,还有两种情况, 如果左子树相同了,那么就可以去判断右子树,如果不同,那么判断一下左右子树交换之后是否相同.
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 #include <stdio.h> #include <string.h> #include <stdlib.h> struct Node { char data; int left; int right; }t1[100 ],t2[100 ]; int TreeNode[100 ];int n;int Build (struct Node* t) { int n; memset (TreeNode,0 ,sizeof (TreeNode)); scanf ("%d" ,&n); getchar(); char left,right; for (int i = 0 ; i < n; i++) { scanf ("%c %c %c" ,&t[i].data,&left,&right); getchar(); if (left == '-' ) { t[i].left = -1 ; } else { t[i].left = left - '0' ; TreeNode[t[i].left] = 1 ; } if (right == '-' ) { t[i].right = -1 ; } else { t[i].right = right - '0' ; TreeNode[t[i].right] = 1 ; } } int root = -1 ; for (int i = 0 ; i < n; i++) { if (TreeNode[i] == 0 ) { root = i; break ; } } return root; } int judge (int _t1,int _t2) { if (_t1 == -1 && _t2 == -1 ) { return 1 ; } if ((_t1 == -1 && _t2 != -1 ) || (_t1 != -1 && _t2 == -1 )) { return 0 ; } if (t1[_t1].data != t2[_t2].data) { return 0 ; } if (t1[_t1].left == -1 && t2[_t2].left == -1 ) { return judge(t1[_t1].right, t2[_t2].right); } if (t1[_t1].left != -1 && t2[_t2].left != -1 && t1[t1[_t1].left].data == t2[t2[_t2].left].data) { return judge(t1[_t1].right, t2[_t2].right) && judge(t1[_t1].left, t2[_t2].left); } else { return judge(t1[_t1].right, t2[_t2].left) && judge(t1[_t1].left,t2[_t2].right); } } int main (int argc, const char * argv[]) { int root1,root2; root1 = Build(t1); root2 = Build(t2); if (judge(root1, root2)) { puts ("Yes" ); } else { puts ("No" ); } return 0 ; }
7-4 朋友圈(25 分)20/25 某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出,如果A和B是朋友,且B和C是朋友,则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
输入格式:
输入的第一行包含两个正整数N(≤30000)和M(≤1000),分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息,其中学生从1~N编号:
第i个俱乐部的人数Mi(空格)学生1(空格)学生2 … 学生Mi
输出格式:
输出给出一个整数,表示在最大朋友圈中有多少人。
输入样例:
7 4
3 1 2 3
2 1 4
3 5 6 7
1 6
输出样例:
4
一道并查集的题.
将每个团队的第一个人设为参照,其余的人都是他的子节点,然后遍历查找1——N的每个人的头节点,例如i是一名同学,那么find(i)也就是i的朋友的那个代表,每找到一个find(i)就在数组里对这个下标所在的位置加1,也就是这个圈子的人数加1,最后找出最大值就行.
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 #include <stdio.h> int pre[30010 ];int sum[30010 ];void init () { for (int i = 0 ; i < 30010 ; i++) { pre[i] = i; } } int _find(int x) { if (pre[x] != x) { pre[x] = _find(pre[x]); } return pre[x]; } void join (int x,int y) { int fx = _find(x); int fy = _find(y); if (fx != fy) { pre[fx] = fy; } } int main () { int ans = 0 ; int n,k; scanf ("%d%d" ,&n,&k); init (); int x; for (int i = 0 ; i < k; i++) { scanf ("%d" ,&x); for (int j = 0 ; j < x; j++) { scanf ("%d" ,&pre[i]); } for (int k = 1 ; k < x; k++) { join(pre[0 ],pre[k]); } } for (int i = 1 ; i <= n; i++) { int t = _find(i); sum[t]++; if (ans < sum[t]) { ans = sum[t]; } } printf ("%d\n" ,ans); return 0 ; }
7-6 是否完全二叉搜索树(30 分) 将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。
输入格式:
输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。
输出格式:
将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出YES,如果该树是完全二叉树;否则输出NO。
输入样例1:
9
38 45 42 24 58 30 67 12 51
输出样例1:
38 45 24 58 42 30 12 67 51
YES
输入样例2:
8
38 24 12 45 58 67 42 51
输出样例2:
38 45 24 58 42 12 67 51
NO
做了一部分题,发现BST的题目有时候是不需要真正的用指针去建树的,用数组模拟即可.
完全二叉树的定义: 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;
那么判断思路就是:
1、如果树为空,则直接返回错。
2、如果树不为空:层序遍历二叉树。
3、如果一个结点左右孩子都不为空,将其左右孩子入队列;
4、如果遇到一个结点,左孩子为空,右孩子不为空,则该树一定不是完全二叉树;
5、如果遇到一个结点,左孩子不为空,右孩子为空;或者左右孩子都为空;则该节点之后 的队列中的结点都为叶子节点;该树才是完全二叉树,否则就不是完全二叉树;
那么这道题就是在建完树之后,进行n次循环来输出层序遍历(建好的树的数据的存放顺序就是层序遍历).遇到-1(空节点)计数,理想情况(完全二叉树)正好等于节点数 + 1,如果不满足则不是完全二叉树
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 #include <stdio.h> #include <string.h> #include <stdlib.h> int n;int tree[1000 ];void insert (int index,int data) { if (tree[index] == -1 ) { tree[index] = data; return ; } if (data > tree[index]) { insert(index * 2 , data); } else { insert(index * 2 + 1 , data); } } int main (int argc, const char * argv[]) { int data; scanf ("%d" ,&n); memset (tree, -1 , sizeof (tree)); for (int i = 0 ; i < n; i++) { scanf ("%d" ,&data); insert(1 , data); } int k = 0 ,i = 0 ; while (1 ) { while (tree[i] == -1 ) i++; if (k == 0 ) { printf ("%d" ,tree[i]); } else { printf (" %d" ,tree[i]); } i++; k++; if (k == n) { break ; } } printf ("\n" ); if (i == n + 1 ) { printf ("YES\n" ); } else { printf ("NO\n" ); } return 0 ; }
script>