|
|
教学公告
22软件工程《数据结构与算法》第7周教学安排
讲解第5章的内容131、134-146页
重点
1、树的遍历
2、二叉树的逻辑结构
3、二叉树的性质与练习
4、二叉树的遍历操作
（由中序遍历和前（后）序遍历推断出一颗唯一的二叉树）
3、二叉树的存储结构和递归算法
（链式存储结构的程序实现）
大家可以根据自己的情况进行相应的预习
师说
为什么要有树
一百个数字，无序排列，我们要根据已知的某个数字a，找到a在这一百个数字中的位置（也就是下标），如何寻找?遍历。假设100个数字可以每次遍历，1万个可以每次遍历，100万个还可以么?再计算遍历的频率，不好好掌握，简单的遍历就可以把负责遍历的人给忙死。
这时候人们开始思考，怎么样可以快速定位呢?很简单，如果插入的时候有顺序，那么这样的遍历就变得非常简单。我们都知道1-100中间如果要找某个数字，我们肯定第一个判断的是50这个数值与要定位的数字a的大小对比（因为有序了，所以大小对比才有意义）。如果小于50，那么我们下一次会先判断25，如果大于50，那么我们会判断75……这就是常见的二分法，我们判断出来要找的数字小于50时，我们就不需要去判断50-100中间的这一堆数字，对比遍历，我们就相当于少了一半多工作量，一直循环下去，对比遍历，遍历的数据越多，效率越高。具体研究请自行百度 二分法 时间/空间复杂度，去得出结论。
编程中遇到这样的问题就有更多，因为查找的效率严重影响我们系统反应的时间。计算机中如何体现上文所述的二分法呢?聪明的人根据二分法的判断顺序，设计了一个有左子树，右子树的树形结构，命名为二叉树。二叉树必须有序，否则无序的二叉树，数据来了都不知道要放在什么地方。
二叉树（Binary Tree）的知识点是程序员面试的常考点，所以平时更应该注重这方面知识的积累。这篇文章主要涉及二叉树的基础知识和基础操作，对初学者相当于是一个引导。若想进一步理解二叉树相关的知识，可以找找相关的技术书籍参考学习。
数据来源:https://blog.csdn.net/chuogangrong4739/article/details/101053059
https://zhuanlan.zhihu.com/p/121602717
二叉树常见面试题（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.判断一颗二叉树是否是另一颗树的子树。
推荐阅读
- 二叉树算法应用案例
https://blog.csdn.net/luyaran/article/details/53992796
