1.本周学习总结

1.1思维导图

1.2学习体会

本周学习了树的相关知识，了解了树结构体的应用和基本操作

学习了二叉树的遍历，创建以及哈夫曼树的相关操作

通过树的构建等操作熟练了递归的使用

2.PTA实验作业

2.1

二叉树叶子结点带权路径长度和

2.1.1 设计思路

if i>len-1 //超过最大节点数

    return NULL

if str[i]=='#' //孩子节点为空

    return NULL

为节点各项赋值

i=temp

while(temp > 1) //由i值计算元素层次

    temp/=2

    num++

bt->wpl=num

递归建左孩子节点

递归建右孩子节点

int wpl=0

if 树为空

    return 0

if 叶子节点

    wpl=tree->data*tree->wpl

    return wpl

wpl+=左孩子节点权带路径和

wpl+=右孩子节点权带路径和

return wpl

2.1.2 代码截图

2.1.3 本题PTA提交列表说明

开始时使用不带路径长的结构体，在GetWpl函数中另行计算路径长，一个测试点不能通过

重新设计了结构体，简化计算后正确

2.2

二叉树层次遍历

2.2.1 设计思路

if 树为空

    cout << NULL

    return

bt进队

while 队不空

    t=队头元素

    按格式输出t

    t出队

    if 有左孩子

        左孩子进队

    if 有右孩子

        右孩子进队

2.2.2 代码截图

2.2.3 本题PTA提交列表说明

输出格式判定代码错误

修改判定条件后正确

2.3

修理牧场

2.3.1 设计思路

创建递增优先队列

for i=0 to num

    各长度进队

while (队不空)

    队头两元素出队

    temp+=队头两元素和

    队头两元素和进队

返回temp

2.3.2 代码截图

2.3.3 本题PTA提交列表说明

在提交之前用了n种（完全错误的）思路解决这题，一直跑不出结果就放着了

上课时老师讲了priority_queue的解法，发现用priority_queue的做法极度简便，一次过

3.阅读代码

3.1 题目

二叉树的右视图

3.2 解题思路

本题相当于使用层次遍历取各层最右节点

1.对树进行层次遍历

2.从右至左将元素进队

3.将队头元素加入链表

4.返回链表

3.3 代码截图

3.4 学习体会

本题复习了个人较不熟练的层次遍历操作

学会利用队列取得每层最边缘元素

巴特西

DS博客作业05—树

1.本周学习总结

1.1思维导图

1.2学习体会

2.PTA实验作业

2.1

2.1.1 设计思路

2.1.2 代码截图

2.1.3 本题PTA提交列表说明

2.2

2.2.1 设计思路

2.2.2 代码截图

2.2.3 本题PTA提交列表说明

2.3

2.3.1 设计思路

2.3.2 代码截图

2.3.3 本题PTA提交列表说明

3.阅读代码

3.1 题目

3.2 解题思路

3.3 代码截图

3.4 学习体会

最新文章

热门文章