第5章学习总结

   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 }