数据结构与算法（c 描述）-k8凯发旗舰

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

（）

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

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

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

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

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

6.求二叉树的宽度；

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

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

推荐阅读

1. 二叉树算法应用案例

2.

3. 二叉树的前世今生