第五章小结

1.第五章中有很多关于树的定义需要搞清楚,下面是几个我容易搞混的或者没有注意到的

(1)结点的度:结点拥有的子树数。

(2)树的度:树内个结点度的最大值

(3)树的深度:树中结点的最大层次称为树的深度或高度

(4)有序树和无序树:树中结点的各子树看成从左到右是有次序的,为有序树,否则为无序树

(5)完全二叉树:深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,为完全二叉树。

2.*二叉树的5个性质

(1)二叉树在第i层上至多有2i-1个结点

(2)深度为k的二叉树至多有2k-1个结点(k>=1)

(3)对于任何一棵二叉树T,其终端结点数为n0,度为2的结点数为n2,则n0=n2+1.

(4)具有n个结点的完全二叉树的深度为logn向下取整+1

(5)对一棵有n个结点的完全二叉树,按层序编号,对任一结点i:(1)i=1,则i为根;i>1,则双亲为i/2向下取整。(2)若2i>n,则结点i无左孩子;否则其左孩子为2i.(3)若2i+1>n,则i无右孩子;否则其右孩子为2i+1;

 

3.二叉树的存储结构以及遍历算法

顺序存储

链式存储:二叉链表(含左右孩子两个指针域),三叉链表(含三个指针域,左右孩子及父母)

*遍历二叉树:将非线性的二叉树排成一个线性序列。

(1)先序遍历

(2)中序遍历

(3)后序遍历

这三种方法都使用了递归算法,只是访问根节点的顺序不同。

(4)层次遍历:用到了STL里的queue,借用队列来完成的层次遍历。

做题的时候跟着老师的思路,完成了层次遍历那道作业题。在后面的实践题中也都用到了层次遍历的方法。

4.树的存储结构:双亲表示法,孩子表示法,孩子兄弟表示法

5.森林和二叉树的转换:依托于孩子兄弟表示法完成,左孩子右兄弟

6.哈夫曼树:这里也有很多的定义

(1)结点带权路径长度:该结点到树根之间的路径长度与结点上权的乘积:

(2)树的带权路径长度:树中所有叶子结点的带权路径长度之和,WPL.

哈夫曼树为WPL最小的二叉树。

下面就是本章实践1树的同构的做题心得

一开始的时候,我没有搞清楚它叫我做什么,后来看看那个样例图,了解到左右孩子可以交换位置,但是该节点的孩子不会跑到别的节点上去,还是它的孩子。

然后我在半懵的状态下,以老师教的层次遍历的结构为基础,在里面加了几句判断,然后对了一半,后面那一半我不会改了。说实话,我也不知道是怎么对的。

后来我又改进了一点,至少我清楚这题是什么意思了。

void level(node t[],node h[],int x,int y)
{
   queue<int> q;
   queue<int> p;
   int temp=0,f=0;
   q.push(x);//t的根节点入栈 
   p.push(y);//h的根节点入栈
   int flag=0;
   while(!q.empty()&&!p.empty())//当队列q和队列p都不为空时 
   {
       temp=q.front(); 
       f=p.front();
       
       q.pop();
       p.pop();
       if(temp!=-1&&f!=-1)//判断temp和f 都不为空 
       {

         if((t[t[temp].lch].name==h[h[f].rch].name)||(t[t[temp].rch].name==h[h[f].lch].name)||(t[t[temp].lch].name==h[h[f].lch].name))//判断这一层的四种情况是否成立
         flag=1;
           else {
           flag=0;
           }
           q.push(t[temp].lch);//q的左孩子入队 
        q.push(t[temp].rch);//q的右孩子入队 
        p.push(h[f].lch);//p的左孩子入队 
        p.push(h[f].rch);    //p的右孩子入队 
       }
       else flag=0;
    } 
    
    if(flag==1)
    cout<<"Yes";
    else cout<<"No";
}

这个是不完全的,我考虑的情况没有考虑完。没有考虑到两个都为空树时的情况,一个为空一个不为空树时的情况。还有在两个都不为空时,判断同构的条件也很混乱。

所以我一直纠着这个地方,一点点改,一点点测试,没有成功。最后我问了同学,她又给了我一个方向,就是那些我没有考虑到的情况,还有入队的判断。于是我又改了一遍。

void level(node t[],node h[],int x,int y)
{
   queue<int> q;
   queue<int> p;
   int temp=0,f=0;
   q.push(x);//t的根节点入栈 
   p.push(y);//h的根节点入栈
   int flag=0;
   if(x==-1&&y==-1) //两个都为空树,为同构 
   flag=1;
   if((q.empty()&&!p.empty())||(!q.empty()&&p.empty()))//一个为空,一个不为空,非同构 
   flag=0;
   while(!q.empty()&&!p.empty())//当队列q和队列p都不为空时 
   {
       temp=q.front(); 
       f=p.front();
       q.pop();
       p.pop();
       if(t[temp].name==h[f].name)//上一层没有交换 ,根结点相同
    {
     if(t[t[temp].lch].name==h[h[f].lch].name||t[t[temp].rch].name==h[h[f].lch].name||t[t[temp].lch].name==h[h[f].rch].name||t[t[temp].rch].name==h[h[f].rch].name)//在上一层相等的情况下,判断这一层是否符合同构 
     flag=1;

    else flag=0;
    }
    //列举所有孩子入队的情况
    if(t[temp].lch!=-1&&h[f].lch!=-1)
    {
        q.push(t[temp].lch);
        p.push(h[f].lch);
    }
    if(t[temp].rch!=-1&&h[f].rch!=-1)
    {
        q.push(t[temp].rch);
        p.push(h[f].rch);
    }
    if(t[temp].lch==-1&&h[f].lch!=-1)
    {
        p.push(h[f].lch);
    }
    if(t[temp].lch!=-1&&h[f].lch==-1)
    {
        q.push(t[temp].lch);
    }
    if(t[temp].rch==-1&&h[f].rch!=-1)
    {
        p.push(h[f].rch);
    }
    if(t[temp].rch!=-1&&h[f].rch==-1)
    {
        q.push(t[temp].rch);
    }
}
    if(flag==1)
    cout<<"Yes";
    else cout<<"No";

我把所有孩子的入队情况列举了一遍,然后那些问题又改了一遍,测试,又是不一样的错误。后来,她帮我看了,修改了一些问题,以及教给我她的做法,于是换了她的思路,改

void level(node t[],node h[],int x,int y)
{
   queue<int> q;
   queue<int> p;
   int temp=0,f=0;
   int flag=1;
   if(x==-1&&y==-1) //两个都为空树,为同构 
   flag=1;
   else if((x==-1&&y!=-1 )||(x!=-1&&y==-1))//一个为空,一个不为空,非同构 
   flag=0;
   
   else
   {
   q.push(x);//t的根节点入栈 
   p.push(y);//h的根节点入栈
   while(!q.empty()&&!p.empty())//当队列q和队列p都不为空时 
   {
       temp=q.front(); 
       f=p.front();
       q.pop();
       p.pop();
       if(t[temp].name==h[f].name)//上一层没有交换,根节点相同 
    {
     if(t[t[temp].lch].name==h[h[f].lch].name&&t[t[temp].rch].name==h[h[f].rch].name)//在上一层相等的情况下,这一层没有交换,看左孩子等不等于左孩子,右孩子等不等于右孩子 
        {
        if(t[temp].lch!=-1)q.push(t[temp].lch);
        if(t[temp].rch!=-1)q.push(t[temp].rch);
        if(h[f].lch!=-1)p.push(h[f].lch);
        if(h[f].rch!=-1)p.push(h[f].rch);
        }
       else    if(t[t[temp].lch].name==h[h[f].rch].name&&t[t[temp].rch].name==h[h[f].lch].name)//这一层交换了,t的左孩子等不等于h的右孩子或者t的右孩子等不等于h的左孩子
        {
//则这一层的h入队顺序就反过来,以达到和t一样入队顺序 if(t[temp].lch!=-1)q.push(t[temp].lch); if(t[temp].rch!=-1)q.push(t[temp].rch); if(h[f].rch!=-1)p.push(h[f].rch); if(h[f].lch!=-1)p.push(h[f].lch); } else flag=0; } else flag=0; } } if(flag==1) cout<<"Yes"; else cout<<"No"; }

 

这回终于对了,她是以一个反向的思维去解这道题。如果这一层没有交换,即t和h这一层完全相同,则正常入队。如果这一层交换了,即t和h这一层不同,那就将h反过来入队,就和t一样了。如果t和h的一层交换一层没有交换等等这些情况都可以考虑到了。

所以,我发现自己写的代码还是很多错漏,不会自己debug,所以还是要把基础知识学好,做题才有支撑。

 对于上一次的目标,我觉得我的课本内容还没有记得很熟练,但是还可以,在老师的带领下,我觉得结构已经清晰。剩下的就是作业问题了,每道题都不一样,但是尽量的,希望自己能做好一道题,清楚明白。

接下来目标,好好巩固自己的书本知识,做复习预习,有时间尝试那些实践2.

上一篇:第五章学习小结


下一篇:[BZOJ 3514]Codechef MARCH14 GERALD07加强版 (CHEF AND GRAPH QUERIES)