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个结点的完全二叉树的深度为log2 n向下取整+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.