一、树的建立
首先要做的事当然是建树,各种操作都是基于一棵树上的
int BulidTree(node t[]) { bool check[100] = {false}; int n; char x, y; cin >> n; for (int i=0; i<n; i++){ cin >> t[i].name >> x >> y; if(x!='-'){ t[i].lch = x-'0'; check[t[i].lch] = true; } else t[i].lch = -1; if(y!='-'){ t[i].rch = y-'0'; check[t[i].rch] = true; } else t[i].rch = -1; } for (int i=0; i<n; i++){ //if(!check[i]) cout<<t[i].lch;//Èç¹ûcheckΪfalseÔò } }
二、树的遍历
在这章我们学习了四种遍历的方法:先序遍历,中序遍历,后序遍历和层序遍历。
我觉得遍历还是非常重要的,我们这次做的三道题都利用了遍历,而在不同的情况下需要判断用什么遍历方法做合适。
先序遍历
void PreOrderTravel(node t[], int x) { cout << t[x].name << " "; if(t[x].lch!=-1) PreOrderTravel(t, t[x].lch); if(t[x].rch!=-1) PreOrderTravel(t, t[x].rch); }
中序遍历
void InOrderTravel(node t[], int x) { if(t[x].lch!=-1) InOrderTravel(t, t[x].lch); cout << t[x].name << " "; if(t[x].rch!=-1) InOrderTravel(t, t[x].rch); }
后续遍历
void PostOrderTravel(node t[], int x) { if(t[x].lch!=-1) PostOrderTravel(t, t[x].lch); if(t[x].rch!=-1) PostOrderTravel(t, t[x].rch); cout << t[x].name << " "; }
层序遍历
void levelOrderTraverse(node t[], int x) { int tmp; queue<int> q; q.push(x); while(!q.empty()){ tmp = q.front(); q.pop(); if(tmp!=-1){ cout << t[tmp].name << " "; q.push(t[tmp].lch); q.push(t[tmp].rch); } } }
三、实践出真知
当然,前面的说再多也没用,最重要的是要利用这些知识去解决问题。
List Leaves
这题主要是找叶子节点,用到了层序遍历和队列。
树的同构
这题还是要遍历的问题,但是有很多细节的点要注意,所以这题我改了很多次才正确。在这题我用了很多的if语句,所以我注意到了if语句的易错的地方,就是if和else if的问题。
-
if为如果,就是如果这种情况,如果那种情况。
-
else if 不是上一个条件的前提下,如果是这个条件。
-
if无论是否满足条件都会向下执行,知道程序结束,else if 满足一个条件就会停止执行。
-
由于if都会执行一遍,则可能会同一个需要判断的事件,会进入2个if语句中,出现错误,而else if就不会发生这样的事情。
if(t1[x].lch!=-1) { if(t1[t1[x].lch].data==t2[t2[y].lch].data) com(t1,t2, t1[x].lch,t2[y].lch); else if(t1[t1[x].lch].data==t2[t2[y].rch].data) com(t1,t2, t1[x].lch,t2[y].rch); else { a=-1; return 0; } } if(t1[x].rch!=-1) {//右孩子不为空 if( t1[t1[x].rch].data==t2[t2[y].lch].data) com(t1,t2, t1[x].rch,t2[y].lch); else if( t1[t1[x].rch].data==t2[t2[y].rch].data) com(t1,t2, t1[x].rch,t2[y].rch); else { a=-1; return 0; } }
我这部分的一开始就没注意到这个问题,所以没能通过。以后一定要注意这个。
深入虎穴
这题是老师带着我们做的,跟着老师的思路感觉特别清晰,很快就做出来了,但是换了是自己的话可能会花很长时间去做。但是我回去还是自己再看了一遍,直到自己完全明白了,再写了一次,感觉印象就很深刻了。
四、小结
总的来说这次的主要问题是一些小细节没有注意,或者说是一些临界点问题,像树的同构那题主要是看到PTA上的提示来解决没有注意到的点,以后做题希望更加注意这种问题,多考虑不同的情况。然后是一定要理解上课老师带我们做的题,虽然上课的时候跟着老师一起做了,但课后还是需要去再加深理解,自己再做一次。
五、目标
上次的目标是看回以前的题,再自己做一次。不过我还没全部完成,所以我接下来依然是继续执行这个目标,慢慢来,相信自己一定会越来越好的。