数据结构与算法(c 描述)-尊龙凯时官方app下载
|
|
|
教学公告
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.判断一颗二叉树是否是另一颗树的子树。
推荐阅读
- 二叉树算法应用案例