一、这一章学习了树和二叉树，下面是我的思维导图：
二、实践，小组合作代码及注释
实践2：
1 #include<iostream>
2 using namespace std;
3
4
5 typedef char ElementType;
6 typedef struct TreeNode Tree;
7 //结构体
8 struct TreeNode {
9 ElementType data;
10 int left;
11 int right;
12 }t1[101],t2[101];//t1是第一棵树，t2是第二棵树
13
14 int Build(Tree t[])
15 {//建立二叉树
16 bool a[101] = { false };
17 int n;
18 cin >> n;
19 char data, left, right;
20 for (int i = 0; i < n; i++)
21 {
22 cin >> data >> left >> right;
23 t[i].data = data;
24 //判断左右节点是否空
25 if (left == '-')
26 t[i].left = -1;
27 else {
28 t[i].left = left-'0';
29 a[(int)left - 48] = true;
30 }
31
32 if (right == '-')
33 t[i].right = -1;
34 else {
35 t[i].right = (int)right-48;
36 a[(int)right - 48] = true;
37 }
38 }
39 //判断是不是根节点，根节点没有双亲结点
40 for (int i = 0; i < n; i++)
41 {
42 //cout << t[i].data <<" "<< t[i].left <<" "<< t[i].right <<" "<< a[i] << endl;;
43 if (!a[i])
44 return i;
45 }
46 return -1;
47 }
48
49 bool Compare(int r1,int r2)
50 {
51 if (r1 == -1 && r2 == -1)
52 return true;//都是空，同构
53 else if ((r1 == -1 && r2 != -1) || (r2 == -1 && r1 != -1))
54 return false;//其中一个为空，不同构
55 else if (t1[r1].data != t2[r2].data)
56 return false;//根数据不同，不同构
57 else if (t1[r1].left == -1 && t2[r2].left == -1)
58 return Compare(t1[r1].right, t2[r2].right);//左子树为空，则判断右子树
59 else if ((t1[r1].left != -1 && t2[r2].left != -1) && (t1[t1[r1].left].data == t2[t2[r2].left].data))
60 return Compare(t1[r1].left, t2[r2].left) && Compare(t1[r1].right, t2[r2].right);///两树左子树皆不空，且值相等 ,判断其子树
61 else
62 return Compare(t1[r1].left, t2[r2].right) && Compare(t1[r1].right, t2[r2].left);//两树左子树有一个空 或者 皆不空但值不等,交换左右子树判断
63 }
64
65 int main()
66 {
67 int root1 = Build(t1);
68 int root2 = Build(t2);
69
70 bool flag = Compare(root1, root2);
71 if (flag)
72 cout << "Yes" << endl;
73 else
74 cout << "No" << endl;
75 return 0;
76 }
小组合作：
1 /*思路： 2 1.定义结点的结构体，其中把每个结点的孩子作为一个孩子数组；再定义结构体数组作为树，其中结构体数组的下标就是结点的编号 3 2.创建树并记录根结点的编号（即结构体数组T的下标） 4 3.根据层次遍历的方法，最后一个访问的结点就是最深的叶子结点 5 4.释放动态申请的空间*/ 6 #include<iostream> 7 #include<queue> 8 //#define Max 100000 9 using namespace std; 10 typedef struct 11 {//定义结点 12 int m;//结点的孩子数 13 int* child;//用数组存放结点的孩子们 要释放空间 14 }TNode;//利用数组下标对应结点编号，（所以就不在结构体里定义编号，省空间？） 15 16 int create(TNode *T,int n); 17 void levelOrder(TNode *T,int R); 18 void destroy(TNode *T,int n); 19 20 int main() 21 { 22 int n; 23 cin >> n; 24 TNode* T; 25 T = new TNode[n + 1];//数组下标就是结点的编号 26 int R;//根结点的编号 27 R=create(T, n); 28 levelOrder(T,R); 29 destroy(T,n);//int* child 30 delete[]T;//TNode* T 31 return 0; 32 } 33 int create(TNode* T, int n) 34 { 35 bool* check;//为了查找根结点 36 check = new bool[n + 1];//动态申请check数组的空间 37 //check[n + 1] = { false }; 38 for(int i=0;i<n+1;i++) 39 { 40 check[i]=false;//初始化为false，最后不为true的元素的下标就是根结点的编号 41 } 42 int root=-1;//需要先初始化 43 //开始输入 44 for (int i = 1; i < n + 1; i++) 45 { 46 cin >> T[i].m; 47 if (T[i].m != 0)//如果结点i有孩子 48 { 49 int ch; 50 T[i].child = new int[T[i].m];//为结点i申请m个孩子的空间 51 for (int j = 0; j < T[i].m; j++) 52 { 53 cin >> ch; 54 T[i].child[j] = ch; 55 check[ch] = true; 56 } 57 } 58 59 } 60 for (int i = 1; i < n + 1; i++) 61 { 62 if (check[i] == false)//此时i就是根结点的编号 63 { 64 root = i; 65 break; 66 } 67 } 68 delete []check ;//因为 check = new bool[n + 1] 69 return root; 70 } 71 void levelOrder(TNode* T,int R) 72 { 73 queue<int> Q; 74 Q.push(R);//根结点先入队，R就代表根结点，而不是T[R]或者T[R]的成员，因为在结构体里面没有表示结点编号的成员 75 int e;//记录出队的队头元素 76 while(!Q.empty()) 77 { 78 e=Q.front();//先把队头元素的值赋给e 79 Q.pop();//再让队头出队 80 if(T[e].m!=0)//如果刚出队的队头e有孩子，就让它的孩子们入队 81 { 82 for(int k=0;k<T[e].m;k++) 83 Q.push(T[e].child[k]); 84 } 85 } 86 cout<<e<<endl;//最后一个出队的就是最深叶子 87 } 88 void destroy(TNode *T,int n) 89 { 90 for(int k=1;k<n+1;k++)//检查每个结点 1~n 91 { 92 if(T[k].m!=0)//如果当前结点i有孩子，就要释放这个结点中为child动态申请的空间 93 { 94 delete []T[k].child; 95 } 96 } 97 98 }
三、个人总结
我感觉我这一章并没有怎么学好，自我反思自己因为最近太忙，而放在思考代码、课本概念的时间比较少，从而感觉完成小组合作、个人代码的时候有点困难
目标：整理前几次课堂笔记，抽时间把课本再看一遍，总结课堂讨论题；下一阶段的学习希望自己能够自律一点，抽出时间，沉住气的打代码