第五章学习小结

一、树的建立

首先要做的事当然是建树,各种操作都是基于一棵树上的

 

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的问题。

  1. if为如果,就是如果这种情况,如果那种情况。

  2. else if 不是上一个条件的前提下,如果是这个条件。

  3. if无论是否满足条件都会向下执行,知道程序结束,else if 满足一个条件就会停止执行。

  4. 由于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上的提示来解决没有注意到的点,以后做题希望更加注意这种问题,多考虑不同的情况。然后是一定要理解上课老师带我们做的题,虽然上课的时候跟着老师一起做了,但课后还是需要去再加深理解,自己再做一次。

五、目标

  上次的目标是看回以前的题,再自己做一次。不过我还没全部完成,所以我接下来依然是继续执行这个目标,慢慢来,相信自己一定会越来越好的。

上一篇:Portworx Essential上手操作指南


下一篇:二叉排序树的构造