DS博客作业——树
1.本周学习总结
1.思维导图
2.谈谈你对树结构的认识及学习体会。
在树这一章节，我们学习的是二叉树的算法。 树的构建：一种是直接给树的顺序存储结构的字符串，一种是通过先序遍历和中序遍历、或中序遍历和后序遍历来构造树（理解的还比较乱），还 有一种哈夫曼树的构造。 树的遍历：比较难的遍历是层次遍历，层次遍历需要利用环形队列（需复习）来进行操作。 线索二叉树到现在还是傻傻分不清。 结构体的构建也超级重要。 在树中常常会用到递归算法，递归口的设置也是一大难点。
2.PTA实验作业
2.1.题目1：7-3 jmu-ds-二叉树层次遍历
2.1.1设计思路（伪代码）
输入表示二叉树的顺序存储结构的字符串；根据字符串构造树{ if 当前字符串下标>字符串长度||当前字符为#||者树为空 then return NULL； end if bt->lchild=递归调用建树函数，下标为2*i； bt->rchild=递归调用建树函数，下标为2*i+1;}层次遍历{ 定义环形队列; 根节点入队; while qu不为空 do 出队并输出; if 有左孩子 then 将左孩子入队; end if if 有右孩子 then 将右孩子入队; end if end while} 2.1.2代码截图
2.1.3本题PTA提交列表说明。
- Q1：以为环形队列不能用queue类，结果把环形队列的代码都再写一遍。。。
A1：层次遍历其实只是需要一个队列来存放顺序，选取环形队列只是为了防止假溢出，而C++queue类没有这个顾虑。
- Q2：其实刚开始的时候，在Dev-C++上编译错误，常把p->data=qu->data[qu->front]。
A2：p->data是char型，qu->data[]是BinTree型！！！搞清楚
- Q3:树为空时，没有“NULL”输出。
A3:因为直接考虑第二个字符（因为第一个为‘#’）没有考虑到只有一个#的情况，即树为空的情况。再加上判断条件if(str[i]=='\0'),就好啦。
- Q4:如何控制空格。
A4:直接定义一个全局变量flag，用flag控制格式。
2.2.题目2：7-4 jmu-ds-二叉树叶子结点带权路径长度和
2.2.1设计思路（伪代码）
创建树CreateBT(string str,int i){ //i为传入的字符的下标 if 下标越界||字符为‘#’||树为空 then return NULL； end if bt->lchild=递归调用建树函数，下标为2*i； bt->rchild=递归调用建树函数，下标为2*i+1;}求带权路径长度和void GetWpl(BinTree bt,int h,int &wpl ){ //h为层数，根节点为0层 if 树为空 then return ; end if if 该结点是叶子节点 then 路径长wpl=叶子节点的权重*层数； end if 递归调用GetWpl函数，查找左孩子的叶子节点，层数+1； 递归调用GetWpl函数，查找右孩子的叶子节点，层数+1；} 2.2.2代码截图
2.2.3本题PTA提交列表说明。
- Q1：在写建树函数时，忘记左孩子、右孩子与双亲结点的下标关系。
- A1：在一棵二叉树的顺序存储结构中，设该节点下标为i，则左孩子下标为2i，右孩子下标为2i+1。
- Q2：路径长的公式搞错。
A2：当根节点算0层时，每个叶子节点的wpl=权重层数；当根节点算第1层的时候，每个叶子节点的wpl=权重（层数-1）。
2.3.题目3：题目名称：7-5 jmu-ds-输出二叉树每层节点
2.3.1设计思路（伪代码）
定义两个树指针，指向当前位置指针curNdoe，指向每层最后一个节点位置的指针lastNode；定义一个树结构类型的队列q；定义控制层数变化的变量flag，令flag=1；令curNode=BT；令lastNode=BT；if 树为空 then 输出“NULL”； return；end if将根节点入队；while 队列不为空 do curNode=队首元素； if curNode有左孩子 then curNode的左孩子进队; end if if curNode有右孩子 then curNode的右孩子进队； end if if flag=1 then 输出格式“层数：”； end if if curNode为下一层的最后一个元素(即curNode=lastNode) then 输出目前队首结点； 出队； lastNode=队尾结点； flag=1； end if 其他情况 输出队首结点； 出队； flag=0；end while
2.3.2代码截图
2.3.3本题PTA提交列表说明。
- Q1：当每一层最后结点不在上一层最后结点的右结点，则答案会出现错误。
- A1：记录上一层每个结点最靠右边的结点，在要进入下一层结点遍历时赋值给lastNode。
3、阅读代码
3.1 题目：玩转二叉树
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。输入样例：71 2 3 4 5 6 74 1 3 2 6 5 7输出样例：4 6 1 7 5 3 2
3.2 解题思路
不必做镜像反转，只用在层次遍历的时候，先加入右儿子结点，再加入左儿子结点即可。
3.3 代码截图
3.4 学习体会
这道题按正常思路就是在建树的时候交换非叶子节点的左右孩子。但在正确的代码却是，只要在层次遍历的时候，将改动一下就可以，胜在灵活。