19软件工程《数据结构与算法》 第8周安排

讲解第5章的内容 137-149页

重点

1、二叉树的性质与练习

2、二叉树的遍历操作

（由中序遍历和前（后）序遍历推断出一颗唯一的二叉树）

3、二叉树的存储结构和递归算法

（链式存储结构的程序实现）

4、树和二叉树的转化

大家可以根据自己的情况进行相应的预习

师说

渗透着大爱精神的思政教育以“随风潜入夜，润物细无声”的方式走进了《数据结构与算法》课堂。

网上看到这样一个故事，不知是真是假，反正有点意思。

联合利华引进了一条香皂包装生产线，使用中发现这条生产线有个缺陷:常常会有盒子里没装入香皂。总不能把空盒子卖给顾客啊，他们只得请了一个自动化的博士后来解决这个问题。博士后组建了一个十几人的科研攻关小组专门研究分拣空的香皂盒，项目涉及到了机械、微电子、自动化、X射线探测等技术，前后总共花了90多万，成功解决了问题。每当生产线上有空香皂盒通过时，两旁的探测器就会检测到，并且驱动一只机械手把空皂盒推走。
　　在中国南方有个乡镇企业也买了同样的生产线，老板发现这个问题后大为光火，找来一个小工来说“你你你把这个问题搞定，不然你给我爬走。”小工临危受命，很快想出了解决办法。他花了190块钱在生产线旁边放了一台大功率的电风扇猛吹，于是空皂盒通过生产线时就被吹走了。。。

这个故事在网上引起很大的争议，我相信大家看完后也会有不少想法，不过我在这里只想说，其实很多复杂的问题都是可以用简单的方法处理的，关键在于你肯不肯动脑筋，肯不肯创新。同理，我们通过树和二叉树的转化，实现了化繁为简，大大提高了算法的效率。

希望各位同学在在工作和学习中要勇于发明和创新、工作严谨、细致，精于协调和沟通，培养学生的团队合作精神。希望大家在遇到问题时，能够掌握分析问题、解决问题的手段和方法，遇到难题时，能够善于转化思路，主动地把课程知识融入到学习、实践的过程中，培养工程实践能力及大国工匠精神。

出处:https://www.haha.mx/joke/1554416

二叉树常见面试题（https://www.cnblogs.com/33debug/p/7252371.html）

1. 求两个节点的最近公共祖先；

2. 求二叉树中最远的两个节点的距离；

3. 由前序遍历和中序遍历重建二叉树（如:前序序列:1 2 3 4 5 6 - 中序序列 :3 2 4 1 6 5）；

4. 判断一棵树是否是完全二叉树 ；

5. 将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向；

6.求二叉树的宽度；

7. 判断一棵二叉树是否是平衡二叉树；

8.判断一颗二叉树是否是另一颗树的子树。